Renata Sotirov, Tilburg University

Abstract

The quadratic shortest path problem (QSPP) is the problem of finding a path between two vertices in a directed graph such that the sum of interaction costs over all pairs of arcs on the path is minimized. This problem is known to be NP-hard.

In this talk we present two approaches for solving the QSPP. Our first approach is based on splitting the quadratic objective into a linearizable and a non-linearizable part. Then, the linearizable part is used to compute  efficiently good lower bounds for the QSPP. Our second approach considers a semidefinite programming relaxation for the QSPP that is solved by using the ADMM. We also present numerical results on solving the problem to optimality by using the mentioned bounds within the branch and bound framework.

Slides     Video