Supermodularity and valid inequalities for quadratic optimization with indicators
From MaRDI portal
(Redirected from Publication:6165587)
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.
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
Cites work
- A faster strongly polynomial time algorithm for submodular function minimization
- A polyhedral approach to bisubmodular function minimization
- A strong conic quadratic reformulation for machine-job assignment with controllable processing times
- A study of the lot-sizing polytope
- An analysis of approximations for maximizing submodular set functions—I
- Applications of second-order cone programming
- Computational study of a family of mixed-integer quadratic programming problems
- Convex programming for disjunctive convex optimization
- Cutting-Planes for Optimization of Convex Functions over Nonconvex Sets
- Decompositions of semidefinite matrices and the perspective reformulation of nonseparable quadratic programs
- Deriving convex hulls through lifting and projection
- Flow pack facets of the single node fixed-charge flow polytope
- scientific article; zbMATH DE number 193411 (Why is no real title available?)
- Ideal formulations for constrained convex optimization problems with indicator variables
- Improving the performance of MIQP solvers for quadratic programs with cardinality and minimum threshold constraints: a semidefinite program approach
- Joint chance-constrained programs and the intersection of mixing sets through a submodularity lens
- Lifting inequalities: a framework for generating strong cuts for nonlinear programs
- Maximizing a class of submodular utility functions
- Maximizing a class of submodular utility functions with constraints
- Minotaur: a mixed-integer nonlinear optimization toolkit
- Mixed-integer nonlinear programs featuring ``on/off constraints
- On mathematical programming with indicator constraints
- On the convexification of constrained quadratic optimization problems with indicator variables
- On valid inequalities for quadratic programming with continuous variables and binary indicators
- OR forum: An algorithmic approach to linear regression
- Outlier detection in time series via mixed-integer conic quadratic optimization
- Path cover and path pack inequalities for the capacitated fixed-charge network flow problem
- Perspective cuts for a class of convex 0-1 mixed integer programs
- Perspective reformulations of mixed integer nonlinear programs with indicator variables
- Polyhedral results for a class of cardinality constrained submodular minimization problems
- Quadratic cone cutting surfaces for quadratic programs with on-off constraints
- Quadratic convex reformulations for semicontinuous quadratic programming
- Scalable algorithms for the sparse ridge regression
- SDP diagonalizations and perspective cuts for a class of nonseparable MIQP
- Second-order cone programming
- Sequence Independent Lifting for the Set of Submodular Maximization Problem
- Sparse and smooth signal estimation: convexification of \(\ell_0\)-formulations
- Sparse regression at scale: branch-and-bound rooted in first-order optimization
- Strong formulations for conic quadratic optimization with indicator variables
- Strong formulations for quadratic optimization with M-matrices and indicator variables
- Submodular function minimization and polarity
- Submodular functions and optimization.
- Submodular functions: from discrete to continuous domains
- Submodularity and valid inequalities in capacitated fixed charge networks
- Submodularity in Conic Quadratic Mixed 0–1 Optimization
- Supermodular covering knapsack polytope
- The ellipsoid method and its consequences in combinatorial optimization
- Valid inequalities and separation for capacitated economic lot sizing
- Valid inequalities for mixed 0-1 programs
- Valid inequalities for problems with additive variable upper bounds
- Valid Linear Inequalities for Fixed Charge Problems
Cited in
(7)- Strong formulations for quadratic optimization with M-matrices and indicator variables
- Outlier detection in time series via mixed-integer conic quadratic optimization
- Technical Note—Preservation of Supermodularity in Parametric Optimization Problems with Nonlattice Structures
- \(2 \times 2\)-convexifications for convex quadratic optimization with 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
- Cutting planes for signomial programming
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)
