Conference abstracts
Session C3 - Continuous Optimization
July 19, 17:00 ~ 17:30 - Room 111
On solving the quadratic shortest path problem
Renata Sotirov
Tilburg University, The Netherlands - r.sotirov@uvt.nl
The quadratic shortest path problem (QSPP) is the problem of finding a path in a digraph such that the sum of weights of arcs and the sum of interaction costs over all pairs of arcs on the path is minimized. The QSPP is NP-hard. In this talk we consider first linearizable QSPP instances whose optimal solution can be obtained by solving the corresponding instance of the shortest path problem. We also present a polynomial-time algorithm that verifies whether a QSPP instance on the directed grid graph is linearizable. Further, we present a semidefinite programming relaxation for the QSPP that provides strong bounds for non-linearizable problem instances of moderate size.
Joint work with Hao Hu (Tilburg University, The Netherlands).