Polyhedra of regular p-nary group problems

Abstract

The duality for group problems developed in [3] is restricted to p-nary group problems. Results for ternary group problems are obtained similar to those obtained by Fulkerson and Lehman for the binary case. A complete facet description of the group polyhedron is available for a group problem having the Fulkerson property. A group problem has the Fulkerson property if its vertices are the facets of the blocking group problem and if its facets are the vertices of the blocking group problem. The Fulkerson property is a generalization of the max-flow min-cut theorem of Ford and Fulkerson which is interpreted as a statement about the pair of row modules arising from a group problem. We show that a group problem has the Fulkerson property if the corresponding row module is regular. © 1989 The Mathematical Programming Society, Inc.