The master equality polyhedron
Speaker: | Ricardo Fukasawa |
---|---|
Affiliation: | University of Waterloo |
Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
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.
No
previous
knowledge
is
assumed.
This
is
joint
work
with
Sanjeeb
Dash
and
Oktay
Gunluk.