The quadratic shortest path problem: complexity, approximability, and solution methods - Archive ouverte HAL Access content directly
Journal Articles European Journal of Operational Research Year : 2018

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

(1) , (2) , (2) , (3) , (4) , (5) , (2)
1
2
3
4
5

Abstract

We consider the problem of finding a shortest path in a directed graph with a quadratic objective func- tion (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 ef- ficient 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 10 0 0 nodes.

Dates and versions

hal-01781605 , version 1 (30-04-2018)

Identifiers

Cite

Borzou Rostami, André Chassein, Michael Hopf, Davide Frey, Christoph Buchheim, et al.. The quadratic shortest path problem: complexity, approximability, and solution methods. European Journal of Operational Research, 2018, 268 (2), pp.473 - 485. ⟨10.1016/j.ejor.2018.01.054⟩. ⟨hal-01781605⟩
252 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More