Optimization Online


Polymatroid inequalities for p-order conic mixed 0-1 optimization

Alper Atamturk(atamturk***at***ieor.berkeley.edu)
Andres Gomez(a.gomez***at***ieor.berkeley.edu)

Abstract: We describe new convex valid inequalities for p-order conic mixed-integer optimization, which includes the important second order conic mixed-integer optimization as a special case. The inequalities are based on the polymatroid inequalities over binary variables for the diagonal case. We prove that the proposed inequalities completely describe the convex hull of a single conic constraint over binary variables and unbounded continuous variables. We then generalize and strengthen the inequalities using other constraints of the optimization problem. Computational experiments for second order conic mixed-integer optimization indicate that the new inequalities strengthen the convex relaxations substantially for the diagonal case as well as the general (non-diagonal) case and lead to significant performance improvements.

Keywords: Polymatroids, submodularity, second order cone, nonlinear cuts

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

Citation: BCOL Research Report 16.02, IEOR, UC Berkeley

Download: [PDF]

Entry Submitted: 11/10/2016
Entry Accepted: 11/11/2016
Entry Last Modified: 11/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