The master equality polyhedron with multiple rows

Sanjeeb Dash(sanjeebdus.ibm.com)
Ricardo Fukasawa(rfukasawus.ibm.com)
Oktay Gunluk(gunlukus.ibm.com)

Abstract: 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.

Keywords: integer programming, master equality polyhedra

Category 1: Integer Programming

Citation: IBM Research Report, February 2009

Download: [PDF]

Entry Submitted: 02/17/2009
Entry Accepted: 02/17/2009
Entry Last Modified: 02/17/2009

Modify/Update this entry