Exact methods for solving the elementary shortest and longest path problems
From MaRDI portal
Publication:512936
DOI10.1007/S10479-016-2116-5zbMATH Open1357.90164OpenAlexW2273056006MaRDI QIDQ512936FDOQ512936
Authors: 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
Recommendations
- Valid inequalities and lifting procedures for the shortest path problem in digraphs with negative cycles
- Integer programming formulations for the elementary shortest path problem
- Solving elementary shortest-path problems as mixed-integer programs
- On the shortest path problem with negative cost cycles
- Exact and approximate algorithms for the longest induced path problem
decompositionmixed integer programmingelementary shortest pathelementary longest pathnegative cycles
Cites Work
- Solving Steiner tree problems in graphs to optimality
- Mixed-integer nonlinear optimization
- Introduction to algorithms.
- An Algorithm for the Traveling Salesman Problem
- Note on the Complexity of the Shortest Path Models for Column Generation in VRPTW
- Integer Programming Formulation of Traveling Salesman Problems
- New dynamic programming algorithms for the resource constrained elementary shortest path problem
- An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems
- Shortest Path Problems with Resource Constraints
- Depth-First Search and Linear Graph Algorithms
- Optimization of a 532-city symmetric traveling salesman problem by branch and cut
- Branching rules revisited
- The vehicle routing problem
- Mixed 0-1 Programming by Lift-and-Project in a Branch-and-Cut Framework
- Title not available (Why is that?)
- Maximum matching and a polyhedron with 0,1-vertices
- On approximating the longest path in a graph
- On Prize‐collecting Tours and the Asymmetric Travelling Salesman Problem
- A note on the prize collecting traveling salesman problem
- Symmetry helps: bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints
- 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
- Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints
- Facet identification for the symmetric traveling salesman polytope
- A branch \& cut algorithm for the asymmetric traveling salesman problem with precedence constraints
- Odd Minimum Cut-Sets and b-Matchings
- Solving elementary shortest-path problems as mixed-integer programs
- Approximating the asymmetric profitable tour
- A strong flow-based formulation for the shortest path problem in digraphs with negative cycles
- An algorithm for the resource constrained shortest path problem
- Facets of the Asymmetric Traveling Salesman Polytope
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A lifting procedure for asymmetric traveling salesman polytope and a large new class of facets
- Reduction tests for the prize-collecting Steiner problem
- A branch and cut algorithm for the Steiner problem in graphs
- Steiner Tree Problems With Profits
Cited In (7)
- Global optimization for scaffolding and completing genome assemblies
- Title not available (Why is that?)
- On exact solution approaches for the longest induced path problem
- Title not available (Why is that?)
- Recoverable robust shortest path problem under interval budgeted uncertainty representations
- Pre-treatment of path problems with required lengths
- Solving elementary shortest-path problems as mixed-integer programs
Uses Software
This page was built for publication: Exact methods for solving the elementary shortest and longest path problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q512936)
