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
- scientific article; zbMATH DE number 1149836 (Why is no real title available?)
- 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 Outer-Inner Approximation for Separable 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
- 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
- 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 Relaxation of Mixed Integer Nonlinear Programs with Indicator Variables
- 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
- 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
(20)- Polyhedral approximation in mixed-integer convex optimization
- Simplex QP-based methods for minimizing a conic quadratic objective over polyhedra
- Lift-and-project cuts for convex mixed integer nonlinear programs
- Fractional 0-1 programs: links between mixed-integer linear and conic quadratic formulations
- Outer approximation and submodular cuts for maximum capture facility location problems with random utilities
- Reformulations for utilizing separability when solving convex MINLP problems
- Exact quadratic convex reformulations of mixed-integer quadratically constrained problems
- scientific article; zbMATH DE number 7370569 (Why is no real title available?)
- extended-MIQCP
- Rational polyhedral outer-approximations of the second-order cone
- Extended formulations in mixed-integer convex programming
- Partially distributed outer approximation
- Exact approaches for competitive facility location with discrete attractiveness
- A combinatorial cut-and-lift procedure with an application to 0-1 second-order conic programming
- Split cuts and extended formulations for mixed integer conic quadratic programming
- Outer approximation with conic certificates for mixed-integer convex problems
- A Scalable Algorithm for Sparse Portfolio Selection
- Convex relaxations of non-convex mixed integer quadratically constrained programs: Extended formulations
- Sparse regression at scale: branch-and-bound rooted in first-order optimization
- JuMP: a modeling language for mathematical optimization
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)
