Intersection cuts for nonlinear integer programming: convexification techniques for structured sets

• 成果类型: Article
• 署名作者: Modaresi, Sina; Kilinc, Mustafa R.; Vielma, Juan Pablo
• 署名单位: Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh; Carnegie Mellon University; Massachusetts Institute of Technology (MIT)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-015-0866-5
• 发表日期: 2016
• 页码: 575-611
• 关键词: chvatal-gomory closure; convex hulls; split closure; optimization; relaxations; progress

摘要

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 conic 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.