On solving the quadratic shortest path problem

DOI10.1287/IJOC.2018.0861zbMATH Open1451.90018arXiv1708.06580OpenAlexW2964025765MaRDI QIDQ3386757FDOQ3386757

Authors: Hao Hu, Renata Sotirov 

Publication date: 7 January 2021

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Abstract: The quadratic shortest path problem is the problem of finding a path in a directed graph such that the sum of interaction costs over all pairs of arcs on the path is minimized. We derive several semidefinite programming relaxations for the quadratic shortest path problem with a matrix variable of order $m+1$, where $m$ is the number of arcs in the graph. We use the alternating direction method of multipliers to solve the semidefinite programming relaxations. Numerical results show that our bounds are currently the strongest bounds for the quadratic shortest path problem. We also present computational results on solving the quadratic shortest path problem using a branch and bound algorithm. Our algorithm computes a semidefinite programming bound in each node of the search tree, and solves instances with up to 1300 arcs in less than an hour (!).

Full work available at URL: https://arxiv.org/abs/1708.06580

Recommendations

• The quadratic shortest path problem: complexity, approximability, and solution methods
• On Semidefinite Programming Relaxations of the Traveling Salesman Problem
• Special cases of the quadratic shortest path problem
• A low-dimensional semidefinite relaxation for the quadratic assignment problem
• Semidefinite programming lower bounds and branch-and-bound algorithms for the quadratic minimum spanning tree problem

zbMATH Keywords

alternating direction method of multiplierssemidefinite programmingbranch and boundquadratic shortest path problem

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Semidefinite programming (90C22) Paths and cycles (05C38) Transportation, logistics and supply chain management (90B06)

Cites Work

• Minimum-cost flow algorithms: an experimental evaluation
• ADMM for the SDP relaxation of the QAP
• Distributed optimization and statistical learning via the alternating direction method of multipliers
• A Mean-Variance Model for Route Guidance in Advanced Traveler Information Systems
• Validation of subgradient optimization
• The Variance-Constrained Shortest Path Problem
• Alternating direction augmented Lagrangian methods for semidefinite programming
• A boundary point method to solve semidefinite programs
• Fast projection onto the simplex and the \(l_1\) ball
• On minimum reload cost cycle cover
• The complexity of a minimum reload cost diameter problem
• Reload cost problems: Minimum diameter spanning tree
• The quadratic shortest path problem: complexity, approximability, and solution methods
• Special cases of the quadratic shortest path problem
• The Minimum Reload s-t Path/Trail/Walk Problems
• On the Slater condition for the SDP relaxations of nonconvex sets
• Quadratic Combinatorial Optimization Using Separable Underestimators

Cited In (16)

• SDP-Based Bounds for the Quadratic Cycle Cover Problem via Cutting-Plane Augmented Lagrangian Methods and Reinforcement Learning
• Lower bounds for the bandwidth problem
• On the analysis of optimization problems in arc-dependent networks
• The quadratic shortest path problem: complexity, approximability, and solution methods
• The linearization problem of a binary quadratic problem and its applications
• Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems
• Arc-dependent networks: theoretical insights and a computational study
• Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs
• Solving quadratic distance problems: an LMI-based approach
• Linearizable special cases of the quadratic shortest path problem
• Solving the quadratic minimum spanning tree problem
• Coastline matching via a graph-based approach
• On the approximability of path and cycle problems in arc-dependent networks
• Special cases of the quadratic shortest path problem
• A linear time algorithm for linearizing quadratic and higher-order shortest path problems
• Partitioning through projections: strong SDP bounds for large graph partition problems

Uses Software

• CPLEX
• Mosek
• ADMM_QAP

This page was built for publication: On solving the quadratic shortest path problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3386757)