On solving the quadratic shortest path problem
From MaRDI portal
Publication:3386757
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 Mean-Variance Model for Route Guidance in Advanced Traveler Information Systems
- A boundary point method to solve semidefinite programs
- 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 Minimum Reload s-t Path/Trail/Walk Problems
- The Variance-Constrained Shortest Path Problem
- The complexity of a minimum reload cost diameter problem
- The quadratic shortest path problem: complexity, approximability, and solution methods
- Validation of subgradient optimization
Cited in
(16)- Partitioning through projections: strong SDP bounds for large graph partition problems
- Lower bounds for the bandwidth problem
- SDP-Based Bounds for the Quadratic Cycle Cover Problem via Cutting-Plane Augmented Lagrangian Methods and Reinforcement Learning
- 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
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)
