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