Retour aux activités
Séminaire “Un(e) chercheur(-euse) du GERAD vous parle!”

The minimum mean cycle-canceling algorithm for linear programs


29 sept. 2021   11h00 — 12h00

Jacques Desrosiers Professeur titulaire, Département de sciences de la décision, HEC Montréal, Canada

Jacques Desrosiers

Présentation sur YouTube

We present 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 \times n\) linear program, it requires a pseudo-polynomial number \(O(n\Delta)\) of phases, where \(\Delta\) depends on the number of rows and the coefficient matrix.

Keywords: Linear program, residual problem, cycle cancellation, complexity analysis, interior direction.

Olivier Bahn responsable


Montréal Québec