Premium
Balanced network flows. VI. Polyhedral descriptions
Author(s) -
FremuthPaeger Christian,
Jungnickel Dieter
Publication year - 2001
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.1015
Subject(s) - polytope , mathematics , combinatorics , matching (statistics) , set (abstract data type) , flow network , convex hull , regular polygon , flow (mathematics) , characterization (materials science) , mathematical optimization , discrete mathematics , computer science , geometry , programming language , nanotechnology , statistics , materials science
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.