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

DOI10.1016/j.ejor.2018.01.054zbMath1403.90645OpenAlexW2602684069MaRDI QIDQ1754341

Marc Goerigk, Christoph Buchheim, Borzou Rostami, Davide Frey, Federico Malucelli, Michael Hopf, André B. Chassein

Publication date: 30 May 2018

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://eprints.lancs.ac.uk/id/eprint/90093/1/paper_final.pdf

zbMATH Keywords

computational complexitycombinatorial optimizationbranch-and-boundshortest path problemquadratic 0-1 optimization

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Mixed integer programming (90C11) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (13)

The quadratic cycle cover problem: special cases and efficient bounds ⋮ Linearizable special cases of the quadratic shortest path problem ⋮ A linear time algorithm for linearizing quadratic and higher-order shortest path problems ⋮ Variable-sized uncertainty and inverse problems in robust optimization ⋮ Generating constrained length personalized bicycle tours ⋮ Special cases of the quadratic shortest path problem ⋮ A conjugate direction based simplicial decomposition framework for solving a specific class of dense convex quadratic programs ⋮ On Solving the Quadratic Shortest Path Problem ⋮ The linearization problem of a binary quadratic problem and its applications ⋮ A class of exponential neighbourhoods for the quadratic travelling salesman problem ⋮ Representations of quadratic combinatorial optimization problems: a case study using quadratic set covering and quadratic knapsack problems ⋮ Approximation algorithms for cost-robust discrete minimization problems based on their LP-relaxations ⋮ Optimal decisions in stochastic graphs with uncorrelated and correlated edge weights

Cites Work

• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• Finding reliable shortest paths in road networks under uncertainty
• The Steiner travelling salesman problem with correlated costs
• Lower bounds for the quadratic minimum spanning tree problem based on reduced cost computation
• The quadratic minimum spanning tree problem: a lower bounding procedure and an efficient search algorithm
• The minimum reload \(s-t\) path, trail and walk problems
• Constrained 0-1 quadratic programming: basic approaches and extensions
• The Quadratic Assignment Problem
• Minimum-cost flow algorithms: an experimental evaluation
• On minimum reload cost paths, tours, and flows
• A New Lower Bound for the Quadratic Assignment Problem
• Improved Linear Integer Programming Formulations of Nonlinear Integer Problems
• A Mean-Variance Model for Route Guidance in Advanced Traveler Information Systems
• The Variance-Constrained Shortest Path Problem
• On approximation properties of the Independent set problem for degree 3 graphs
• Optimal and Suboptimal Algorithms for the Quadratic Assignment Problem

This page was built for publication: The quadratic shortest path problem: complexity, approximability, and solution methods