The minimum mean cycle-canceling algorithm for linear programs

DOI10.1016/j.ejor.2021.09.022zbMath1490.90194OpenAlexW3202776709MaRDI QIDQ2076908

Jean Bertrand Gauthier, Jacques Desrosiers

Publication date: 22 February 2022

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

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

zbMATH Keywords

linear programcomplexity analysiscycle cancellationinterior directionresidual problem

Mathematics Subject Classification ID

Linear programming (90C05) Extreme-point and pivoting methods (90C49)

Related Items (1)

On circuit diameter bounds via circuit imbalances

Cites Work

• Unnamed Item
• Unnamed Item
• About the minimum mean cycle-canceling algorithm
• Influence of the normalization constraint on the integral simplex using decomposition
• A new polynomial-time algorithm for linear programming
• A characterization of the minimum cycle mean in a digraph
• Tight bounds on the number of minimum-mean cycle cancellations and related results
• A strongly polynomial contraction-expansion algorithm for network flow problems
• Linear fractional approximations for master problems in column generation
• Decomposition theorems for linear programs
• Steepest-edge simplex algorithms for linear programming
• An Improved Primal Simplex Algorithm for Degenerate Linear Programs
• Finding minimum-cost circulations by canceling negative cycles
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Linear Programming
• Vector Space Decomposition for Solving Large-Scale Linear Programs
• Automation and Combination of Linear-Programming Based Stabilization Techniques in Column Generation
• Dynamic Aggregation of Set-Partitioning Constraints in Column Generation
• Programming with linear fractional functionals

This page was built for publication: The minimum mean cycle-canceling algorithm for linear programs