A strong flow-based formulation for the shortest path problem in digraphs with negative cycles

DOI10.1111/j.1475-3995.2008.00681.xzbMath1176.90416OpenAlexW2020990638MaRDI QIDQ3184586

M. S. Ibrahim, Michel Minoux, Nelson F. Maculan

Publication date: 21 October 2009

Published in: International Transactions in Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1111/j.1475-3995.2008.00681.x

zbMATH Keywords

linear programmingshortest pathdigraphs

Mathematics Subject Classification ID

Integer programming (90C10) Linear programming (90C05) Paths and cycles (05C38)

Related Items (9)

Integer programming formulations for the elementary shortest path problem ⋮ Enhanced compact models for the connected subgraph problem and for the shortest path problem in digraphs with negative cycles ⋮ MTZ-primal-dual model, cutting-plane, and combinatorial branch-and-bound for shortest paths avoiding negative cycles ⋮ Solving elementary shortest-path problems as mixed-integer programs ⋮ 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 ⋮ On the shortest path problem with negative cost cycles ⋮ An efficient cutting plane algorithm for the minimum weighted elementary directed cycle problem in planar digraphs ⋮ A note on the separation of subtour elimination constraints in elementary shortest path problems

Uses Software

• GLPK

Cites Work

• A note on two problems in connexion with graphs
• A lower bound for the shortest Hamiltonean path in directed graphs
• A lifting procedure for asymmetric traveling salesman polytope and a large new class of facets
• On a routing problem
• Unnamed Item

This page was built for publication: A strong flow-based formulation for the shortest path problem in digraphs with negative cycles