Integer programming formulations for the elementary shortest path problem

DOI10.1016/j.ejor.2016.01.003zbMath1346.90793OpenAlexW2233296499MaRDI QIDQ322844

Leonardo 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

zbMATH Keywords

integer programmingbranch-and-cutextended formulationselementary shortest pathsubtour elimination constraints

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10)

Related Items (18)

Linearized formulations for failure aware barter exchange ⋮ Constrained shortest path tour problem: branch-and-price algorithm ⋮ Fast, flexible, and exact minimum flow decompositions via ILP ⋮ LP-based dual bounds for the maximum quasi-clique problem ⋮ MTZ-primal-dual model, cutting-plane, and combinatorial branch-and-bound for shortest paths avoiding negative cycles ⋮ A fully polynomial time approximation scheme for the probability maximizing shortest path problem ⋮ Fuzzy and robust approach for decision-making in disaster situations ⋮ A type of biased consensus-based distributed neural network for path planning ⋮ A fix‐and‐optimize heuristic for the minmax regret shortest path arborescence problem under interval uncertainty ⋮ Shortest paths with exclusive-disjunction arc pairs conflicts ⋮ A vertex-separator-based integer linear programming formulation for the partitioned Steiner tree problem ⋮ Shortest Paths in Graphs of Convex Sets ⋮ On the multistage shortest path problem under distributional uncertainty ⋮ A family of heuristic-based inequalities for maximizing overall safety margins in aircraft parking stands arrangement problems ⋮ A branch and cut algorithm for the time-dependent profitable tour problem with resource constraints ⋮ Generalized Bounded Rationality and Robust Multicommodity Network Design ⋮ Shortest paths with ordinal weights ⋮ Small-\(m\) method for detecting all longest paths

Uses Software

• SNDlib
• Concorde
• LEMON
• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Enhanced compact models for the connected subgraph problem and for the shortest path problem in digraphs with negative cycles
• The orienteering problem: a survey
• On approximating the longest path in a graph
• Projection, lifting and extended formulation integer and combinatorial optimization
• An analytical comparison of different formulations of the travelling salesman problem
• A branch-and-cut algorithm for the capacitated profitable tour problem
• A note on the separation of subtour elimination constraints in elementary shortest path problems
• 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
• Accelerated label setting algorithms for the elementary resource constrained shortest path problem
• A strong flow-based formulation for the shortest path problem in digraphs with negative cycles
• Maximum Throughput Network Routing Subject to Fair Flow Allocation
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Integer Programming Formulation of Traveling Salesman Problems
• A New Formulation for the Travelling Salesman Problem
• Subset-Row Inequalities Applied to the Vehicle-Routing Problem with Time Windows
• A new approach to the maximum-flow problem
• An algorithm for the resource constrained shortest path problem
• The prize collecting traveling salesman problem
• Solving the Orienteering Problem through Branch-and-Cut
• 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
• Finding Paths and Cycles of Superpolylogarithmic Length
• Automata, Languages and Programming
• Shortest Path Problems with Resource Constraints
• Depth-First Search and Linear Graph Algorithms
• A branch and cut approach to the cardinality constrained circuit problem.

This page was built for publication: Integer programming formulations for the elementary shortest path problem