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

INFORMS journal on computing

Decision Diagram Decomposition for Quadratically Constrained Binary Optimization

David Bergman, Leonardo Lozano

Published Aug 14, 2020• 10 citations
Publisher

Abstract

In recent years the use of decision diagrams within the context of discrete optimization has proliferated. This paper continues this expansion by proposing the use of decision diagrams for modeling and solving binary optimization problems with quadratic constraints. The model proposes the use of multiple decision diagrams to decompose a quadratic matrix so that each individual diagram has provably limited size. The decision diagrams are then linked through channeling constraints to ensure that the solution represented is consistent across the decision diagrams and that the original quadratic constraints are satisfied. The resulting family of decision diagrams are optimized over by a dedicated cutting-plane algorithm akin to Benders decomposition. The approach is general, in that commercial integer programming solvers can readily apply the technique. A thorough experimental evaluation on both benchmark and synthetic instances exhibits that the proposed decision diagram reformulation provides significant improvements over current methods for quadratic constraints in state-of-the-art solvers.

DOI
10.1287/ijoc.2019.0938

Related papers

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

A Convex Reformulation and an Outer Approximation for a Large Class of Binary Quadratic Programs

Borzou Rostami, Fausto Errico, Andrea Lodi

Binary Quadratic Program with Variable Partitioning Constraints The binary quadratic program with variable partitioning constraints is a very general class of optimization problems that is very difficult to solve because of the nonconvexity and integrality of the variables and is ubiquitous, among others, in network design, computer vision, and transportation and logistics. In their article, “A convex reformulation and an outer approximation for a large class of binary quadratic programs,” Rostami et al. show how to transform such a nonconvex challenging problem into a convex bilinear program with decomposable structure. The authors develop a branch-and-cut algorithm based on outer approximation cuts, in which the cuts are generated on the fly by efficiently solving separation subproblems. The results of their computational experiments on different problems confirm the efficacy of the solution methods in solving large-scale problem instances.

Operations Research•Feb 22, 2022•14 citations

Lagrangean decompositions for the unconstrained binary quadratic programming problem

Geraldo Regis Mauri, Luiz Antônio Nogueira Lorena

The unconstrained binary quadratic programming problem (QP) is a classical non-linear problem of optimizing a quadratic objective by a suitable choice of binary decision variables. This paper proposes new Lagrangean decompositions to find bounds for QP. The methods presented treat a mixed binary linear version (LQP) of QP with constraints represented by a graph. This graph is partitioned into clusters of vertices forming a dual problem that is solved by a subgradient algorithm. The subproblems formed by the generated subgraphs are solved by CPLEX. Computational experiments consider a data set formed by several difficult instances with different features. The results show the efficiency of the proposed methods over traditional Lagrangean relaxations and other methods found in the literature.

International Transactions in Operational Research•Dec 4, 2009•11 citations

Solving Quadratic Programming by Cutting Planes

Pierre Bonami, Andrea Lodi, Jonas Schweiger +1 more

We propose new cutting planes for strengthening the linear relaxations that appear in the solution of nonconvex quadratic problems with linear constraints. By a famous result of Motzkin and Straus, these problems are connected to the clique number of a graph. Our cuts are derived in the context of a spatial branch-and-bound algorithm where linearization variables are introduced to represent products. Their validity is based on the result of Motzkin and Straus, in that it depends on the clique number of certain graphs. For convenience, we derive our cuts for the special case of the so-called standard quadratic programs, where the only (linear) constraint imposes that variables must belong to a simplex. We specifically consider cuts that correspond to carefully constructed complete bipartite graphs. We study the relation between these cuts and the classical ones obtained at the first level of the reformulation-linearization technique. By studying this relation, we derive a new type of valid inequalities that generalizes both types of cuts, and thus leading to a large family of cutting planes to strengthen the linear relaxation. We present extensive computational results using the different cutting planes we propose within the spatial branch and bound implemented by the commercial solver CPLEX. We show that our cuts allow us to obtain a significantly better bound than reformulation-linearization cuts and reduce computing times for global optimality. Finally, we formally establish the scaling necessary for using the proposed cuts to solve nonconvex quadratic problems with linear constraints, e.g., quadratic knapsack problems.

SIAM Journal on Optimization•Jan 1, 2019•22 citations

Quadratic Convex Reformulation for discrete quadratic optimization : Basic results and recent extensions

Sourour Elloumi

We consider problem (QP) of minimizing a quadratic function subject to linear or quadratic constraints. Variables are integer and bounded. This very general problem can model many classical problems in Combinatorial Optimization.A major difference between (QP) and integer linear programs lies in the fact that, in general, its continuous relaxation is an NP-hard optimization problem. To overcome this difficulty, the Convex Quadratic Reformulation approach transforms (QP) into a problem (QP'), equivalent to (QP), but whose continuous relaxation is a convex problem. To compute a global optimal solution to (QP) it becomes possible to solve (QP') by an implicit enumeration algorithm based on continuous convex optimization.We make an overview of recent developments in this approach. We show in particular how positive semidefinite relaxations can be used to build the most interesting equivalent problems (QP'). In the case of binary variables, we give a vision of classical linearization as a special case of Convex Quadratic Reformulation.Finally, we illustrate the generality and the computational efficiency of the Quadratic Convex Reformulation approach for several combinatorial optimization problems.

•Oct 28, 2014•0 citations

DECOMPOSITION AND RELAXATION ALGORITHMS FOR NONCONVEX MIXED INTEGER QUADRATICALLY CONSTRAINED QUADRATIC PROGRAMMING PROBLEMS

TIAGO COUTINHO CARNEIRO DE ANDRADE

This thesis investigates and develops algorithms based on Lagrangian relaxation and normalized multiparametric disaggregation technique to solve nonconvex mixed-integer quadratically constrained quadratic programming.First, relaxations for quadratic programming and related problem classes are reviewed.Then, the normalized multiparametric disaggregation technique is improved to a reformulated version, in which the size of the generated subproblems are reduced in the number of binary variables.Furthermore, issues related to the use of the Lagrangian relaxation to solve nonconvex problems are addressed by replacing the dual subproblems with convex relaxations.This method is compared to commercial and open source off-the-shelf global solvers using randomly generated instances.The proposed method converged in 35 of 36 instances, while Baron, the benchmark solver that obtained the best results only converged in 4 of 36.Additionally, even for the one instance the methods did not converge, it achieved relative gaps below 1% in all instances, while Baron achieved relative gaps between 10% and 30% in most of them.

•Dec 13, 2018•0 citations
In recent years the use of decision diagrams within the context of discrete optimization has proliferated. This paper continues this expansion by proposing the use of decision diagrams for modeling and solving binary optimization problems with quadratic constraints. The model proposes the use of multiple decision diagrams to decompose a quadratic matrix so that each individual diagram has provably limited size. The decision diagrams are then linked through channeling constraints to ensure that the solution represented is consistent across the decision diagrams and that the original quadratic constraints are satisfied. The resulting family of decision diagrams are optimized over by a dedicated cutting-plane algorithm akin to Benders decomposition. The approach is general, in that commercial integer programming solvers can readily apply the technique. A thorough experimental evaluation on both benchmark and synthetic instances exhibits that the proposed decision diagram reformulation provides significant improvements over current methods for quadratic constraints in state-of-the-art solvers.
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.
Binary Quadratic Program with Variable Partitioning Constraints The binary quadratic program with variable partitioning constraints is a very general class of optimization problems that is very difficult to solve because of the nonconvexity and integrality of the variables and is ubiquitous, among others, in network design, computer vision, and transportation and logistics. In their article, “A convex reformulation and an outer approximation for a large class of binary quadratic programs,” Rostami et al. show how to transform such a nonconvex challenging problem into a convex bilinear program with decomposable structure. The authors develop a branch-and-cut algorithm based on outer approximation cuts, in which the cuts are generated on the fly by efficiently solving separation subproblems. The results of their computational experiments on different problems confirm the efficacy of the solution methods in solving large-scale problem instances.
The unconstrained binary quadratic programming problem (QP) is a classical non-linear problem of optimizing a quadratic objective by a suitable choice of binary decision variables. This paper proposes new Lagrangean decompositions to find bounds for QP. The methods presented treat a mixed binary linear version (LQP) of QP with constraints represented by a graph. This graph is partitioned into clusters of vertices forming a dual problem that is solved by a subgradient algorithm. The subproblems formed by the generated subgraphs are solved by CPLEX. Computational experiments consider a data set formed by several difficult instances with different features. The results show the efficiency of the proposed methods over traditional Lagrangean relaxations and other methods found in the literature.
We propose new cutting planes for strengthening the linear relaxations that appear in the solution of nonconvex quadratic problems with linear constraints. By a famous result of Motzkin and Straus, these problems are connected to the clique number of a graph. Our cuts are derived in the context of a spatial branch-and-bound algorithm where linearization variables are introduced to represent products. Their validity is based on the result of Motzkin and Straus, in that it depends on the clique number of certain graphs. For convenience, we derive our cuts for the special case of the so-called standard quadratic programs, where the only (linear) constraint imposes that variables must belong to a simplex. We specifically consider cuts that correspond to carefully constructed complete bipartite graphs. We study the relation between these cuts and the classical ones obtained at the first level of the reformulation-linearization technique. By studying this relation, we derive a new type of valid inequalities that generalizes both types of cuts, and thus leading to a large family of cutting planes to strengthen the linear relaxation. We present extensive computational results using the different cutting planes we propose within the spatial branch and bound implemented by the commercial solver CPLEX. We show that our cuts allow us to obtain a significantly better bound than reformulation-linearization cuts and reduce computing times for global optimality. Finally, we formally establish the scaling necessary for using the proposed cuts to solve nonconvex quadratic problems with linear constraints, e.g., quadratic knapsack problems.
We consider problem (QP) of minimizing a quadratic function subject to linear or quadratic constraints. Variables are integer and bounded. This very general problem can model many classical problems in Combinatorial Optimization.A major difference between (QP) and integer linear programs lies in the fact that, in general, its continuous relaxation is an NP-hard optimization problem. To overcome this difficulty, the Convex Quadratic Reformulation approach transforms (QP) into a problem (QP'), equivalent to (QP), but whose continuous relaxation is a convex problem. To compute a global optimal solution to (QP) it becomes possible to solve (QP') by an implicit enumeration algorithm based on continuous convex optimization.We make an overview of recent developments in this approach. We show in particular how positive semidefinite relaxations can be used to build the most interesting equivalent problems (QP'). In the case of binary variables, we give a vision of classical linearization as a special case of Convex Quadratic Reformulation.Finally, we illustrate the generality and the computational efficiency of the Quadratic Convex Reformulation approach for several combinatorial optimization problems.
This thesis investigates and develops algorithms based on Lagrangian relaxation and normalized multiparametric disaggregation technique to solve nonconvex mixed-integer quadratically constrained quadratic programming.First, relaxations for quadratic programming and related problem classes are reviewed.Then, the normalized multiparametric disaggregation technique is improved to a reformulated version, in which the size of the generated subproblems are reduced in the number of binary variables.Furthermore, issues related to the use of the Lagrangian relaxation to solve nonconvex problems are addressed by replacing the dual subproblems with convex relaxations.This method is compared to commercial and open source off-the-shelf global solvers using randomly generated instances.The proposed method converged in 35 of 36 instances, while Baron, the benchmark solver that obtained the best results only converged in 4 of 36.Additionally, even for the one instance the methods did not converge, it achieved relative gaps below 1% in all instances, while Baron achieved relative gaps between 10% and 30% in most of them.