2013/02/11 by Sina Modaresi, Modaresi, Sina, Mustafa R. Kılınç +3 · 1 citation
Mathematics · #FOS: Mathematics #Optimization and Control (math.OC) #math.OC
paper · pdf · doi:10.48550/arxiv.1302.2556
arxiv created 2014/06/11 · arxiv updated 2014/06/12
We study the generalization of split, k-branch split, and intersection cuts from Mixed Integer Linear Programming to the realm of Mixed Integer Nonlinear Programming. Constructing such cuts requires calculating the convex hull of the difference between a convex set and an open set with a simple geometric structure. We introduce two techniques to give precise characterizations of such convex hulls and use them to construct split, k-branch split, and intersection cuts for several classes of non-polyhedral sets. In particular, we give simple formulas for split cuts for essentially all convex sets described by a single quadratic inequality. We also give simple formulas for k-branch split cuts and some general intersection cuts for a wide variety of convex quadratic sets.