Optimization Problems in Graphs with Locational Uncertainty

Marin Bougeret (), Jérémy Omer () and Michael Poss ()
Additional contact information
Marin Bougeret: Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier, Centre National de la Recherche Scientifique, 34095 Montpellier, France
Jérémy Omer: Institut de Recherche Mathématique de Rennes, Institut National des Sciences Appliquées, 35700 Rennes, France
Michael Poss: Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier, Centre National de la Recherche Scientifique, 34095 Montpellier, France

INFORMS Journal on Computing, 2023, vol. 35, issue 3, 578-592

Abstract: 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 N P -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.

Keywords: combinatorial optimization; robust optimization; N P -hardness; cutting plane algorithms; dynamic programming (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2023.1276 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:35:y:2023:i:3:p:578-592

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().