Optimization Online


Two-Term Disjunctions on the Second-Order Cone

Fatma Kilinc Karzan (fkilinc***at***andrew.cmu.edu)
Sercan Yildiz (syildiz***at***andrew.cmu.edu)

Abstract: Balas introduced disjunctive cuts in the 1970s for mixed-integer linear programs. Several recent papers have attempted to extend this work to mixed-integer conic programs. In this paper we study the structure of the convex hull of a two-term disjunction applied to the second-order cone, and develop a methodology to derive closed-form expressions for convex inequalities describing the resulting convex hull. Our approach is based on first characterizing the structure of undominated valid linear inequalities for the disjunction and then using conic duality to derive a family of convex, possibly nonlinear, valid inequalities that correspond to these linear inequalities. We identify and study the cases where these valid inequalities can equivalently be expressed in conic quadratic form and where a single inequality from this family is sufficient to describe the convex hull. In particular, our results on two-term disjunctions on the second-order cone generalize related results on split cuts by Modaresi, Kilinc, and Vielma, and by Andersen and Jensen.

Keywords: Mixed-integer conic programming, second-order cone programming, cutting planes, disjunctive cuts

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

Category 2: Linear, Cone and Semidefinite Programming (Second-Order Cone Programming )

Citation: Carnegie Mellon University, April 2014

Download: [PDF]

Entry Submitted: 04/30/2014
Entry Accepted: 04/30/2014
Entry Last Modified: 03/10/2016

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