Séminaire : Un chercheur du GERAD vous parle!

The minimum mean cycle-canceling algorithm for linear programs

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

Lien pour le webinaire
ID de réunion : 883 6759 0761
Code secret : 615791

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×n

linear program, it requires a pseudo-polynomial number O(nΔ) of phases, where Δ depends on the number of rows and the coefficient matrix.

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