The Master Equality Polyhedron with Multiple Rows

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 defines 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 defined by m > 1 rows. We define the notion of a polaroid, a set containing all nontrivial facet defining 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 defined 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.