Home > Research > Publications & Outputs > The quadratic shortest path problem

Research

Associated organisational unit

Links

Keywords

View graph of relations

The quadratic shortest path problem: complexity, approximability, and solution methods

Research output: Working paper

Published

Standard

The quadratic shortest path problem: complexity, approximability, and solution methods. / Rostami, Borzou; Chassein, André; Hopf, Michael et al.
2016.

Research output: Working paper

Harvard

Rostami, B, Chassein, A, Hopf, M, Frey, D, Buchheim, C, Malucelli, F & Goerigk, M 2016 'The quadratic shortest path problem: complexity, approximability, and solution methods'. <http://www.optimization-online.org/DB_HTML/2016/02/5341.html>

APA

Rostami, B., Chassein, A., Hopf, M., Frey, D., Buchheim, C., Malucelli, F., & Goerigk, M. (2016). The quadratic shortest path problem: complexity, approximability, and solution methods. http://www.optimization-online.org/DB_HTML/2016/02/5341.html

Vancouver

Rostami B, Chassein A, Hopf M, Frey D, Buchheim C, Malucelli F et al. The quadratic shortest path problem: complexity, approximability, and solution methods. 2016 Feb 24.

Author

Rostami, Borzou ; Chassein, André ; Hopf, Michael et al. / The quadratic shortest path problem : complexity, approximability, and solution methods. 2016.

Bibtex

@techreport{61ec7df385974430ac6997be017426c4,
title = "The quadratic shortest path problem: complexity, approximability, and solution methods",
abstract = "We consider the problem of finding a shortest path in a directed graph with a quadratic objective function (the QSPP). We show that the QSPP cannot be approximated unless P=NP. For the case of a convex objective function, an n-approximation algorithm is presented, where n is the number of nodes in the graph, and APX-hardness is shown. Furthermore, we prove that even if only adjacent arcs play a part in the quadratic objective function, the problem still cannot be approximated unless P=NP. In order to solve the problem we first propose a mixed integer programming formulation, and then devise an efficient exact Branch-and-Bound algorithm for the general QSPP, where lower bounds are computed by considering a reformulation scheme that is solvable through a number of minimum cost flow problems. In our computational experiments we solve to optimality different classes of instances with up to 1000 nodes.",
keywords = "Shortest path problem, Quadratic 0-1 optimization, Computational complexity, Branch and Bound",
author = "Borzou Rostami and Andr{\'e} Chassein and Michael Hopf and Davide Frey and Christoph Buchheim and Federico Malucelli and Marc Goerigk",
year = "2016",
month = feb,
day = "24",
language = "English",
type = "WorkingPaper",

}

RIS

TY - UNPB

T1 - The quadratic shortest path problem

T2 - complexity, approximability, and solution methods

AU - Rostami, Borzou

AU - Chassein, André

AU - Hopf, Michael

AU - Frey, Davide

AU - Buchheim, Christoph

AU - Malucelli, Federico

AU - Goerigk, Marc

PY - 2016/2/24

Y1 - 2016/2/24

N2 - We consider the problem of finding a shortest path in a directed graph with a quadratic objective function (the QSPP). We show that the QSPP cannot be approximated unless P=NP. For the case of a convex objective function, an n-approximation algorithm is presented, where n is the number of nodes in the graph, and APX-hardness is shown. Furthermore, we prove that even if only adjacent arcs play a part in the quadratic objective function, the problem still cannot be approximated unless P=NP. In order to solve the problem we first propose a mixed integer programming formulation, and then devise an efficient exact Branch-and-Bound algorithm for the general QSPP, where lower bounds are computed by considering a reformulation scheme that is solvable through a number of minimum cost flow problems. In our computational experiments we solve to optimality different classes of instances with up to 1000 nodes.

AB - We consider the problem of finding a shortest path in a directed graph with a quadratic objective function (the QSPP). We show that the QSPP cannot be approximated unless P=NP. For the case of a convex objective function, an n-approximation algorithm is presented, where n is the number of nodes in the graph, and APX-hardness is shown. Furthermore, we prove that even if only adjacent arcs play a part in the quadratic objective function, the problem still cannot be approximated unless P=NP. In order to solve the problem we first propose a mixed integer programming formulation, and then devise an efficient exact Branch-and-Bound algorithm for the general QSPP, where lower bounds are computed by considering a reformulation scheme that is solvable through a number of minimum cost flow problems. In our computational experiments we solve to optimality different classes of instances with up to 1000 nodes.

KW - Shortest path problem

KW - Quadratic 0-1 optimization

KW - Computational complexity

KW - Branch and Bound

M3 - Working paper

BT - The quadratic shortest path problem

ER -