Optimization Online


Robust combinatorial optimization with knapsack uncertainty

M. Poss(michael.poss***at***lirmm.fr)

Abstract: We study in this paper min max robust combinatorial optimization problems for an uncertainty polytope that is defined by knapsack constraints, either in the space of the optimization variables or in an extended space. We provide exact and approximation algorithms that extend the iterative algorithms proposed by Bertismas and Sim (2003). We also study the limitation of the approach and point out NP-hard situations. Then, we approximate axis-parallel ellipsoids with knapsack constraints and provide an approximation scheme for the corresponding robust problem. The approximation scheme is also adapted to handle the intersection of an axis-parallel ellipsoid and a box.

Keywords: robust optimization, combinatorial optimization, approximation algorithms, ellipsoidal uncertainty

Category 1: Robust Optimization

Category 2: Combinatorial Optimization

Citation: Discrete Optimization, In press

Download: [PDF]

Entry Submitted: 09/26/2017
Entry Accepted: 09/26/2017
Entry Last Modified: 09/26/2017

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