A note on the separation of subtour elimination constraints in elementary shortest path problems

DOI10.1016/J.EJOR.2013.03.009MaRDI QIDQ2355890zbMATH OpenOpenAlexFDO

Authors Michael Drexl

Publication date 28 July 2015

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejor.2013.03.009

zbMATH Keywords

branch-and-cutinteger programmingseparationstrong componentssubtour elimination constraints

Mathematics Subject Classification ID

Applications of graph theory (05C90) Deterministic network models in operations research (90B10) Integer programming (90C10) Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• Requiem for the Miller-Tucker-Zemlin subtour elimination constraints?
• Efficient separation routines for the symmetric traveling salesman problem. I: General tools and comb separation
• On solving cycle problems with branch-and-cut: extending shrinking and exact subcycle elimination separation algorithms
• Shortest Path Problems with Resource Constraints
• Vehicle routing problem with elementary shortest path based column generation

Cites work

• A branch-and-cut algorithm for the capacitated profitable tour problem
• A Polyhedral Approach to the Asymmetric Traveling Salesman Problem
• A strong flow-based formulation for the shortest path problem in digraphs with negative cycles
• Depth-First Search and Linear Graph Algorithms
• scientific article; zbMATH DE number 1312984 (Why is no real title available?)
• Network flows. Theory, algorithms, and applications.
• The orienteering problem: a survey
• The traveling salesman problem and its variations

Cited in

(7)

• A branch and cut algorithm for the time-dependent profitable tour problem with resource constraints
• MTZ-primal-dual model, cutting-plane, and combinatorial branch-and-bound for shortest paths avoiding negative cycles
• On solving cycle problems with branch-and-cut: extending shrinking and exact subcycle elimination separation algorithms
• Solving elementary shortest-path problems as mixed-integer programs
• An improved formulation for the inventory routing problem with time-varying demands
• Integer programming formulations for the elementary shortest path problem
• scientific article; zbMATH DE number 942499 (Why is no real title available?)

Describes a project that uses

Uses Software

• Boost

This page was built for publication: A note on the separation of subtour elimination constraints in elementary shortest path problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2355890)