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.
Type de document :
Article dans une revue
European Journal of Operational Research, Elsevier, 2014, 237 (3), pp.836-845
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01099569
Contributeur : Michael Poss <>
Soumis le : dimanche 4 janvier 2015 - 18:23:33
Dernière modification le : mercredi 4 juillet 2018 - 16:44:02
Document(s) archivé(s) le : samedi 15 avril 2017 - 13:15:06

Fichier

Poss14.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01099569, version 1

Collections

Citation

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

Partager

Métriques

Consultations de la notice

215

Téléchargements de fichiers

232