Optimization Online


Submodularity in conic quadratic mixed 0-1 optimization

Alper Atamturk(atamturk***at***berkeley.edu)
Andres Gomez(agomez***at***pitt.edu)

Abstract: We describe strong convex valid inequalities for conic quadratic mixed 0-1 optimization. These inequalities can be utilized for solving numerous practical nonlinear discrete optimization problems from value-at-risk minimization to queueing system design, from robust interdiction to assortment optimization through appropriate conic quadratic mixed 0-1 relaxations. The inequalities exploit the submodularity of the binary restrictions and are based on the polymatroid inequalities over binaries for the diagonal case. We prove that the convex inequalities completely describe the convex hull of a single conic quadratic constraint as well as the rotated cone constraint over binary variables and unbounded continuous variables. We then generalize and strengthen the inequalities by incorporating additional constraints of the optimization problem. Computational experiments on mean-risk optimization with correlations, assortment optimization, and robust conic quadratic optimization indicate that the new inequalities strengthen the convex relaxations substantially and lead to significant performance improvements.

Keywords: Polymatroid, submodularity, second-order cone, nonlinear cuts, robust optimization, assortment optimization, value-at-risk, Sharpe ratio

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

Category 2: Integer Programming (Cutting Plane Approaches )

Citation: BCOL Research Report 16.02, IEOR, UC Berkeley

Download: [PDF]

Entry Submitted: 12/30/2018
Entry Accepted: 12/30/2018
Entry Last Modified: 12/30/2018

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