Integer programming formulations for the elementary shortest path problem
From MaRDI portal
Publication:322844
DOI10.1016/J.EJOR.2016.01.003zbMATH Open1346.90793OpenAlexW2233296499MaRDI QIDQ322844FDOQ322844
Authors: L. Taccari 
Publication date: 7 October 2016
Published in: European Journal of Operational Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ejor.2016.01.003
Recommendations
- Solving elementary shortest-path problems as mixed-integer programs
- A polyhedral study of the elementary shortest path problem with resource constraints
- New formulations for the elementary shortest-path problem visiting a given set of nodes
- Exact methods for solving the elementary shortest and longest path problems
- Valid inequalities and lifting procedures for the shortest path problem in digraphs with negative cycles
integer programmingbranch-and-cutextended formulationselementary shortest pathsubtour elimination constraints
Cites Work
- The traveling salesman problem. A computational study.
- An analytical comparison of different formulations of the travelling salesman problem
- A branch-and-cut algorithm for the capacitated profitable tour problem
- Integer Programming Formulation of Traveling Salesman Problems
- A New Formulation for the Travelling Salesman Problem
- The prize collecting traveling salesman problem
- An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems
- Solution of a Large-Scale Traveling-Salesman Problem
- Shortest Path Problems with Resource Constraints
- Depth-First Search and Linear Graph Algorithms
- The orienteering problem: a survey
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Finding Paths and Cycles of Superpolylogarithmic Length
- Automata, Languages and Programming
- On approximating the longest path in a graph
- A new approach to the maximum-flow problem
- Title not available (Why is that?)
- Symmetry helps: bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints
- Accelerated label setting algorithms for the elementary resource constrained shortest path problem
- Subset-Row Inequalities Applied to the Vehicle-Routing Problem with Time Windows
- Solving the Orienteering Problem through Branch-and-Cut
- Title not available (Why is that?)
- A note on the separation of subtour elimination constraints in elementary shortest path problems
- Solving elementary shortest-path problems as mixed-integer programs
- Title not available (Why is that?)
- A strong flow-based formulation for the shortest path problem in digraphs with negative cycles
- Maximum Throughput Network Routing Subject to Fair Flow Allocation
- Enhanced compact models for the connected subgraph problem and for the shortest path problem in digraphs with negative cycles
- An algorithm for the resource constrained shortest path problem
- A branch and cut approach to the cardinality constrained circuit problem.
- Projection, lifting and extended formulation integer and combinatorial optimization
Cited In (22)
- Fuzzy and robust approach for decision-making in disaster situations
- Shortest paths with ordinal weights
- Linearized formulations for failure aware barter exchange
- A vertex-separator-based integer linear programming formulation for the partitioned Steiner tree problem
- Shortest paths with exclusive-disjunction arc pairs conflicts
- Small-\(m\) method for detecting all longest paths
- A fix‐and‐optimize heuristic for the minmax regret shortest path arborescence problem under interval uncertainty
- Shortest Paths in Graphs of Convex Sets
- Combinatorial robust optimization with decision-dependent information discovery and polyhedral uncertainty
- LP-based dual bounds for the maximum quasi-clique problem
- A fully polynomial time approximation scheme for the probability maximizing shortest path problem
- A type of biased consensus-based distributed neural network for path planning
- MTZ-primal-dual model, cutting-plane, and combinatorial branch-and-bound for shortest paths avoiding negative cycles
- A branch and cut algorithm for the time-dependent profitable tour problem with resource constraints
- On the multistage shortest path problem under distributional uncertainty
- Crack modeling via minimum-weight surfaces in 3d Voronoi diagrams
- KidneyExchange.jl: a Julia package for solving the kidney exchange problem with branch-and-price
- Fast, flexible, and exact minimum flow decompositions via ILP
- Generalized Bounded Rationality and Robust Multicommodity Network Design
- Constrained shortest path tour problem: branch-and-price algorithm
- A family of heuristic-based inequalities for maximizing overall safety margins in aircraft parking stands arrangement problems
- Solving elementary shortest-path problems as mixed-integer programs
Uses Software
This page was built for publication: Integer programming formulations for the elementary shortest path problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q322844)
