MTZ-primal-dual model, cutting-plane, and combinatorial branch-and-bound for shortest paths avoiding negative cycles

Recommendations

On the shortest path problem with negative cost cycles
Valid inequalities and lifting procedures for the shortest path problem in digraphs with negative cycles
scientific article; zbMATH DE number 536593
Enhanced compact models for the connected subgraph problem and for the shortest path problem in digraphs with negative cycles
A strong flow-based formulation for the shortest path problem in digraphs with negative cycles
On a parametric shortest path problem from primal—dual multicommodity network optimization
Relaxed most negative cycle and most positive cut canceling algorithms for minimum cost flow
ON SOLVING SHORTEST PATHS WITH A LEAST-SQUARES PRIMAL-DUAL ALGORITHM
Randomized algorithms for finding the shortest negative cost cycle in networks
Multi-objective and multi-constrained non-additive shortest path problems

Cites work

A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
A note on the separation of subtour elimination constraints in elementary shortest path problems
A strong flow-based formulation for the shortest path problem in digraphs with negative cycles
A zero-space algorithm for negative cost cycle detection in networks
An efficient cutting plane algorithm for the minimum weighted elementary directed cycle problem in planar digraphs
Enhanced compact models for the connected subgraph problem and for the shortest path problem in digraphs with negative cycles
Finding all the negative cycles in a directed graph
Improved Algorithms for Detecting Negative Cost Cycles in Undirected Graphs
Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints
Integer Programming Formulation of Traveling Salesman Problems
Integer programming formulations for the elementary shortest path problem
On the shortest path problem with negative cost cycles
The Floyd-Warshall algorithm on graphs with negative cycles
Tolerance-based vs. cost-based branching for the asymmetric capacitated vehicle routing problem
Valid inequalities and lifting procedures for the shortest path problem in digraphs with negative cycles

Cited in

(6)

Arc-dependent networks: theoretical insights and a computational study
On finding shortest paths in arc-dependent networks
A strong flow-based formulation for the shortest path problem in digraphs with negative cycles
On the analysis of optimization problems in arc-dependent networks
scientific article; zbMATH DE number 536593 (Why is no real title available?)
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

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