Submodularity in Conic Quadratic Mixed 0–1 Optimization
Alper Atamtürk () and
Andrés Gómez ()
Additional contact information
Alper Atamtürk: Department of Industrial Engineering and Operations Research, University of California, Berkeley, Berkeley, California 94720
Andrés Gómez: Department of Industrial and Systems Engineering, University of Southern California, Los Angeles, California, 90089
Operations Research, 2020, vol. 68, issue 2, 609-630
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; interdiction; Sharpe ratio (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:
Downloads: (external link)
https://doi.org/10.1287/opre.2019.1888 (application/pdf)
Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
HTML/Text
Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:68:y:2020:i:2:p:609-630
Access Statistics for this article
More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().