  


Intersection Cuts for Nonlinear Integer Programming: Convexification Techniques for Structured Sets
Sina Modaresi (sim23pitt.edu) Abstract: We study the generalization of split, kbranch 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, kbranch split, and intersection cuts for several classes of nonpolyhedral 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 kbranch split cuts and some general intersection cuts for a wide variety of convex quadratic sets. Keywords: Split Cuts; Intersection Cuts; MINLP Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming ) Citation: Download: [PDF] Entry Submitted: 02/11/2013 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  