We study the Master Equality Polyhedron (MEP) which generalizes the Master Cyclic Group Polyhedron and the Master Knapsack Polyhedron.
We present an explicit characterization of the polar of the nontrivial facet-defining inequalities for the MEP. This result generalizes similar results for the Master Cyclic Group Polyhedron by Gomory [9] and for the Master Knapsack Polyhedron by Araoz [1]. Furthermore, this characterization also gives a polynomial time algorithm for separating an arbitrary point from the MEP.
We describe how facet defining inequalities for the Master Cyclic Group Polyhedron can be lifted to obtain facet defining inequalities for the MEP, and also present facet defining inequalities for the MEP that cannot be obtained in such a way. Finally, we study the mixed-integer extension of the MEP and present an interpolation theorem that produces valid inequalities for general mixed integer programming problems using facets of the MEP.
By: Sanjeeb Dash; Ricardo Fukasawa; Oktay Gunluk
Published in: RC24201 in 2007
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .