Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Description

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.