Decomposition for adjustable robust linear optimization subject to uncertainty polytope

• DOI: 10.1007/s10287-016-0249-2
• Publication Date: 2016-02-23T12:48:12Z
• Authors: Josette Ayoub; Michael Poss
• Keywords: 0211 other engineering and technologies; [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]; 02 engineering and technology; [INFO.INFO-RO] Computer Science [cs]/Operations Research [math.OC]

We present in this paper a general decomposition framework to solve exactly adjustable robust linear optimization problems subject to poly-tope 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.