On Solving the Quadratic Shortest Path Problem

DOI10.1287/ijoc.2018.0861zbMath1451.90018arXiv1708.06580OpenAlexW2964025765MaRDI QIDQ3386757

Renata Sotirov, Hao Hu

Publication date: 7 January 2021

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

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

zbMATH Keywords

semidefinite programmingbranch and boundalternating direction method of multipliersquadratic shortest path problem

Mathematics Subject Classification ID

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

Related Items (11)

On the analysis of optimization problems in arc-dependent networks ⋮ SDP-Based Bounds for the Quadratic Cycle Cover Problem via Cutting-Plane Augmented Lagrangian Methods and Reinforcement Learning ⋮ Lower bounds for the bandwidth problem ⋮ Linearizable special cases of the quadratic shortest path problem ⋮ Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs ⋮ Coastline matching via a graph-based approach ⋮ 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 ⋮ The linearization problem of a binary quadratic problem and its applications

Uses Software

• CPLEX
• Mosek
• ADMM_QAP

Cites Work

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

This page was built for publication: On Solving the Quadratic Shortest Path Problem