
Discrete Mathematics and Optimization Seminar

Mar. 16th, 2009
The master equality polyhedron
Sanjeeb Dash
IBM

Abstract:
In this talk, we introduce the master equality polyhedron (MEP), which generalizes the master polyhedra of Gomory (1969). Gomory introduced master polyhedra and master cyclic group polyhedra as tools to obtain cutting planes for general integer programming problems, and characterized their "nontrivial polar", i.e., the convex hull of inequalities which define nontrivial facets of master polyhedra. When the MEP is defined by a single constraint, we obtain a similar characterization of its nontrivial polar, and obtain slightly weaker results when the MEP is defined by two or three constraints. Our results imply that given an integer program min{cx : Ax = b, x >= 0} defined by up to three constraints, one can solve the separation problem in pseudopolynomial time simply by solving a linear program. This approach is much simpler than the previously known approach based on Papadimitriou's (1981) pseudopolynomial time dynamic programming algorithm to solve integer programs having fixed number of constraints.
Bio:
Sanjeeb Dash is a Research Staff Member at the Mathematical Sciences Department of the IBM T. J. Watson Research Center. In recent years, his research has centered on various aspects of cutting planes for general integer programming problems, including their complexity and numerical implementation. He is also interested in linear programming solvers, and is a coauthor of QSopt and of QSopt_ex, an exact linear programming solver.



