Exact methods for solving the elementary shortest and longest path problems

DOI10.1007/S10479-016-2116-5zbMath1357.90164OpenAlexW2273056006MaRDI QIDQ512936

Quoc Trung Bui, Quang Dung Pham, Yves Deville

Publication date: 3 March 2017

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10479-016-2116-5

zbMATH Keywords

decompositionmixed integer programmingelementary shortest pathelementary longest pathnegative cycles

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Mixed integer programming (90C11)

Related Items (2)

Pre-treatment of path problems with required lengths ⋮ Global optimization for scaffolding and completing genome assemblies

Uses Software

• SteinLib
• VRP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints
• On approximating the longest path in a graph
• A note on the prize collecting traveling salesman problem
• Facet identification for the symmetric traveling salesman polytope
• Optimization of a 532-city symmetric traveling salesman problem by branch and cut
• A branch \& cut algorithm for the asymmetric traveling salesman problem with precedence constraints
• Branching rules revisited
• A lifting procedure for asymmetric traveling salesman polytope and a large new class of facets
• Solving elementary shortest-path problems as mixed-integer programs
• Symmetry helps: bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints
• Reduction tests for the prize-collecting Steiner problem
• An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem
• Accelerated label setting algorithms for the elementary resource constrained shortest path problem
• The Vehicle Routing Problem
• A strong flow-based formulation for the shortest path problem in digraphs with negative cycles
• Integer Programming Formulation of Traveling Salesman Problems
• New dynamic programming algorithms for the resource constrained elementary shortest path problem
• An algorithm for the resource constrained shortest path problem
• Odd Minimum Cut-Sets and b-Matchings
• Facets of the Asymmetric Traveling Salesman Polytope
• Note on the Complexity of the Shortest Path Models for Column Generation in VRPTW
• Mixed 0-1 Programming by Lift-and-Project in a Branch-and-Cut Framework
• A branch and cut algorithm for the Steiner problem in graphs
• Solving Steiner tree problems in graphs to optimality
• An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems
• Mixed-integer nonlinear optimization
• Shortest Path Problems with Resource Constraints
• Maximum matching and a polyhedron with 0,1-vertices
• An Algorithm for the Traveling Salesman Problem
• Depth-First Search and Linear Graph Algorithms
• On Prize‐collecting Tours and the Asymmetric Travelling Salesman Problem
• Steiner Tree Problems With Profits

This page was built for publication: Exact methods for solving the elementary shortest and longest path problems