An SDP Dual Relaxation for the Robust Shortest-Path Problem with Ellipsoidal Uncertainty: Pierra’s Decomposition Method and a New Primal Frank–Wolfe-Type Heuristics for Duality Gap Evaluation

Chifaa Al Dahik (), Zeina Al Masry, Stéphane Chrétien, Jean-Marc Nicod and Landy Rabehasaina
Additional contact information
Chifaa Al Dahik: FEMTO-ST Institute, University Bourgogne Franche-Comté, CNRS, ENSMM, 25000 Besançon, France
Zeina Al Masry: FEMTO-ST Institute, University Bourgogne Franche-Comté, CNRS, ENSMM, 25000 Besançon, France
Stéphane Chrétien: Laboratoire ERIC, UFR ASSP, Université Lyon 2, 69500 Lyon, France
Jean-Marc Nicod: FEMTO-ST Institute, University Bourgogne Franche-Comté, CNRS, ENSMM, 25000 Besançon, France
Landy Rabehasaina: Laboratoire de Mathématiques de Besançon, University Bourgogne Franche-Comté, CNRS, 25000 Besançon, France

Mathematics, 2022, vol. 10, issue 21, 1-21

Abstract: This work addresses the robust counterpart of the shortest path problem (RSPP) with a correlated uncertainty set. Because this problem is difficult, a heuristic approach, based on Frank–Wolfe’s algorithm named discrete Frank–Wolfe (DFW), has recently been proposed. The aim of this paper is to propose a semi-definite programming relaxation for the RSPP that provides a lower bound to validate approaches such as the DFW algorithm. The relaxed problem is a semi-definite programming (SDP) problem that results from a bidualization that is done through a reformulation of the RSPP into a quadratic problem. Then, the relaxed problem is solved by using a sparse version of Pierra’s decomposition in a product space method. This validation method is suitable for large-size problems. The numerical experiments show that the gap between the solutions obtained with the relaxed and the heuristic approaches is relatively small.

Keywords: robust optimization; robust shortest path problem; ellipsoidal uncertainty; discrete Frank–Wolfe; uncertainty; SDP relaxation; sparse computations (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/21/4009/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/21/4009/ (text/html)

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:gam:jmathe:v:10:y:2022:i:21:p:4009-:d:956544

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().