Skip to Main content Skip to Navigation
New interface
Journal articles

Robust combinatorial optimization with variable cost uncertainty

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, espe-cially for vectors with few non-zero components. An example of budget function is 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 opti-mization problems. We show that when the budget function is affine, the resulting optimization prob-lems 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 reduc-tion in the price of robustness obtained with the new model on the shortest path problem and on a sur-vivable network design problem.
Document type :
Journal articles
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download
Contributor : Michaël Poss Connect in order to contact the contributor
Submitted on : Sunday, January 4, 2015 - 6:23:33 PM
Last modification on : Tuesday, August 30, 2022 - 5:14:20 PM
Long-term archiving on: : Saturday, April 15, 2017 - 1:15:06 PM


Files produced by the author(s)


  • HAL Id : hal-01099569, version 1



Michael Poss. Robust combinatorial optimization with variable cost uncertainty. European Journal of Operational Research, 2014, 237 (3), pp.836-845. ⟨hal-01099569⟩



Record views


Files downloads