  


The master equality polyhedron with multiple rows
Sanjeeb Dash(sanjeebdus.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 twoterm 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 subexponential number of terms do not imply validity. In particular, when m = 3, we show that fourterm 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 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  