Optimization Problems in Graphs with Locational Uncertainty
- Resource Type
- Authors
- Marin Bougeret; Jérémy Omer; Michael Poss
- Source
- ROADEF 2022-23e congrès annuel de la société Française de Recherche Opérationnelle et d'Aide à la Décision
ROADEF 2022-23e congrès annuel de la société Française de Recherche Opérationnelle et d'Aide à la Décision, INSA Lyon, Feb 2022, Villeurbanne, France
HAL
- Subject
- FOS: Computer and information sciences
cutting plane algorithms
General Engineering
robust optimization
[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
cutting plane algorithm
NP
hardness
68W25, 68Q27
Computer Science - Data Structures and Algorithms
[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
NP-hardness
Data Structures and Algorithms (cs.DS)
combinatorial optimization
F.2.2
approximation algorithms
ComputingMilieux_MISCELLANEOUS
MathematicsofComputing_DISCRETEMATHEMATICS
- Language
- ISSN
- 1526-5528
1091-9856
Many discrete optimization problems amount to selecting a feasible set of edges of least weight. We consider in this paper the context of spatial graphs where the positions of the vertices are uncertain and belong to known uncertainty sets. The objective is to minimize the sum of the distances of the chosen set of edges for the worst positions of the vertices in their uncertainty sets. We first prove that these problems are [Formula: see text]-hard even when the feasible sets consist either of all spanning trees or of all s – t paths. Given this hardness, we propose an exact solution algorithm combining integer programming formulations with a cutting plane algorithm, identifying the cases where the separation problem can be solved efficiently. We also propose a conservative approximation and show its equivalence to the affine decision rule approximation in the context of Euclidean distances. We compare our algorithms to three deterministic reformulations on instances inspired by the scientific literature for the Steiner tree problem and a facility location problem. History: Accepted by David Alderson, Area Editor for Network Optimization: Algorithms & Applications. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2023.1276 .