Optimization Online


A polynomial time algorithm for the linearization problem of the QSPP and its applications

Renata Sotirov(r.sotirov***at***uvt.nl)
Hu Hao(h.hu***at***tilburguniversity.edu)

Abstract: 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.

Keywords: quadratic shortest path problem, linearization problem, directed acyclic graph, lower bounds

Category 1: Combinatorial Optimization (Other )

Category 2: Integer Programming (Other )


Download: [PDF]

Entry Submitted: 01/28/2018
Entry Accepted: 01/29/2018
Entry Last Modified: 01/28/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society