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

A Dual Bounding Framework Through Cost Splitting for Binary Quadratic Optimization

Mahdis Bayani, Borzou Rostami, Yossiri Adulyasak, Louis-Martin Rousseau

Published Mar 12, 2024• 0 citations
Publisher

Abstract

Binary quadratic programming (BQP) is a class of combinatorial optimization problems comprising binary variables, quadratic objective functions, and linear/nonlinear constraints. This paper examines a unified framework to reformulate a BQP problem with linear constraints to a new BQP with an exponential number of variables defined on a graph. This framework relies on the concept of stars in the graph to split the quadratic costs into adjacent and nonadjacent components indicating in-star and out-of-star interactions. We exploit the star-based structure of the new reformulation to develop a decomposition-based column generation algorithm. In our computational experiments, we evaluate the performance of our methodology on different applications with different quadratic structures. The quadratic component of the problem is dealt with in the column generation master problem and its subproblem. Results indicate the superiority of the framework over one of the state-of-the-art solvers, GUROBI, when applied to various benchmark reformulations with adjacent-only or sparse quadratic cost matrices. The framework outperforms GUROBI in terms of both dual bound and computational time in almost all instances. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: The authors thank the Mitacs Accelerate Program for providing funding for this project. In addition, B. Rostami gratefully acknowledges the funding provided by the Canadian Natural Sciences and Engineering Research Council (NSERC) under a Discovery Grant [Grant RGPIN-2020-05395]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2021.0186 .

DOI
10.1287/ijoc.2021.0186

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

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

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

A Direct SDP Approach for Constrained Quadratic Binary Optimization Problems

MilaNedic, Zvmcevap

This repository contains the source code, computational experiments, analysis, and benchmarks accompanying the paper A Direct SDP-Based Framework for Certified Bounds for Constrained Quadratic Binary Optimization Problems. The repository implements a direct semidefinite programming (SDP) approach for constrained quadratic binary optimization, designed to obtain strong bounds for exact optimization. The SDP relaxation is strengthened using quadratized linear constraints and triangle (hypermetric) inequalities. To address the numerical infeasibility of SDP solutions obtained from numerical solvers such as MOSEK, the framework includes a correction procedure that converts approximate SDP solutions into mathematically certified bounds suitable for use in Branch-and-Bound algorithms. The repository also implements an adaptation of the Goemans–Williamson randomized hyperplane rounding scheme to constrained binary optimization, together with problem-specific feasibility restoration. Computational experiments are provided for the Sparsest k-Subgraph and Maximum Independent Set problems. The work presented in this repository was funded and developed under the QBIQ project (project no. 644), funded by the Slovenian Research and Innovation Agency (ARIS) through the Applied Projects programme. The code and accompanying data are intended to facilitate reproducibility of the computational results and provide a foundation for further research on exact SDP-based methods for constrained quadratic binary optimization.

•Aug 25, 2026•0 citations

A fast global algorithm for multi-linearly constrained separable binary quadratic program

Guangtai Qu, Shaoze Li, Zhibin Deng +1 more

The multi-linearly constrained separable binary quadratic programming problem (MLSBQP) is a direct extension of the classical singly-linearly constrained separable binary quadratic programming problem (SLSBQP). In the literature, several algorithms have been proposed for SLSBQP which can solve problem instances with millions of variables globally. However, for the case of MLSBQP, the current state-of-the-art solver can only solve problems with up to 40000 binary variables within a reasonable computational time. In this paper, we propose an extremely efficient branch-and-bound algorithm for solving MLSBQP. The main feature of the proposed algorithm is that an efficient dual coordinate ascent algorithm is applied to obtain lower bounds, and the complexity of each inner loop of the dual coordinate ascent algorithm is $ \mathcal{O}(n\log n) $. Our numerical experiments show that the proposed branch-and-bound algorithm can solve MLSBQP with up to millions of variables within only several minutes, and performs much faster than Gurobi when the number of linear constraints is small.

Journal of Industrial and Management Optimization•Oct 9, 2024•7 citations

Enhancing Quadratic Programming Solvers via Quadratic Nonconvex Reformulation

Cheng Zhu Lu, Fei Yu, Kang, Gaojian +4 more

In this paper, we consider solving nonconvex quadratic programming problems using modern solvers such as Gurobi and SCIP. It is well-known that the classical techniques of quadratic convex reformulation can improve the computational efficiency of global solvers for mixed-integer quadratic optimization problems. In contrast, the use of quadratic nonconvex reformulation (QNR) has not been previously explored. This paper introduces a QNR framework--an unconventional yet highly effective approach for improving the performance of state-of-the-art quadratic programming solvers such as Gurobi and SCIP. Our computational experiments on diverse nonconvex quadratic programming problem instances demonstrate that QNR can substantially accelerate both Gurobi and SCIP. Notably, with QNR, Gurobi achieves state-of-the-art performance on several benchmark and randomly generated instances.

arXiv:2508.20897•Aug 28, 2025•2 citations
Binary quadratic programming (BQP) is a class of combinatorial optimization problems comprising binary variables, quadratic objective functions, and linear/nonlinear constraints. This paper examines a unified framework to reformulate a BQP problem with linear constraints to a new BQP with an exponential number of variables defined on a graph. This framework relies on the concept of stars in the graph to split the quadratic costs into adjacent and nonadjacent components indicating in-star and out-of-star interactions. We exploit the star-based structure of the new reformulation to develop a decomposition-based column generation algorithm. In our computational experiments, we evaluate the performance of our methodology on different applications with different quadratic structures. The quadratic component of the problem is dealt with in the column generation master problem and its subproblem. Results indicate the superiority of the framework over one of the state-of-the-art solvers, GUROBI, when applied to various benchmark reformulations with adjacent-only or sparse quadratic cost matrices. The framework outperforms GUROBI in terms of both dual bound and computational time in almost all instances. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: The authors thank the Mitacs Accelerate Program for providing funding for this project. In addition, B. Rostami gratefully acknowledges the funding provided by the Canadian Natural Sciences and Engineering Research Council (NSERC) under a Discovery Grant [Grant RGPIN-2020-05395]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2021.0186 .
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.
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.
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.
This repository contains the source code, computational experiments, analysis, and benchmarks accompanying the paper A Direct SDP-Based Framework for Certified Bounds for Constrained Quadratic Binary Optimization Problems. The repository implements a direct semidefinite programming (SDP) approach for constrained quadratic binary optimization, designed to obtain strong bounds for exact optimization. The SDP relaxation is strengthened using quadratized linear constraints and triangle (hypermetric) inequalities. To address the numerical infeasibility of SDP solutions obtained from numerical solvers such as MOSEK, the framework includes a correction procedure that converts approximate SDP solutions into mathematically certified bounds suitable for use in Branch-and-Bound algorithms. The repository also implements an adaptation of the Goemans–Williamson randomized hyperplane rounding scheme to constrained binary optimization, together with problem-specific feasibility restoration. Computational experiments are provided for the Sparsest k-Subgraph and Maximum Independent Set problems. The work presented in this repository was funded and developed under the QBIQ project (project no. 644), funded by the Slovenian Research and Innovation Agency (ARIS) through the Applied Projects programme. The code and accompanying data are intended to facilitate reproducibility of the computational results and provide a foundation for further research on exact SDP-based methods for constrained quadratic binary optimization.
The multi-linearly constrained separable binary quadratic programming problem (MLSBQP) is a direct extension of the classical singly-linearly constrained separable binary quadratic programming problem (SLSBQP). In the literature, several algorithms have been proposed for SLSBQP which can solve problem instances with millions of variables globally. However, for the case of MLSBQP, the current state-of-the-art solver can only solve problems with up to 40000 binary variables within a reasonable computational time. In this paper, we propose an extremely efficient branch-and-bound algorithm for solving MLSBQP. The main feature of the proposed algorithm is that an efficient dual coordinate ascent algorithm is applied to obtain lower bounds, and the complexity of each inner loop of the dual coordinate ascent algorithm is $ \mathcal{O}(n\log n) $. Our numerical experiments show that the proposed branch-and-bound algorithm can solve MLSBQP with up to millions of variables within only several minutes, and performs much faster than Gurobi when the number of linear constraints is small.
In this paper, we consider solving nonconvex quadratic programming problems using modern solvers such as Gurobi and SCIP. It is well-known that the classical techniques of quadratic convex reformulation can improve the computational efficiency of global solvers for mixed-integer quadratic optimization problems. In contrast, the use of quadratic nonconvex reformulation (QNR) has not been previously explored. This paper introduces a QNR framework--an unconventional yet highly effective approach for improving the performance of state-of-the-art quadratic programming solvers such as Gurobi and SCIP. Our computational experiments on diverse nonconvex quadratic programming problem instances demonstrate that QNR can substantially accelerate both Gurobi and SCIP. Notably, with QNR, Gurobi achieves state-of-the-art performance on several benchmark and randomly generated instances.