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

Autor: André Chassein, Davide Frey, Federico Malucelli, Michael Hopf, Borzou Rostami, Christoph Buchheim, Marc Goerigk
Přispěvatelé: École Polytechnique de Montréal (EPM), Fachbereich Mathematik [Kaiserslautern], Technische Universität Kaiserslautern (TU Kaiserslautern), the World Is Distributed Exploring the tension between scale and coordination (WIDE), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Fakultät für Mathematik [Dortmund], Dipartimento di Elettronica e Informazione (DEI), Politecnico di Milano [Milan] (POLIMI), Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1)
Jazyk: angličtina
Rok vydání: 2018
Předmět:
Zdroj: European Journal of Operational Research
European Journal of Operational Research, 2018, 268 (2), pp.473-485. ⟨10.1016/j.ejor.2018.01.054⟩
European Journal of Operational Research, Elsevier, 2018, 268 (2), pp.473-485. ⟨10.1016/j.ejor.2018.01.054⟩
ISSN: 0377-2217
1872-6860
Popis: International audience; 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.
Databáze: OpenAIRE
Externí odkaz: