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 metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/hal-01099569
Contributor : Michael Poss <>
Submitted on : Sunday, January 4, 2015 - 6:23:33 PM
Last modification on : Friday, July 26, 2019 - 11:58:03 AM
Long-term archiving on : Saturday, April 15, 2017 - 1:15:06 PM

File

Poss14.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01099569, version 1

Citation

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

Share

Metrics

Record views

298

Files downloads

439