The master equality polyhedron

In this talk, we discuss the master equality polyhedron (MEP) which generalizes the master polyhedra of Gomory (1969). Gomory introduced master polyhedra and master cyclic group polyhedra as tools to obtain cutting planes for general integer programming problems, and characterized their “non-trivial polar”, i.e., the convex hull of inequalities which define non-trivial facets of master polyhedra. When the MEP is defined by a single constraint, a similar characterization of its non-trivial polar was given earlier in Dash, Fukasawa and Gunluk (2008). In this talk we describe slightly weaker results when the MEP is defined by two or three constraints. Our results imply that given an integer program min{cx : Ax = b, x >= 0} defined by up to three constraints, one can solve the separation problem in pseudo-polynomial time simply by solving a linear program. This approach is much simpler than the previously known approach based on Papadimitriou’s (1981) pseudo-polynomial time dynamic programming algorithm to solve integer programs having fixed number of constraints.