Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Optimization methods & software

Dynamically generated cutting planes for mixed-integer quadratically constrained quadratic programs and their incorporation into GloMIQO 2

Ruth Misener, James B. Smadbeck, Christodoulos A. Floudas

Published Apr 22, 2014• 48 citations
Publisher

Abstract

The global mixed-integer quadratic optimizer, GloMIQO, addresses mixed-integer quadratically constrained quadratic programs (MIQCQP) to ε-global optimality. This paper documents the branch-and-cut framework integrated into GloMIQO 2. Cutting planes are derived from reformulation–linearization technique equations, convex multivariable terms, αBB convexifications, and low- and high-dimensional edge-concave aggregations. Cuts are based on both individual equations and collections of nonlinear terms in MIQCQP. Novel contributions of this paper include: development of a corollary to Crama's [Concave extensions for nonlinear 0-1 maximization problems, Math. Program. 61 (1993), pp. 53–60] necessary and sufficient condition for the existence of a cut dominating the termwise relaxation of a bilinear expression; algorithmic descriptions for deriving each class of cut; presentation of a branch-and-cut framework integrating the cuts. Computational results are presented along with comparison of the GloMIQO 2 performance to several state-of-the-art solvers.

DOI
10.1080/10556788.2014.916287

Related papers

On partial convexification cuts for mixed-integer quadratic programs with 0-1 indicators

Rui Ma, Renaud Chicoisne, Pierre Latouche

This paper studies mixed-integer quadratic programming (MIQP) problems with 0--1 indicator constraints.We propose two cut-generation algorithms under three reformulation schemes, which can be seamlessly embedded into a branch-and-bound framework.The algorithms are based on a partial convexification strategy applied to selected subsets of variables, enabling the efficient generation of both quadratic and linear cuts.We provide theoretical insights by characterizing the generated cuts as deepest cuts and by comparing quadratic cuts with their linear counterparts in different variable spaces, thereby bridging convexification theory and practical MIQP solution methods.Furthermore, we develop three practical strengthening techniques that exploit structural properties of the quadratic terms.Extensive computational experiments demonstrate that the proposed cut-generation algorithms meaningfully improve solver performance by accelerating convergence to optimal solutions.

•Jan 20, 2026•0 citations

Global solution of non-convex quadratically constrained quadratic programs

Sourour Elloumi, Amélie Lambert

The class of mixed-integer quadratically constrained quadratic programs (QCQP) consists of minimizing a quadratic function under quadratic constraints where the variables could be integer or continuous. On a previous paper we introduced a method called MIQCR for solving QCQPs with the following restriction: all quadratic sub-functions of purely continuous variables are already convex. In this paper, we propose an extension of MIQCR which applies to any QCQP. Let (P) be a QCQP. Our approach to solve (P) is first to build an equivalent mixed-integer quadratic problem (P∗). This equivalent problem (P∗) has a quadratic convex objective function, linear constraints, and additional variables y that are meant to satisfy the additional quadratic constraints y=xxT, where x are the initial variables of problem (P). We then propose to solve (P∗) by a branch-and-bound algorithm based on the relaxation of the additional quadratic constraints and of the integrality constraints. This type of branching is known as spatial branch-and-bound. Computational experiences are carried out on a total of 325 instances. The results show that the solution time of most of the considered instances is improved by our method in comparison with the recent implementation of QuadProgBB, and with the solvers Cplex, Couenne, Scip, BARON and GloMIQO.

Optimization methods & software•Jul 28, 2017•25 citations

Enhancements of discretization approaches for non-convex mixed-integer quadratically constrained quadratic programming: Part I

Benjamin Beach, Robert Burlacu, Andreas Bärmann +2 more

Abstract We study mixed-integer programming (MIP) relaxation techniques for the solution of non-convex mixed-integer quadratically constrained quadratic programs (MIQCQPs). We present MIP relaxation methods for non-convex continuous variable products. In this paper, we consider MIP relaxations based on separable reformulation. The main focus is the introduction of the enhanced separable MIP relaxation for non-convex quadratic products of the form $$z=xy$$ z = x y , called hybrid separable (HybS). Additionally, we introduce a logarithmic MIP relaxation for univariate quadratic terms, called sawtooth relaxation , based on Beach (Beach in J Glob Optim 84:869–912, 2022). We combine the latter with HybS and existing separable reformulations to derive MIP relaxations of MIQCQPs. We provide a comprehensive theoretical analysis of these techniques, underlining the theoretical advantages of HybS compared to its predecessors. We perform a broad computational study to demonstrate the effectiveness of the enhanced MIP relaxation in terms of producing tight dual bounds for MIQCQPs. In Part II, we study MIP relaxations that extend the MIP relaxation normalized multiparametric disaggregation technique (NMDT) (Castro in J Glob Optim 64:765–784, 2015) and present a computational study which also includes the MIP relaxations from this work and compares them with a state-of-the-art of MIQCQP solvers.

Computational Optimization and Applications•Jan 30, 2024•5 citations

Enhancements of Discretization Approaches for Non-Convex Mixed-Integer Quadratically Constraint Quadratic Programming: Part I

Benjamin Beach, Robert Burlacu, Andreas Bärmann +2 more

We study mixed-integer programming (MIP) relaxation techniques for the solution of non convex mixed-integer quadratically constrained quadratic programs (MIQCQPs). We present MIP relaxation methods for non convex continuous variable products. In Part I, we consider MIP relaxations based on separable reformulation. The main focus is the introduction of the enhanced separable MIP relaxation for nonconvex quadratic products of the form z=xy, called hybrid separable (HybS). Additionally, we introduce a logarithmic MIP relaxation for univariate quadratic terms, called sawtooth relaxation. We combine the latter with HybS and existing separable reformulations to derive MIP relaxations of MIQCQPs. We provide a comprehensive theoretical analysis of these techniques, underlining the theoretical advantages of HybS compared to its predecessors. We perform a broad computational study to demonstrate the effectiveness of the enhanced MIP relaxation in terms of producing tight dual bounds for MIQCQPs. In Part II, we study MIP relaxations that extend the well-known MIP relaxation normalized multiparametric disaggregation technique (NMDT) and present further theoretical and computational analyses.

arXiv:2211.00876•Nov 2, 2022•0 citations

Enhancements of discretization approaches for non-convex mixed-integer quadratically constrained quadratic programming: part II

Benjamin Beach, Robert Burlacu, Andreas Bärmann +2 more

Abstract This is Part II of a study on mixed-integer programming (MIP) relaxation techniques for the solution of non-convex mixed-integer quadratically constrained quadratic programs (MIQCQPs). We set the focus on MIP relaxation methods for non-convex continuous variable products where both variables are bounded and extend the well-known MIP relaxation normalized multiparametric disaggregation technique(NMDT), applying a sophisticated discretization to both variables. We refer to this approach as doubly discretized normalized multiparametric disaggregation technique (D-NMDT). In a comprehensive theoretical analysis, we underline the theoretical advantages of the enhanced method D-NMDT compared to NMDT. Furthermore, we perform a broad computational study to demonstrate its effectiveness in terms of producing tight dual bounds for MIQCQPs. Finally, we compare D-NMDT to the separable MIP relaxations from Part I and a state-of-the-art MIQCQP solver.

Computational Optimization and Applications•Mar 18, 2024•0 citations

A convex reformulation and an outer approximation for a class of binary quadratic program

Borzou Rostami, Fausto Errico, Andrea Lodi

In this paper, we propose a general modeling framework for a large class of binary quadratic programs subject to variable partitioning constraints.This problem has a wide range of applications as many of the binary quadratic programs with linear constraints can be represented in this form.By exploiting the problems' structure, we propose mixed-integer nonlinear program (MINLP) and mixed-integer linear program (MILP) reformulations and show the relationship between the two models in terms of the relaxation strength.Our methodology relies on a convex reformulation of the proposed MINLP and a branch-and-cut algorithm based on outer approximation cuts where the cuts are generated on the fly by efficiently solving separation subproblems.Our experimental results on various quadratic combinatorial optimization problems show that our approach outperforms the state-of-the-art solver applied to different MILP reformulations of the corresponding problems.

•Jan 1, 2018•4 citations
The global mixed-integer quadratic optimizer, GloMIQO, addresses mixed-integer quadratically constrained quadratic programs (MIQCQP) to ε-global optimality. This paper documents the branch-and-cut framework integrated into GloMIQO 2. Cutting planes are derived from reformulation–linearization technique equations, convex multivariable terms, αBB convexifications, and low- and high-dimensional edge-concave aggregations. Cuts are based on both individual equations and collections of nonlinear terms in MIQCQP. Novel contributions of this paper include: development of a corollary to Crama's [Concave extensions for nonlinear 0-1 maximization problems, Math. Program. 61 (1993), pp. 53–60] necessary and sufficient condition for the existence of a cut dominating the termwise relaxation of a bilinear expression; algorithmic descriptions for deriving each class of cut; presentation of a branch-and-cut framework integrating the cuts. Computational results are presented along with comparison of the GloMIQO 2 performance to several state-of-the-art solvers.
This paper studies mixed-integer quadratic programming (MIQP) problems with 0--1 indicator constraints.We propose two cut-generation algorithms under three reformulation schemes, which can be seamlessly embedded into a branch-and-bound framework.The algorithms are based on a partial convexification strategy applied to selected subsets of variables, enabling the efficient generation of both quadratic and linear cuts.We provide theoretical insights by characterizing the generated cuts as deepest cuts and by comparing quadratic cuts with their linear counterparts in different variable spaces, thereby bridging convexification theory and practical MIQP solution methods.Furthermore, we develop three practical strengthening techniques that exploit structural properties of the quadratic terms.Extensive computational experiments demonstrate that the proposed cut-generation algorithms meaningfully improve solver performance by accelerating convergence to optimal solutions.
The class of mixed-integer quadratically constrained quadratic programs (QCQP) consists of minimizing a quadratic function under quadratic constraints where the variables could be integer or continuous. On a previous paper we introduced a method called MIQCR for solving QCQPs with the following restriction: all quadratic sub-functions of purely continuous variables are already convex. In this paper, we propose an extension of MIQCR which applies to any QCQP. Let (P) be a QCQP. Our approach to solve (P) is first to build an equivalent mixed-integer quadratic problem (P∗). This equivalent problem (P∗) has a quadratic convex objective function, linear constraints, and additional variables y that are meant to satisfy the additional quadratic constraints y=xxT, where x are the initial variables of problem (P). We then propose to solve (P∗) by a branch-and-bound algorithm based on the relaxation of the additional quadratic constraints and of the integrality constraints. This type of branching is known as spatial branch-and-bound. Computational experiences are carried out on a total of 325 instances. The results show that the solution time of most of the considered instances is improved by our method in comparison with the recent implementation of QuadProgBB, and with the solvers Cplex, Couenne, Scip, BARON and GloMIQO.
Abstract We study mixed-integer programming (MIP) relaxation techniques for the solution of non-convex mixed-integer quadratically constrained quadratic programs (MIQCQPs). We present MIP relaxation methods for non-convex continuous variable products. In this paper, we consider MIP relaxations based on separable reformulation. The main focus is the introduction of the enhanced separable MIP relaxation for non-convex quadratic products of the form z=xyz=xyz=xy z = x y , called hybrid separable (HybS). Additionally, we introduce a logarithmic MIP relaxation for univariate quadratic terms, called sawtooth relaxation , based on Beach (Beach in J Glob Optim 84:869–912, 2022). We combine the latter with HybS and existing separable reformulations to derive MIP relaxations of MIQCQPs. We provide a comprehensive theoretical analysis of these techniques, underlining the theoretical advantages of HybS compared to its predecessors. We perform a broad computational study to demonstrate the effectiveness of the enhanced MIP relaxation in terms of producing tight dual bounds for MIQCQPs. In Part II, we study MIP relaxations that extend the MIP relaxation normalized multiparametric disaggregation technique (NMDT) (Castro in J Glob Optim 64:765–784, 2015) and present a computational study which also includes the MIP relaxations from this work and compares them with a state-of-the-art of MIQCQP solvers.
We study mixed-integer programming (MIP) relaxation techniques for the solution of non convex mixed-integer quadratically constrained quadratic programs (MIQCQPs). We present MIP relaxation methods for non convex continuous variable products. In Part I, we consider MIP relaxations based on separable reformulation. The main focus is the introduction of the enhanced separable MIP relaxation for nonconvex quadratic products of the form z=xy, called hybrid separable (HybS). Additionally, we introduce a logarithmic MIP relaxation for univariate quadratic terms, called sawtooth relaxation. We combine the latter with HybS and existing separable reformulations to derive MIP relaxations of MIQCQPs. We provide a comprehensive theoretical analysis of these techniques, underlining the theoretical advantages of HybS compared to its predecessors. We perform a broad computational study to demonstrate the effectiveness of the enhanced MIP relaxation in terms of producing tight dual bounds for MIQCQPs. In Part II, we study MIP relaxations that extend the well-known MIP relaxation normalized multiparametric disaggregation technique (NMDT) and present further theoretical and computational analyses.
Abstract This is Part II of a study on mixed-integer programming (MIP) relaxation techniques for the solution of non-convex mixed-integer quadratically constrained quadratic programs (MIQCQPs). We set the focus on MIP relaxation methods for non-convex continuous variable products where both variables are bounded and extend the well-known MIP relaxation normalized multiparametric disaggregation technique(NMDT), applying a sophisticated discretization to both variables. We refer to this approach as doubly discretized normalized multiparametric disaggregation technique (D-NMDT). In a comprehensive theoretical analysis, we underline the theoretical advantages of the enhanced method D-NMDT compared to NMDT. Furthermore, we perform a broad computational study to demonstrate its effectiveness in terms of producing tight dual bounds for MIQCQPs. Finally, we compare D-NMDT to the separable MIP relaxations from Part I and a state-of-the-art MIQCQP solver.
In this paper, we propose a general modeling framework for a large class of binary quadratic programs subject to variable partitioning constraints.This problem has a wide range of applications as many of the binary quadratic programs with linear constraints can be represented in this form.By exploiting the problems' structure, we propose mixed-integer nonlinear program (MINLP) and mixed-integer linear program (MILP) reformulations and show the relationship between the two models in terms of the relaxation strength.Our methodology relies on a convex reformulation of the proposed MINLP and a branch-and-cut algorithm based on outer approximation cuts where the cuts are generated on the fly by efficiently solving separation subproblems.Our experimental results on various quadratic combinatorial optimization problems show that our approach outperforms the state-of-the-art solver applied to different MILP reformulations of the corresponding problems.