Balanced network flows. VI. Polyhedral descriptions

This paper discusses the balanced circulation polytope, that is, the convex hull of balanced circulations of a given balanced flow network. The LP description of this polytope is the LP description of ordinary circulations plus some odd-set constraints. The paper starts with an exposition of several classes of odd-set inequalities. These inequalities are described in terms of balanced network flows as well as matchings and put into relation to each other. Step by step, the problem of finding a cost minimum balanced circulation can be reduced to the b-matching problem. We present an LP characterization of the b-matching polytope by blossom inequalities. With a moderate effort, these odd sets are lifted to the setting of balanced-network flows. We finish with the dualization of the derived LP formulation, an introduction of reduced-cost labels, and a corresponding optimality condition.