Jeffrey T. Linderoth, Associate Professor, University of Wisconsin-Madison

Starting from first principles, we give an explicit characterization of the convex hull of the union of a point and a bounded convex set defined by analytic functions. The result can be applied to develop tight formulations of mixed integer nonlinear programs in which the nonlinear functions are separable and convex, and in which variable upper (or lower) bounds play an important role. Frangioni and Gentile (2006) studied the same set and described a class of “perspective cuts” as first-order (outer)-approximations to the convex hull of this set. Our work provides a different perspective on the work of Frangioni and Gentile. Further, we show that for many classes of problems, the convex hull can be expressed via conic quadratic constraints, and thus relaxations can be solved via second-order cone programming. We conclude with computational results on applications that show the power of the reformulation technique.

Joint work with Oktay Gunluk (IBM T.J. Watson Center).