The well-known MaxFlow-MinCut theorem asserts that, in a directed graph with a source s, a sink t
and (integer) capacities on the arcs, the maximum amount of (integer) flow equals the minimum capacity
of an st-cut. This min-max result has the desirable property that it still holds when flow requirements
are added on each arc.
In terms of linear systems, the addition of bounds on the arc variables preserves the min-max
theorem. This comes from the combination of integrality properties of the associated linear system
(called total dual integrality) and of the associated polyhedron (called box-total dual integrality). More
precisely, the properties of the linear system yield the min-max theorem, that of the polyhedron allow
the addition of bounds.
In this tutorial, we will mainly focus on the polyhedral part of such min-max results. Box-totally dual
integral polyhedra were introduced in the 80's, and received a renewed interest since around 2008. At a
gentle pace, we will review some of their recent characterizations, which will involve geometrical and
matricial considerations. We will discuss consequences and applications to specific polyhedra, and this
will be accompanied by exercises and open problems.