Tutte seminar - Ricardo Fukasawa

The master equality polyhedron

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.