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).

View abstract PDF



FoCM 2017, based on a nodethirtythree design.