Optimization Online


Robust combinatorial optimization with cost uncertainty

Michael Poss(mjposs***at***gmail.com)

Abstract: We present in this paper a new model for robust combinatorial optimization with cost uncertainty that generalizes the classical budgeted uncertainty set. We suppose here that the budget of uncertainty is given by a function of the problem variables, yielding an uncertainty multifunction. The new model is less conservative than the classical model and approximates better Value-at-Risk objective functions, especially for vectors with few non-zero components. Examples of budget functions are constructed from the probabilistic bounds computed by Bertsimas and Sim. We provide an asymptotically tight bound for the cost reduction obtained with the new model. We turn then to the tractability of the resulting optimization problems and provide a mixed-integer linear reformulation. We show that when the budget function is affine, the resulting optimization problems can be solved by solving $n+1$ deterministic problems. We propose combinatorial algorithms to handle problems with more general budget functions. We also adapt existing dynamic programming algorithms to solve faster the robust counterparts of optimization problems, which can be applied both to the traditional budgeted uncertainty model and to our new model. We evaluate numerically the reduction in the price of robustness obtained with the new model on the shortest path problem and on a survivable network design problem.

Keywords: Combinatorial optimization, robust optimization, dynamic programming, price of robustness, budgeted uncertainty

Category 1: Robust Optimization

Category 2: Combinatorial Optimization


Download: [PDF]

Entry Submitted: 02/11/2013
Entry Accepted: 02/11/2013
Entry Last Modified: 02/11/2013

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