|
|
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 "non-trivial polar", i.e., the convex hull of inequalities which define non-trivial facets of master polyhedra. When the MEP is defined by a single constraint, we obtain a similar characterization of its non-trivial 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 pseudo-polynomial time simply by solving a linear program. This approach is much simpler than the previously known approach based on Papadimitriou's (1981) pseudo-polynomial 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 co-author of QSopt and of QSopt_ex, an exact linear programming solver.
|
|
|
|