Optimization Online


The master equality polyhedron with multiple rows

Sanjeeb Dash(sanjeebd***at***us.ibm.com)
Ricardo Fukasawa(rfukasaw***at***us.ibm.com)
Oktay Gunluk(gunluk***at***us.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society