Optimization Online


Intersection Cuts for Nonlinear Integer Programming: Convexification Techniques for Structured Sets

Sina Modaresi (sim23***at***pitt.edu)
Mustafa Kilinc (mrk46***at***pitt.edu)
Juan Pablo Vielma (jvielma***at***mit.edu)

Abstract: 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.

Keywords: Split Cuts; Intersection Cuts; MINLP

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )


Download: [PDF]

Entry Submitted: 02/11/2013
Entry Accepted: 02/11/2013
Entry Last Modified: 06/11/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society