The Quadratic Shortest Path Problem: Complexity, Approximability, and Solution Methods

Borzou Rostami(borzou.rostamimath.tu-dortmund.de)
André Chassein(chasseinmathematik.uni-kl.de)
Michael Hopf(hopfmathematik.uni-kl.de)
Davide Frey(davide.freyinria.fr)
Christoph Buchheim(christoph.buchheimmath.tu-dortmund.de)
Federico Malucelli(federico.malucellipolimi.it)
Marc Goerigk(m.goerigklancaster.ac.uk)

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

Category 1: Combinatorial Optimization

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Citation:

Download: [PDF]

Entry Submitted: 02/24/2016
Entry Accepted: 02/24/2016
Entry Last Modified: 02/24/2016

Modify/Update this entry