|
Friday, October 16, 2009 |
|
|
|
|
The master equality polyhedron |
|
|
In this talk, we introduce the master equality polyhedron (MEP), which generalizes
the master polyhedra of Gomory (1969). Gomory introduced the master polyhedron and
the master cyclic group polyhedron as tools to obtain cutting planes for general
integer programming problems, and characterized their "non-trivial polar", i.e.,
the convex hull of inequalities which define their non-trivial facets. We obtain a
similar characterization of the MEP when it is defined by a single
constraint. When the MEP is defined by multiple constraints, a similar
characterization is harder to obtain. Nevertheless, for the two and three
constraint case, we obtain results that allow us to solve the separation problem
over the MEP in polynomial-time. We will discuss these results and their
implications. |