Group for Research in Decision Analysis

G-2021-05

The minimum mean cycle-canceling algorithm for linear programs

and

This paper presents the properties of the minimum mean cycle-canceling algorithm for solving linear programming models. Originally designed by Goldberg and Tarjan(1989) 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 (Gauthier et al., 2014) 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 \times n\) linear program, it requires \(O(n\Delta)\) so-called phases, where \(\Delta\) depends on the number of rows and the coefficient matrix. Since each phase comprises at most \(n\) iterations solvable in polynomial time by an interior point algorithm, the overall complexity is pseudo-polynomial.

, 14 pages