Robustness and duality in linear programming

Abstract

In this paper, we consider a linear program in which the right hand sides of the constraints are uncertain and inaccurate. This uncertainty is represented by intervals, that is to say that each right hand side can take any value in its interval regardless of other constraints. The problem is then to determine a robust solution, which is satisfactory for all possible coefficient values. Classical criteria, such as the worst case and the maximum regret, are applied to define different robust versions of the initial linear program. More recently, Bertsimas and Sim have proposed a new model that generalizes the worst case criterion. The subject of this paper is to establish the relationships between linear programs with uncertain right hand sides and linear programs with uncertain objective function coefficients using the classical duality theory. We show that the transfer of the uncertainty from the right hand sides to the objective function coefficients is possible by establishing new duality relations. When the right hand sides are approximated by intervals, we also propose an extension of the Bertsimas and Sim's model and we show that the maximum regret criterion is equivalent to the worst case criterion.

Keywords:

• linear programming
• decision analysis
• robustness

Acknowledgements

The anonymous referee is gratefully acknowledged for his comments on a first version of the paper.