Supermodularity and valid inequalities for quadratic optimization with indicators
From MaRDI portal
Publication:6165587
DOI10.1007/S10107-022-01908-2zbMATH Open1522.90041arXiv2012.14633OpenAlexW3115452290MaRDI QIDQ6165587FDOQ6165587
Authors: Alper Atamtürk, Andrés Gómez 
Publication date: 1 August 2023
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Abstract: We study the minimization of a rank-one quadratic with indicators and show that the underlying set function obtained by projecting out the continuous variables is supermodular. Although supermodular minimization is, in general, difficult, the specific set function for the rank-one quadratic can be minimized in linear time. We show that the convex hull of the epigraph of the quadratic can be obtaining from inequalities for the underlying supermodular set function by lifting them into nonlinear inequalities in the original space of variables. Explicit forms of the convex-hull description are given, both in the original space of variables and in an extended formulation via conic quadratic-representable inequalities, along with a polynomial separation algorithm. Computational experiments indicate that the lifted supermodular inequalities in conic quadratic form are quite effective in reducing the integrality gap for quadratic optimization with indicators.
Full work available at URL: https://arxiv.org/abs/2012.14633
Recommendations
- \(2 \times 2\)-convexifications for convex quadratic optimization with indicator variables
- Submodularity in Conic Quadratic Mixed 0–1 Optimization
- Supermodular covering knapsack polytope
- Lifted polymatroid inequalities for mean-risk optimization with indicator variables
- Strong formulations for quadratic optimization with M-matrices and indicator variables
quadratic optimizationliftingconic quadratic cutsperspective formulationconvex piecewise valid inequalitiessupermodular inequalities
Quadratic programming (90C20) Nonconvex programming, global optimization (90C26) Mixed integer programming (90C11)
Cites Work
- Minotaur: a mixed-integer nonlinear optimization toolkit
- Title not available (Why is that?)
- Applications of second-order cone programming
- The ellipsoid method and its consequences in combinatorial optimization
- Second-order cone programming
- Convex programming for disjunctive convex optimization
- Perspective cuts for a class of convex 0-1 mixed integer programs
- Submodular functions and optimization.
- SDP diagonalizations and perspective cuts for a class of nonseparable MIQP
- A strong conic quadratic reformulation for machine-job assignment with controllable processing times
- A faster strongly polynomial time algorithm for submodular function minimization
- Computational study of a family of mixed-integer quadratic programming problems
- An analysis of approximations for maximizing submodular set functions—I
- A study of the lot-sizing polytope
- Lifting inequalities: a framework for generating strong cuts for nonlinear programs
- On mathematical programming with indicator constraints
- Quadratic convex reformulations for semicontinuous quadratic programming
- Cutting-Planes for Optimization of Convex Functions over Nonconvex Sets
- Valid inequalities for mixed 0-1 programs
- Valid Linear Inequalities for Fixed Charge Problems
- Flow pack facets of the single node fixed-charge flow polytope
- Valid inequalities for problems with additive variable upper bounds
- Mixed-integer nonlinear programs featuring ``on/off constraints
- Perspective reformulations of mixed integer nonlinear programs with indicator variables
- Valid inequalities and separation for capacitated economic lot sizing
- Submodularity and valid inequalities in capacitated fixed charge networks
- Improving the performance of MIQP solvers for quadratic programs with cardinality and minimum threshold constraints: a semidefinite program approach
- Maximizing a class of submodular utility functions with constraints
- Maximizing a class of submodular utility functions
- Title not available (Why is that?)
- A polyhedral approach to bisubmodular function minimization
- Supermodular covering knapsack polytope
- Strong formulations for quadratic optimization with M-matrices and indicator variables
- Submodular functions: from discrete to continuous domains
- Sparse regression at scale: branch-and-bound rooted in first-order optimization
- Scalable algorithms for the sparse ridge regression
- On valid inequalities for quadratic programming with continuous variables and binary indicators
- Deriving convex hulls through lifting and projection
- OR forum: An algorithmic approach to linear regression
- Quadratic cone cutting surfaces for quadratic programs with on-off constraints
- Path cover and path pack inequalities for the capacitated fixed-charge network flow problem
- Polyhedral results for a class of cardinality constrained submodular minimization problems
- Ideal formulations for constrained convex optimization problems with indicator variables
- On the convexification of constrained quadratic optimization problems with indicator variables
- Outlier detection in time series via mixed-integer conic quadratic optimization
- Strong formulations for conic quadratic optimization with indicator variables
- Decompositions of semidefinite matrices and the perspective reformulation of nonseparable quadratic programs
- Submodularity in Conic Quadratic Mixed 0–1 Optimization
- Sequence Independent Lifting for the Set of Submodular Maximization Problem
- Joint chance-constrained programs and the intersection of mixing sets through a submodularity lens
- Submodular function minimization and polarity
Cited In (6)
- Technical Note—Preservation of Supermodularity in Parametric Optimization Problems with Nonlattice Structures
- \(2 \times 2\)-convexifications for convex quadratic optimization with indicator variables
- Outlier detection in time series via mixed-integer conic quadratic optimization
- Strong formulations for quadratic optimization with M-matrices and indicator variables
- Strong valid inequalities for a class of concave submodular minimization problems under cardinality constraints
- On the convex hull of convex quadratic optimization problems with indicators
This page was built for publication: Supermodularity and valid inequalities for quadratic optimization with indicators
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6165587)
