Extended formulations in mixed integer conic quadratic programming
From MaRDI portal
Abstract: In this paper we consider the use of extended formulations in LP-based algorithms for mixed integer conic quadratic programming (MICQP). Extended formulations have been used by Vielma, Ahmed and Nemhauser (2008) and Hijazi, Bonami and Ouorou (2013) to construct algorithms for MICQP that can provide a significant computational advantage. The first approach is based on an extended or lifted polyhedral relaxation of the Lorentz cone by Ben-Tal and Nemirovski (2001) that is extremely economical, but whose approximation quality cannot be iteratively improved. The second is based on a lifted polyhedral relaxation of the euclidean ball that can be constructed using techniques introduced by Tawarmalani and Sahinidis (2005). This relaxation is less economical, but its approximation quality can be iteratively improved. Unfortunately, while the approach of Vielma, Ahmed and Nemhauser is applicable for general MICQP problems, the approach of Hijazi, Bonami and Ouorou can only be used for MICQP problems with convex quadratic constraints. In this paper we show how a homogenization procedure can be combined with the technique by Tawarmalani and Sahinidis to adapt the extended formulation used by Hijazi, Bonami and Ouorou to a class of conic mixed integer programming problems that include general MICQP problems. We then compare the effectiveness of this new extended formulation against traditional and extended formulation-based algorithms for MICQP. We find that this new formulation can be used to improve various LP-based algorithms. In particular, the formulation provides an easy-to-implement procedure that, in our benchmarks, significantly improved the performance of commercial MICQP solvers.
Recommendations
- Extended formulations in mixed-integer convex programming
- Split cuts and extended formulations for mixed integer conic quadratic programming
- Convex relaxations of non-convex mixed integer quadratically constrained programs: projected formulations
- Convex relaxations of non-convex mixed integer quadratically constrained programs: Extended formulations
- A lifted linear programming branch-and-bound algorithm for mixed-integer conic quadratic programs
Cites work
- A branch-and-cut method for 0-1 mixed convex programming
- A computational comparison of reformulations of the perspective relaxation: SOCP vs. cutting planes
- A lifted linear programming branch-and-bound algorithm for mixed-integer conic quadratic programs
- A polyhedral branch-and-cut approach to global optimization
- Algorithm for cardinality-constrained quadratic optimization
- Algorithms and Software for Convex Mixed Integer Nonlinear Programs
- An algorithmic framework for convex mixed integer nonlinear programs
- An improved branch and bound algorithm for mixed integer nonlinear programs
- An outer-approximation algorithm for a class of mixed-integer nonlinear programs
- An Outer-Inner Approximation for Separable Mixed-Integer Nonlinear Programs
- Applications of second-order cone programming
- Benchmarking optimization software with performance profiles.
- Branch and Bound Experiments in Convex Nonlinear Integer Programming
- Computational study of a family of mixed-integer quadratic programming problems
- Computing in operations research using Julia
- Convex programming for disjunctive convex optimization
- FilMINT: an outer approximation-based solver for convex mixed-integer nonlinear programs
- Generalized Benders decomposition
- Generalized convex disjunctive programming: Nonlinear convex hull relaxation
- Heuristics for cardinality constrained portfolio optimization
- scientific article; zbMATH DE number 1149836 (Why is no real title available?)
- Integrating SQP and branch-and-bound for mixed integer nonlinear programming
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- Mixed-integer nonlinear programs featuring ``on/off constraints
- On Polyhedral Approximations of the Second-Order Cone
- On valid inequalities for quadratic programming with continuous variables and binary indicators
- Optimization of cardinality constrained portfolios with a hybrid local search algorithm
- Perspective cuts for a class of convex 0-1 mixed integer programs
- Perspective reformulation and applications
- Perspective reformulations of mixed integer nonlinear programs with indicator variables
- Perspective Relaxation of Mixed Integer Nonlinear Programs with Indicator Variables
- Portfolio optimization with linear and fixed transaction costs
- Projected perspective reformulations with applications in design problems
- Quadratic cone cutting surfaces for quadratic programs with on-off constraints
- SDP diagonalizations and perspective cuts for a class of nonseparable MIQP
- Solving mixed integer nonlinear programs by outer approximation
Cited in
(22)- Lift-and-project cuts for convex mixed integer nonlinear programs
- Outer approximation and submodular cuts for maximum capture facility location problems with random utilities
- Split cuts and extended formulations for mixed integer conic quadratic programming
- Polyhedral approximation in mixed-integer convex optimization
- Rational polyhedral outer-approximations of the second-order cone
- Partially distributed outer approximation
- A combinatorial cut-and-lift procedure with an application to 0-1 second-order conic programming
- Sparse regression at scale: branch-and-bound rooted in first-order optimization
- Outer approximation with conic certificates for mixed-integer convex problems
- Fractional 0-1 programs: links between mixed-integer linear and conic quadratic formulations
- Simplex QP-based methods for minimizing a conic quadratic objective over polyhedra
- Convex relaxations of non-convex mixed integer quadratically constrained programs: Extended formulations
- Exact quadratic convex reformulations of mixed-integer quadratically constrained problems
- Extended formulations in mixed-integer convex programming
- extended-MIQCP
- Sparse and smooth signal estimation: convexification of \(\ell_0\)-formulations
- A Scalable Algorithm for Sparse Portfolio Selection
- JuMP: a modeling language for mathematical optimization
- Sparsity penalized mean-variance portfolio selection: analysis and computation
- Global optimization of mixed-integer nonlinear programs with SCIP 8
- Reformulations for utilizing separability when solving convex MINLP problems
- Exact approaches for competitive facility location with discrete attractiveness
Describes a project that uses
Uses Software
This page was built for publication: Extended formulations in mixed integer conic quadratic programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1688453)
