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
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 propos...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-10-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/10/21/4009 |
| _version_ | 1797467410164350976 |
|---|---|
| author | Chifaa Al Dahik Zeina Al Masry Stéphane Chrétien Jean-Marc Nicod Landy Rabehasaina |
| author_facet | Chifaa Al Dahik Zeina Al Masry Stéphane Chrétien Jean-Marc Nicod Landy Rabehasaina |
| author_sort | Chifaa Al Dahik |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-09T18:53:13Z |
| format | Article |
| id | doaj.art-ce041c7274d8491594343edd952efb37 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-09T18:53:13Z |
| publishDate | 2022-10-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-ce041c7274d8491594343edd952efb372023-11-24T05:43:28ZengMDPI AGMathematics2227-73902022-10-011021400910.3390/math10214009An 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 EvaluationChifaa Al Dahik0Zeina Al Masry1Stéphane Chrétien2Jean-Marc Nicod3Landy Rabehasaina4FEMTO-ST Institute, University Bourgogne Franche-Comté, CNRS, ENSMM, 25000 Besançon, FranceFEMTO-ST Institute, University Bourgogne Franche-Comté, CNRS, ENSMM, 25000 Besançon, FranceLaboratoire ERIC, UFR ASSP, Université Lyon 2, 69500 Lyon, FranceFEMTO-ST Institute, University Bourgogne Franche-Comté, CNRS, ENSMM, 25000 Besançon, FranceLaboratoire de Mathématiques de Besançon, University Bourgogne Franche-Comté, CNRS, 25000 Besançon, FranceThis 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.https://www.mdpi.com/2227-7390/10/21/4009robust optimizationrobust shortest path problemellipsoidal uncertaintydiscrete Frank–WolfeuncertaintySDP relaxation |
| spellingShingle | Chifaa Al Dahik Zeina Al Masry Stéphane Chrétien Jean-Marc Nicod Landy Rabehasaina 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 Mathematics robust optimization robust shortest path problem ellipsoidal uncertainty discrete Frank–Wolfe uncertainty SDP relaxation |
| title | 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 |
| title_full | 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 |
| title_fullStr | 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 |
| title_full_unstemmed | 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 |
| title_short | 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 |
| title_sort | 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 |
| topic | robust optimization robust shortest path problem ellipsoidal uncertainty discrete Frank–Wolfe uncertainty SDP relaxation |
| url | https://www.mdpi.com/2227-7390/10/21/4009 |
| work_keys_str_mv | AT chifaaaldahik ansdpdualrelaxationfortherobustshortestpathproblemwithellipsoidaluncertaintypierrasdecompositionmethodandanewprimalfrankwolfetypeheuristicsfordualitygapevaluation AT zeinaalmasry ansdpdualrelaxationfortherobustshortestpathproblemwithellipsoidaluncertaintypierrasdecompositionmethodandanewprimalfrankwolfetypeheuristicsfordualitygapevaluation AT stephanechretien ansdpdualrelaxationfortherobustshortestpathproblemwithellipsoidaluncertaintypierrasdecompositionmethodandanewprimalfrankwolfetypeheuristicsfordualitygapevaluation AT jeanmarcnicod ansdpdualrelaxationfortherobustshortestpathproblemwithellipsoidaluncertaintypierrasdecompositionmethodandanewprimalfrankwolfetypeheuristicsfordualitygapevaluation AT landyrabehasaina ansdpdualrelaxationfortherobustshortestpathproblemwithellipsoidaluncertaintypierrasdecompositionmethodandanewprimalfrankwolfetypeheuristicsfordualitygapevaluation AT chifaaaldahik sdpdualrelaxationfortherobustshortestpathproblemwithellipsoidaluncertaintypierrasdecompositionmethodandanewprimalfrankwolfetypeheuristicsfordualitygapevaluation AT zeinaalmasry sdpdualrelaxationfortherobustshortestpathproblemwithellipsoidaluncertaintypierrasdecompositionmethodandanewprimalfrankwolfetypeheuristicsfordualitygapevaluation AT stephanechretien sdpdualrelaxationfortherobustshortestpathproblemwithellipsoidaluncertaintypierrasdecompositionmethodandanewprimalfrankwolfetypeheuristicsfordualitygapevaluation AT jeanmarcnicod sdpdualrelaxationfortherobustshortestpathproblemwithellipsoidaluncertaintypierrasdecompositionmethodandanewprimalfrankwolfetypeheuristicsfordualitygapevaluation AT landyrabehasaina sdpdualrelaxationfortherobustshortestpathproblemwithellipsoidaluncertaintypierrasdecompositionmethodandanewprimalfrankwolfetypeheuristicsfordualitygapevaluation |