MTZ-primal-dual model, cutting-plane, and combinatorial branch-and-bound for shortest paths avoiding negative cycles
From MaRDI portal
Publication:2178342
DOI10.1007/s10479-017-2743-5zbMath1443.90321OpenAlexW2778160562MaRDI QIDQ2178342
Rafael Castro de Andrade, Rommel Dias Saraiva
Publication date: 11 May 2020
Published in: Annals of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10479-017-2743-5
cutting-planecombinatorial branch-and-boundcompact primal-dual modelshortest path in the presence of negative cycles
Cites Work
- 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
- The Floyd-Warshall algorithm on graphs with negative cycles
- Finding all the negative cycles in a directed graph
- Valid inequalities and lifting procedures for the shortest path problem in digraphs with negative cycles
- Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints
- A note on the separation of subtour elimination constraints in elementary shortest path problems
- A zero-space algorithm for negative cost cycle detection in networks
- Tolerance-Based vs. Cost-Based Branching for the Asymmetric Capacitated Vehicle Routing Problem
- An efficient cutting plane algorithm for the minimum weighted elementary directed cycle problem in planar digraphs
- A strong flow-based formulation for the shortest path problem in digraphs with negative cycles
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Integer Programming Formulation of Traveling Salesman Problems
- Improved Algorithms for Detecting Negative Cost Cycles in Undirected Graphs
- On the shortest path problem with negative cost cycles
This page was built for publication: MTZ-primal-dual model, cutting-plane, and combinatorial branch-and-bound for shortest paths avoiding negative cycles
