Given an instance of the quadratic shortest path problem (QSPP) on a digraph $G$, the linearization problem for the QSPP asks whether there exists an instance of the linear shortest path problem on $G$ such that the associated costs for both problems are equal for every $s$-$t$ path in $G$. We prove here that the linearization problem for the QSPP on directed acyclic graphs can be solved in ${\mathcal O}(nm^{3})$ time, where $n$ is the number of vertices and $m$ is the number of arcs in $G$. By exploiting this linearization result, we introduce a family of lower bounds for the QSPP on acyclic digraphs. The strongest lower bound from this family of bounds is the optimal solution of a linear programming problem. To the best of our knowledge, this is the first study in which the linearization problem is exploited to compute bounds for the corresponding optimization problem. Numerical results show that our approach provides the best known linear programming bound for the QSPP. We also present a lower bound for the QSPP that is derived from a sequence of problem reformulations, and prove finite convergence of that sequence. This lower bound belongs to our family of linear bounds, and requires less computational effort than the best bound from the family.
Article
View A polynomial time algorithm for the linearization problem of the QSPP and its applications