Robustness and duality in linear programming

V Gabrel () and C Murat
Additional contact information
V Gabrel: LAMSADE, CNRS and Université Paris-Dauphine
C Murat: LAMSADE, CNRS and Université Paris-Dauphine

Journal of the Operational Research Society, 2010, vol. 61, issue 8, 1288-1296

Abstract: 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 (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (17)

Downloads: (external link)
http://link.springer.com/10.1057/jors.2009.81 Abstract (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:pal:jorsoc:v:61:y:2010:i:8:d:10.1057_jors.2009.81

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/41274

DOI: 10.1057/jors.2009.81

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald and Jonathan Crook

More articles in Journal of the Operational Research Society from Palgrave Macmillan, The OR Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().