On Minimal Valid Inequalities for Mixed Integer Conic Programs

• 成果类型: Article
• 署名作者: Kilinc-Karzan, Fatma
• 署名单位: Carnegie Mellon University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2015.0737
• 发表日期: 2016
• 页码: 477-510
• 关键词: lmi description; optimization; cuts; algorithm

摘要

We study disjunctive conic sets involving a general regular (closed, convex, full dimensional, and pointed) cone K such as the nonnegative orthant, the Lorentz cone, or the positive semidefinite cone. In a unified framework, we introduce K-minimal inequalities and show that, under mild assumptions, these inequalities together with the trivial cone-implied inequalities are sufficient to describe the convex hull. We focus on the properties of K-minimal inequalities by establishing algebraic necessary conditions for an inequality to be K-minimal. This characterization leads to a broader algebraically defined class of K-sublinear inequalities. We demonstrate a close connection between K-sublinear inequalities and the support functions of convex sets with a particular structure. This connection results in practical ways of verifying K-sublinearity and/or K-minimality of inequalities. Our study generalizes some of the results from the mixed integer linear case. It is well known that the minimal inequalities for mixed integer linear programs are generated by sublinear (positively homogeneous, subadditive, and convex) functions that are also piecewise linear. Our analysis easily recovers this result. However, in the case of general regular cones other than the nonnegative orthant, our study reveals that such a cut-generating function view, which treats the data associated with each individual variable independently, is far from sufficient.