Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Polyhedral valid inequalities for mixed integer programming

Student-Run Research Seminar

Speaker: Prof. Alper Atamturk, OR & IE UC Berkeley
Location: 593 Kerr
Start time: Wed, May 16 2001, 1:10PM

Gomory cutting planes for mixed integer programs (MIPs) are obtained from individual rows of the simplex tableau of the LP relaxation of MIPs. We study the convex hull of mixed integer knapsack sets as defined by the rows of the simplex tableau. We show that coefficients of Gomory cuts are described by a superadditive approximation of a certain lifting function. We discuss when this approximation is exact and how the exact lifting function is computed. We describe two new classes of cutting planes that dominate Gomory cuts under certain conditions. We conclude with a summary of a computational study on a network design application.