Optimization Online


On Minimal Valid Inequalities for Mixed Integer Conic Programs

Fatma Kilinc-Karzan (fkilinc***at***andrew.cmu.edu)

Abstract: We study mixed integer 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 study the properties of K-minimal inequalities by establishing necessary conditions for an inequality to be K-minimal. This characterization leads to a broader class of K-sublinear inequalities, which includes K-minimal inequalities as a subclass. We establish a close connection between K-sublinear inequalities and the support functions of sets with certain structure. This leads to practical ways of showing that a given inequality is K-sublinear and K-minimal. We provide examples to show how our framework can be applied. Our framework generalizes the results from the mixed integer linear case, such as the minimal inequalities for mixed integer linear programs are generated by sublinear (positively homogeneous, subadditive and convex) functions that are also piecewise linear. So whenever possible we highlight the connections to the existing literature. However our study reveals that such a cut generating function view is not possible for in the conic case even when the cone involved is the Lorentz cone.

Keywords: Minimal Inequailities; Mixed Integer Conic Programming; Cutting Planes

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

Citation: GSIA Working Paper Number: 2013-E20


Entry Submitted: 06/27/2013
Entry Accepted: 06/27/2013
Entry Last Modified: 05/04/2015

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