Balanced network flows. VI. Polyhedral descriptions
Christian Fremuth‐Paeger, Dieter Jungnickel · Networks · 2001
Abstract 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. © 2001 John Wiley & Sons, Inc.