Integer Programming (IP) is the one of the most important and effective modeling paradigms for optimization problems in operations research. Though modern IP solvers can now efficiently solve a large class of IP models, many salient models, in particular those including non-linear constraints and objectives remain intractable.   <?xml:namespace prefix = o />

In this talk, I will survey recent theoretical progress for the class of convex integer programs, i.e. the class of IPs whose continuous relaxation is a general convex program. Convex IPs naturally occur as convexifications of general non-linear programs, and hence are important to study from the perspective of obtaining strong bounds for non-linear problems. Cutting planes, i.e. valid linear inequalities for integer points inside the feasible region, are one of the most useful tools for solving real world IPs. The properties of cutting planes for non-linear IPs however remain poorly understood. In the first part of the talk, I will describe recent results on cutting plane closures for Convex IPs. Firstly, we show that the Chvatal-Gomory closure of any compact convex set is rational polyhedral. This resolves a long standing question of Schrijver for irrational polytopes. Second, we show that the split closure of any strictly convex body is finitely generately, though need not be polyhedral.

In the second part of the talk, I discuss improvements to the computational complexity of the Integer Programming Problem. In the seminal works of Lenstra (MOR `83) and Kannan (MOR `87), it was shown that any n variable Integer Linear Program (ILP) can be solved in time O(n)^{2.5n} (with polynomial dependence on the remaining parameters). In recent work, I give an O(n)^n time algorithm to minimize a convex function over the integer points in any n dimensional convex body. This yields the first exact algorithm for Convex IP and the current fastest algorithm for ILP. The algorithm relies on new insights in the geometry of numbers as well as new techniques for lattice problems. 

Coffee will be served at 3:30pm<?xml:namespace prefix = v /><?xml:namespace prefix = w />