SFU Operations Research Seminar: Angela Morrison

There is a wealth of combinatorial algorithms for classical min-cost flow problems and their simpler variants like max flow or shortest-path problems. It is wellknown that several of these algorithms are intimately related to the Simplex method and the more general circuit augmentation schemes. Prime examples are the network Simplex method, a refinement of the primal Simplex method, and (min-mean) cycle canceling, which corresponds to a (steepest-descent) circuit augmentation scheme over the underlying polyhedron.

We are interested in deepening and expanding the understanding of the close relationship between circuit augmentation and combinatorial network flows algorithms. To this end, we generalize from the consideration of primal or dual feasible flows to the so-called pseudoflows, which allow for a violation of flow balance. We introduce what are called ‘pseudoflow polyhedra’, in which slack variables are used to quantify this violation, and characterize their circuits. This enables us to study various network flows algorithms in view of the walks that they trace in these polyhedra, and in view of the pivot rules used to choose the steps.

In particular, we show that the Successive Shortest Path Algorithm and the Shortest/ Generic Augmenting Path Algorithm form general, non-edge circuit walks. We also provide a proof outline showing that the aforementioned algorithms correspond to a Dantzig Rule and Steepest-ascent circuit augmentation scheme respectively.