Exact quadratic convex reformulations of mixed-integer quadratically constrained problems
From MaRDI portal
This article considers the general mixed integer, quadratically constrained problem in combinatorial optimization and proposes a novel reformulation of the problem into an equivalent quadratic problem with a convex continuous relaxation. The article begins with an overview of the literature and the mathematical formulation of the problem, followed by the presentation of a family of equivalent formulations. This is followed by a method for calculating the best convex equivalent formulation which is then used to find the optimal solution to the problem. The fourth and fifth sections present an extension of the method to the case of equality constraints and the case where some of the variables are continuous, respectively. A large number of computational results are presented where the method is applied to numerous quadratic problems and the performance of the approach is evaluated.
Recommendations
- Convex quadratic mixed-integer problems with quadratic constraints
- scientific article; zbMATH DE number 7152114
- Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems
- A note on convex reformulation schemes for mixed integer quadratic programs
- Extended formulations in mixed integer conic quadratic programming
- scientific article; zbMATH DE number 3920195
- Convex relaxations of non-convex mixed integer quadratically constrained programs: Extended formulations
- Quadratic convex reformulations for quadratic 0-1 programming
- Compact mixed-integer programming formulations in quadratic optimization
- Quadratic convex reformulations for semicontinuous quadratic programming
Cites work
- A branch and cut algorithm for nonconvex quadratically constrained quadratic programming
- A relaxation method for nonconvex quadratically constrained quadratic programs
- A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs
- A simplicial branch-and-bound method for solving nonconvex all-quadratic programs
- Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems
- CSDP, A C library for semidefinite programming
- Deterministic global optimization in nonlinear optimal control problems
- Essays and Surveys in Global Optimization
- Extending the QCR method to general mixed-integer programs
- Global optimization. From theory to implementation.
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Introduction to semidefinite, conic and polynomial optimization
- Linear Reformulations of Integer Quadratic Programs
- Semidefinite relaxations for non-convex quadratic mixed-integer programming
- Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons
Cited in
(40)- A note on solving quadratic programs using mixed-integer programming
- Quadratic convex reformulation for nonconvex binary quadratically constrained quadratic programming via surrogate constraint
- Quadratic convex reformulation for quadratic programming with linear on-off constraints
- Lagrangian decomposition and mixed-integer quadratic programming reformulations for probabilistically constrained quadratic programs
- An efficient compact quadratic convex reformulation for general integer quadratic programs
- Convex reformulation for binary quadratic programming problems via average objective value maximization
- Solving unconstrained 0-1 polynomial programs through quadratic convex reformulation
- Convex quadratic mixed-integer problems with quadratic constraints
- Compact mixed-integer programming formulations in quadratic optimization
- Structured linear reformulation of binary quadratically constrained quadratic programs
- Global solutions of nonconvex standard quadratic programs via mixed integer linear programming reformulations
- A branch and bound algorithm for general mixed-integer quadratic programs based on quadratic convex relaxation
- A note on convex reformulation schemes for mixed integer quadratic programs
- Semidefinite approximation bound for a class of nonhomogeneous nonconvex quadratically constrained quadratic programming problem
- Parametric convex quadratic relaxation of the quadratic knapsack problem
- Representations of quadratic combinatorial optimization problems: a case study using quadratic set covering and quadratic knapsack problems
- Using quadratic convex reformulation to tighten the convex relaxation of a quadratic program with complementarity constraints
- Convex relaxations of non-convex mixed integer quadratically constrained programs: Extended formulations
- Tighter quadratically constrained convex reformulations for semi-continuous quadratic programming
- Comparison of Quadratic Convex Reformulations to Solve the Quadratic Assignment Problem
- A model for clustering data from heterogeneous dissimilarities
- Quadratic 0–1 programming: Tightening linear or quadratic convex reformulation by use of relaxations
- Global solution of non-convex quadratically constrained quadratic programs
- Convex MIQP reformulations for semi-continuous quadratic programming with low price
- Perspective Reformulations of Semicontinuous Quadratically Constrained Quadratic Programs
- A simultaneous diagonalization-based quadratic convex reformulation for nonconvex quadratically constrained quadratic program
- Global optimization algorithm for mixed integer quadratically constrained quadratic program
- scientific article; zbMATH DE number 7152114 (Why is no real title available?)
- Quadratic convex reformulations for semicontinuous quadratic programming
- Using a conic bundle method to accelerate both phases of a quadratic convex reformulation
- Using general triangle inequalities within quadratic convex reformulation method
- A Convex Reformulation and an Outer Approximation for a Large Class of Binary Quadratic Programs
- Convex relaxations of non-convex mixed integer quadratically constrained programs: projected formulations
- Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems
- A tight compact quadratically constrained convex relaxation of the optimal power flow problem
- Extending the QCR method to general mixed-integer programs
- Using quadratic cuts to iteratively strengthen convexifications of box quadratic programs
- New notions of simultaneous diagonalizability of quadratic forms with applications to QCQPs
- Quadratic convex reformulations for a class of complex quadratic programming problems
- Global solution of quadratic problems using interval methods and convex relaxations
This page was built for publication: Exact quadratic convex reformulations of mixed-integer quadratically constrained problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q304240)
