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

arXiv:2107.08665

Generating Cutting Inequalities Successively for Quadratic Optimization Problems in Binary Variables

Sunyoung Kim, Masakazu Kojima

Published Jul 19, 2021• 0 citations
arXivHTMLPDF

Abstract

We propose a successive generation of cutting inequalities for binary quadratic optimization problems. Multiple cutting inequalities are successively generated for the convex hull of the set of the optimal solutions $\subset \{0, 1\}^n$, while the standard cutting inequalities are used for the convex hull of the feasible region. An arbitrary linear inequality with integer coefficients and the right-hand side value in integer is considered as a candidate for a valid inequality. The validity of the linear inequality is determined by solving a conic relaxation of a subproblem such as the doubly nonnegative relaxation, under the assumption that an upper bound for the unknown optimal value of the problem is available. Moreover, the candidates generated for the multiple cutting inequalities are tested simultaneously for their validity in parallel. Preliminary numerical results on 60 quadratic unconstrained binary optimization problems with a simple implementation of the successive cutting inequalities using an 8- or 32-core machine show that the exact optimal values are obtained for 70\% of the tested problems, demonstrating the strong potential of the proposed technique.

DOI
10.48550/arxiv.2107.08665

Related papers

A unified view of linear and quadratic convex reformulations for binary quadratic programming

Sourour Elloumi

We consider binary quadratic programs (QP) having a quadratic objectivefunction, linear constraints, and binary variables. Many classical solution methods ofthese problems are based on exact reformulation of QP into anequivalent mixed integer linear program. Several linearization methods werestudied in the literature. More recent solution methods alsobuild an exact reformulation but into a problem which objective function isquadratic and convex. A common point of the two approaches is that thecontinuous relaxation of the reformulated problem is a convex optimizationproblem that can be solved in polynomial time. This makes it possible to use a general branch-and-bound framework to solve the reformulated problem and even to rely on the strongness of standard solvers. In this paper, we show that several quadratic convex reformulation methods, as well as classical linearization, can be viewed within a unified framework. This shows the non-surprising result that linearization is a particular quadratic convex reformulation on the one hand. On the other hand, it allows to compare these methods from a theoretical point of view.

•Aug 20, 2012•0 citations

Progressive Bound Strengthening via Doubly Nonnegative Cutting Planes for Nonconvex Quadratic Programs

Qu, Zheng, Defeng Sun, Jintao Xu

We introduce a cutting-plane framework for nonconvex quadratic programs (QPs) that progressively tightens convex relaxations. Our approach leverages the doubly nonnegative (DNN) relaxation to compute strong lower bounds and generate separating cuts, which are iteratively added to improve the relaxation. We establish that, at any Karush-Kuhn-Tucker (KKT) point satisfying a second-order sufficient condition, a valid cut can be obtained by solving a linear semidefinite program (SDP), and we devise a finite-termination local search procedure to identify such points. Extensive computational experiments on both benchmark and synthetic instances demonstrate that our approach yields tighter bounds and consistently outperforms leading commercial and academic solvers in terms of efficiency, robustness, and scalability. Notably, on a standard desktop, our algorithm reduces the relative optimality gap to 0.01% on 138 out of 140 instances of dimension 100 within one hour, without resorting to branch-and-bound.

arXiv:2510.02948•Oct 3, 2025•0 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

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
We propose a successive generation of cutting inequalities for binary quadratic optimization problems. Multiple cutting inequalities are successively generated for the convex hull of the set of the optimal solutions ⊂{0,1}n\subset \{0, 1\}^n⊂{0,1}n, while the standard cutting inequalities are used for the convex hull of the feasible region. An arbitrary linear inequality with integer coefficients and the right-hand side value in integer is considered as a candidate for a valid inequality. The validity of the linear inequality is determined by solving a conic relaxation of a subproblem such as the doubly nonnegative relaxation, under the assumption that an upper bound for the unknown optimal value of the problem is available. Moreover, the candidates generated for the multiple cutting inequalities are tested simultaneously for their validity in parallel. Preliminary numerical results on 60 quadratic unconstrained binary optimization problems with a simple implementation of the successive cutting inequalities using an 8- or 32-core machine show that the exact optimal values are obtained for 70% of the tested problems, demonstrating the strong potential of the proposed technique.
We consider binary quadratic programs (QP) having a quadratic objectivefunction, linear constraints, and binary variables. Many classical solution methods ofthese problems are based on exact reformulation of QP into anequivalent mixed integer linear program. Several linearization methods werestudied in the literature. More recent solution methods alsobuild an exact reformulation but into a problem which objective function isquadratic and convex. A common point of the two approaches is that thecontinuous relaxation of the reformulated problem is a convex optimizationproblem that can be solved in polynomial time. This makes it possible to use a general branch-and-bound framework to solve the reformulated problem and even to rely on the strongness of standard solvers. In this paper, we show that several quadratic convex reformulation methods, as well as classical linearization, can be viewed within a unified framework. This shows the non-surprising result that linearization is a particular quadratic convex reformulation on the one hand. On the other hand, it allows to compare these methods from a theoretical point of view.
We introduce a cutting-plane framework for nonconvex quadratic programs (QPs) that progressively tightens convex relaxations. Our approach leverages the doubly nonnegative (DNN) relaxation to compute strong lower bounds and generate separating cuts, which are iteratively added to improve the relaxation. We establish that, at any Karush-Kuhn-Tucker (KKT) point satisfying a second-order sufficient condition, a valid cut can be obtained by solving a linear semidefinite program (SDP), and we devise a finite-termination local search procedure to identify such points. Extensive computational experiments on both benchmark and synthetic instances demonstrate that our approach yields tighter bounds and consistently outperforms leading commercial and academic solvers in terms of efficiency, robustness, and scalability. Notably, on a standard desktop, our algorithm reduces the relative optimality gap to 0.01% on 138 out of 140 instances of dimension 100 within one hour, without resorting to branch-and-bound.
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.
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.