6533b86cfe1ef96bd12c89ff
RESEARCH PRODUCT
The minimum mean cycle-canceling algorithm for linear programs
Jacques DesrosiersJean Bertrand GauthierJean Bertrand Gauthiersubject
021103 operations researchInformation Systems and ManagementGeneral Computer ScienceLinear programmingDegenerate energy levels0211 other engineering and technologiesPhase (waves)0102 computer and information sciences02 engineering and technologyManagement Science and Operations ResearchResidualFlow network01 natural sciencesIndustrial and Manufacturing EngineeringDual (category theory)010201 computation theory & mathematicsModeling and SimulationCoefficient matrixRowAlgorithmMathematicsdescription
Abstract This paper presents the properties of the minimum mean cycle-canceling algorithm for solving linear programming models. Originally designed for solving network flow problems for which it runs in strongly polynomial time, most of its properties are preserved. This is at the price of adapting the fundamental decomposition theorem of a network flow solution together with various definitions: that of a cycle and the way to calculate its cost, the residual problem, and the improvement factor at the end of a phase. We also use the primal and dual necessary and sufficient optimality conditions stated on the residual problem for establishing the pricing step giving its name to the algorithm. It turns out that the successive solutions need not be basic, there are no degenerate pivots, and the improving directions are potentially interior in addition to those on edges. For solving an m × n linear program, it requires a pseudo-polynomial number O ( n Δ ) of so-called phases, where Δ depends on the number of rows and the coefficient matrix.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2022-04-01 | European Journal of Operational Research |