Optimization Online


A conic representation of the convex hull of disjunctive sets and conic cuts for integer second order cone optimization

Pietro Belotti (petr.7b6***at***gmail.com)
Julio C. Goez (jgoez***at***hotmail.com)
Imre Polik (imre***at***polik.net )
Ted K. Ralphs (ted***at***lehigh.edu )
Tamas Terlaky (terlaky***at***lehigh.edu )

Abstract: We study the convex hull of the intersection of a convex set E and a linear disjunction. This intersection is at the core of solution techniques for Mixed Integer Conic Optimization. We prove that if there exists a cone K (resp., a cylinder C) that has the same intersection with the boundary of the disjunction as E, then the convex hull is the intersection of E with K (resp., C). The existence of such a cone (resp., a cylinder) is difficult to prove for general conic optimization. We prove existence and unicity of a second order cone (resp., a cylinder), when E is the intersection of an affine space and a second order cone (resp., a cylinder). We also provide a method for finding that cone, and hence the convex hull, for the continuous relaxation of the feasible set of a Mixed Integer Second Order Cone Optimization (MISOCO) problem, assumed to be the intersection of an ellipsoid with a general linear disjunction. This cone provides a new conic cut for MISOCO that can be used in branch-and-cut algorithms for MISOCO problems.

Keywords: Integer Optimization, Conic Optimization, Second Order Cone Optimization

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

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


Download: [PDF]

Entry Submitted: 06/03/2012
Entry Accepted: 06/03/2012
Entry Last Modified: 10/30/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