Groupe d’études et de recherche en analyse des décisions

IPS and Capacitated Minimum Cost Flow Problems

Jean-Bertrand Gauthier HEC Montréal, Canada

The minimum mean cycle (MmC) algorithm belongs to the prized strongly polynomial family of algorithm. The latter has been developed to solve capacitated network problems. We review the theory behind this algorithm in order to make a parallel study with the Improved Primal Simplex (IPS) when it is applied to the same kind of problems. The purpose of this talk is threefold: establish theoretical properties for IPS algorithm, provide some insights about its behavior and develop some acceleration techniques.