Optimization Online


Polyhedral Approximation of Ellipsoidal Uncertainty Sets via Extended Formulations - a computational case study -

Andreas Bärmann (Andreas.Baermann***at***math.uni-erlangen.de)
Andreas Heidt (Andreas.Heidt***at***math.uni-erlangen.de)
Alexander Martin (Alexander.Martin***at***math.uni-erlangen.de)
Sebastian Pokutta (Sebastian.Pokutta***at***isye.gatech.edu)
Christoph Thurner (Christoph.Thurner***at***math.uni-erlangen.de)

Abstract: Robust optimization is an important technique to immunize optimization problems against data uncertainty. In the case of a linear program and an ellipsoidal uncertainty set, the robust counterpart turns into a second-order cone program. In this work, we investigate the efficiency of linearizing the second-order cone constraints of the latter. This is done using the optimal linear outer-approximation approach by Ben-Tal and Nemirovski [2001] from which we derive an optimal inner approximation of the second-order cone. We examine the performance of this approach on various benchmark sets including portfolio optimization instances as well as (robustified versions of) the MIPLIB and the SNDlib.

Keywords: robust optimization, second-order cone programming, extended formulations, mixed-integer linear programming

Category 1: Robust Optimization

Category 2: Linear, Cone and Semidefinite Programming (Second-Order Cone Programming )

Category 3: Integer Programming ((Mixed) Integer Linear Programming )


Download: [PDF]

Entry Submitted: 02/21/2014
Entry Accepted: 02/21/2014
Entry Last Modified: 12/18/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society