On solving the quadratic shortest path problem
From MaRDI portal
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 , where 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 (!).
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
Cites work
- A boundary point method to solve semidefinite programs
- A Mean-Variance Model for Route Guidance in Advanced Traveler Information Systems
- ADMM for the SDP relaxation of the QAP
- Alternating direction augmented Lagrangian methods for semidefinite programming
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- Fast projection onto the simplex and the l₁ ball
- Minimum-cost flow algorithms: an experimental evaluation
- On minimum reload cost cycle cover
- On the Slater condition for the SDP relaxations of nonconvex sets
- Quadratic Combinatorial Optimization Using Separable Underestimators
- Reload cost problems: Minimum diameter spanning tree
- Special cases of the quadratic shortest path problem
- The complexity of a minimum reload cost diameter problem
- The Minimum Reload s-t Path/Trail/Walk Problems
- The quadratic shortest path problem: complexity, approximability, and solution methods
- The Variance-Constrained Shortest Path Problem
- Validation of subgradient optimization
Cited in
(17)- Special cases of the quadratic shortest path problem
- The quadratic shortest path problem: complexity, approximability, and solution methods
- The linearization problem of a binary quadratic problem and its applications
- On the analysis of optimization problems in arc-dependent networks
- Lower bounds for the bandwidth problem
- Linearizable special cases of the quadratic shortest path problem
- Coastline matching via a graph-based approach
- Solving the quadratic minimum spanning tree problem
- SDP-Based Bounds for the Quadratic Cycle Cover Problem via Cutting-Plane Augmented Lagrangian Methods and Reinforcement Learning
- Solving quadratic distance problems: an LMI-based approach
- Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs
- A linear time algorithm for linearizing quadratic and higher-order shortest path problems
- On the approximability of path and cycle problems in arc-dependent networks
- Partitioning through projections: strong SDP bounds for large graph partition problems
- Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems
- Arc-dependent networks: theoretical insights and a computational study
- A linear time algorithm for linearizing quadratic and higher-order shortest path problems
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)
