The master equality polyhedron (MEP) is a canonical set that generalizes the Master Cyclic Group Polyhedron (MCGP) of Gomory. We recently characterized a nontrivial polar for the MEP, i.e., a polyhedron T such that an inequality denotes a nontrivial facet of the MEP if and only if its coefficient vector forms a vertex of T. In this paper we study the MEP when it is denoted by m > 1 rows. We denote the notion of a polaroid, a set containing all nontrivial facet denoting inequalities. We show how to use linear programming to efficiently solve the separation problem for the MEP when the polaroid has a compact polyhedral description, and obtain such descriptions via subadditivity conditions when m = 2 or m = 3. For the MCGP and the MEP denoted by a single constraint, the notions of two-term subadditivity and valid inequalities for MEP are essentially equivalent. We show this is not true in the case of the MEP when m >= 3; In fact, we prove that subadditivity conditions with a sub-exponential number of terms do not imply validity. In particular, when m = 3, we show that four-term subadditivity conditions are necessary and sufficient for validity.
Citation
IBM Research Report, February 2009