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

International audienceThis work addresses the robust counterpart of the shortest pathproblem (RSPP) with a correlated uncertainty set. Because thisproblem is difficult, a heuristic approach, based on Frank– Wolfe’salgorithm named discrete Frank–Wolfe (DFW), has recently beenproposed. The aim of this paper is to propose a semi-definiteprogramming relaxation for the RSPP that provides a lower bound tovalidate approaches such as the DFW algorithm. The relaxed problemis a semi-definite programming (SDP) problem that results from abidualization that is done through a reformulation of the RSPP intoa quadratic problem. Then, the relaxed problem is solved by using asparse version of Pierra’s decomposition in a product space method.This validation method is suitable for large-size problems. Thenumerical experiments show that the gap between the solutionsobtained with the relaxed and the heuristic approaches isrelatively small.&nbsp