On solving the quadratic shortest path problem

Research output: Contribution to journalArticleScientificpeer-review

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 (!)
Original languageEnglish
JournalINFORMS Journal on Computing
Publication statusAccepted/In press - 2018

Fingerprint

Directed graphs
Costs
Shortest path
Semidefinite programming
Multiplier
Node
Directed graph
Graph
Branch and bound algorithm
Interaction

Cite this

@article{55240b45ea974222a31dcb9e3ec30e97,
title = "On solving the quadratic shortest path problem",
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 (!)",
author = "Hao Hu and Renata Sotirov",
year = "2018",
language = "English",
journal = "INFORMS Journal on Computing",
issn = "1091-9856",
publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",

}

On solving the quadratic shortest path problem. / Hu, Hao; Sotirov, Renata.

In: INFORMS Journal on Computing, 2018.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - On solving the quadratic shortest path problem

AU - Hu, Hao

AU - Sotirov, Renata

PY - 2018

Y1 - 2018

N2 - 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 (!)

AB - 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 (!)

M3 - Article

JO - INFORMS Journal on Computing

JF - INFORMS Journal on Computing

SN - 1091-9856

ER -