Optimization Online


On Solving the Quadratic Shortest Path Problem

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

Abstract: The quadratic shortest path problem is the problem of finding a path in a directed graph such that the sum of interaction costs over all pairs of arcs on the path is minimized. We derive several semidefinite programming relaxations for the quadratic shortest path problem with a matrix variable of order $m+1$, where $m$ is the number of arcs in the graph. We use the alternating direction method of multipliers to solve the semidefinite programming relaxations. Numerical results show that our bounds are currently the strongest bounds for the quadratic shortest path problem. We also present computational results on solving the quadratic shortest path problem using a branch and bound algorithm. Our algorithm computes a semidefinite programming bound in each node of the search tree, and solves instances with up to 1300 arcs in less than an hour (!).

Keywords: quadratic shortest path problem, semidefinite programming, alternating direction method of multipliers, branch and bound

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )


Download: [PDF]

Entry Submitted: 08/16/2017
Entry Accepted: 08/16/2017
Entry Last Modified: 08/16/2017

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