Fulltext

Bulk-Robust combinatorial optimization

Adjiashvili, David ; Stiller, Sebastian ; Zenklusen, Rico

In: Mathematical Programming, 2015, vol. 149, no. 1-2, p. 361-390

Ajouter à la liste personnelle
    Titre
    • Bulk-Robust combinatorial optimization
    Auteur
    • Adjiashvili, David. Institute for Operations Research, ETH Zürich, Rämistrasse 101, 8092, Zurich, Switzerland
    • Stiller, Sebastian. Department of Mathematics, Berlin Institute of Technology, Strasse des 17. Juni 136, 10623, Berlin, Germany
    • Zenklusen, Rico. Department of Mathematics, ETH Zürich, Rämistrasse 101, 8092, Zurich, Switzerland
    Type de document
    • Postprint
    Langue
    • Anglais
    Publié dans
    • Mathematical Programming, 2015, vol. 149, no. 1-2, p. 361-390. Springer Berlin Heidelberg
    Autre version électronique
    Identifiant OAI-PMH
    • oai:doc.rero.ch:332688
    Summary
    We commence an algorithmic study of Bulk-Robustness, a new model of robustness in combinatorial optimization. Unlike most existing models, Bulk-Robust combinatorial optimization features a highly nonuniform failure model. Instead of an interdiction budget, Bulk-Robust counterparts provide an explicit list of interdiction sets, comprising the admissible set of scenarios, thus allowing to model correlations between failures of different components in the system, interdiction sets of variable cardinality and more. The resulting model is suitable for capturing failures of complex structures in the system. We provide complexity results and approximation algorithms for Bulk-Robust counterparts of the Minimum Matroid Basis problems and the Shortest Path problem. Our results rely on various techniques, and outline the rich and heterogeneous combinatorial structure of Bulk-Robust optimization.