Decomposition for adjustable robust linear optimization subject to uncertainty polytope

Josette Ayoub () and Michael Poss ()
Additional contact information
Josette Ayoub: CDS Consultant at Murex
Michael Poss: Université de Montpellier

Computational Management Science, 2016, vol. 13, issue 2, No 4, 219-239

Abstract: Abstract We present in this paper a general decomposition framework to solve exactly adjustable robust linear optimization problems subject to polytope uncertainty. Our approach is based on replacing the polytope by the set of its extreme points and generating the extreme points on the fly within row generation or column-and-row generation algorithms. The novelty of our approach lies in formulating the separation problem as a feasibility problem instead of a max–min problem as done in recent works. Applying the Farkas lemma, we can reformulate the separation problem as a bilinear program, which is then linearized to obtained a mixed-integer linear programming formulation. We compare the two algorithms on a robust telecommunications network design under demand uncertainty and budgeted uncertainty polytope. Our results show that the relative performance of the algorithms depend on whether the budget is integer or fractional.

Keywords: Adjustable robust optimization; Uncertainty polytope; Benders decomposition; Mixed-integer linear programming; Network design (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (21)

Downloads: (external link)
http://link.springer.com/10.1007/s10287-016-0249-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:comgts:v:13:y:2016:i:2:d:10.1007_s10287-016-0249-2

Ordering information: This journal article can be ordered from
http://www.springer. ... ch/journal/10287/PS2

DOI: 10.1007/s10287-016-0249-2

Access Statistics for this article

Computational Management Science is currently edited by Ruediger Schultz

More articles in Computational Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().