Title: Cutting Planes and Elementary Closures for Non-linear Integer Programming
Speaker: Juan Pablo Vielma, University of Pittsburg
Date: Monday, November 21, 2011 11:00am - 12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
In this talk we discuss theoretical properties of cutting planes for non-linear integer programming and the elementary closures generated by combining all cuts in a given family. We give closed form expression in the original variable space of split cuts for certain classes of conic quadratic representable sets and show that, while the split closure of a strictly convex body is defined by a finite number of split disjunctions, it is not necessarily polyhedral. To contrast this result we also show that Chvatal-Gomory closure of any compact convex set is a rational polytope. In particular this result shows that the Chvatal-Gomory closure of a non-rational polytope is a rational polytope, resolving an open question posed by A. Schrijver in 1980. We finally discuss the implication of these results and present some theoretical and computational open questions related to them.
DIMACS/CCICADA Interdisciplinary Series, Complete Fall Calendar 2011