Optimization Online


Robust Combinatorial Optimization under Budgeted-Ellipsoidal Uncertainty

Jannis Kurtz (jannis.kurtz***at***math.tu-dortmund.de)

Abstract: In the field of robust optimization uncertain data is modeled by uncertainty sets, i.e. sets which contain all relevant outcomes of the uncertain parameters. The complexity of the related robust problem depends strongly on the shape of the uncertainty set. Two popular classes of uncertainty are budgeted uncertainty and ellipsoidal uncertainty. In this paper we introduce a new uncertainty class which is a combination of both. More precisely we consider ellipsoidal uncertainty sets with the additional restriction that at most $\Gamma$ many uncertain parameters may differ from the ellipsoid-center at the same time. We define a discrete and a convex variant of the latter set and prove that the corresponding robust min-max problem is \NP-hard for several combinatorial problems. Furthermore we prove that for uncorrelated budgeted-ellipsoidal uncertainty the min-max problem can be solved in polynomial time for several combinatorial problems if the parameter $\Gamma$ is fixed.

Keywords: Robust Optimization, Combinatorial Optimization, Budgeted Uncertainty, Ellipsoidal Uncertainty, Complexity

Category 1: Robust Optimization

Category 2: Combinatorial Optimization

Category 3: Integer Programming (0-1 Programming )

Citation: Department for Mathematics, TU Dortmund University, Vogelpothsweg 87, 44227 Dortmund, Germany

Download: [PDF]

Entry Submitted: 08/02/2017
Entry Accepted: 08/02/2017
Entry Last Modified: 04/26/2018

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