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:1406.4812 · Chinese Automation Congress

A benchmark generator for boolean quadratic programming

Xiaojun Zhou, Tingwen Huang

Published Nov 6, 2020• 3 citations
arXivHTMLPDF

Abstract

For boolean quadratic programming (BQP), we will show that there is no duality gap between the primal and dual problems under some conditions by using the classical Lagrangian duality. A benchmark generator is given to create random BQP problems which can be solved in polynomial time. Several numerical examples are generated to demonstrate the effectiveness of the proposed method.

DOI
10.1109/cac51589.2020.9326828

Related papers

Duality Gap Estimation of Linear Equality Constrained Binary Quadratic Programming

Xiaojin Zheng, Xiaoling Sun, Duan Li +1 more

We investigate in this paper the Lagrangian duality properties of linear equality constrained binary quadratic programming. We derive an underestimation of the duality gap between the primal problem and its Lagrangian dual or SDP relaxation, using the distance from the set of binary integer points to certain affine subspace, while the computation of this distance can be achieved by the cell enumeration of hyperplane arrangement. Alternative Lagrangian dual schemes via the exact penalty and the squared norm constraint reformulations are also discussed.

Mathematics of Operations Research•Nov 1, 2010•11 citations

Cover-Relax-Search: A Primal Heuristic for Binary Quadratic Programs

Weimin Huang, Natalie M. Isenberg, Ján Drgoňa +2 more

Binary Quadratic Programs (BQPs) are a class of NP-hard problems that arise in a wide range of applications, including finance, machine learning, and logistics. These problems are challenging to solve due to the combinatorial search space and nonlinearity. In fact, this class of optimization problems is so challenging that, in many instances, standard algorithms struggle to identify feasible solutions within a reasonable time. Primal heuristic algorithms have been developed to quickly identify feasible solutions to BQPs. In this paper, we propose Cover-Relax-Search, an efficient primal heuristic for BQPs. This approach is inspired by multiple local search algorithms, including Undercover. We evaluate the \emph{Cover-Relax-Search} algorithm on multiple BQP benchmarks and show that our proposed heuristic identifies high-quality solutions at a faster speed and significantly reduces the primal integral compared to state-of-the-art solvers and other local search baselines.

arXiv:2501.05052•Jan 9, 2025•0 citations

Solving constrained quadratic binary problems via quantum adiabatic evolution

Pooya Ronagh, Brad Woods, Ehsan Iranmanesh

Quantum adiabatic evolution is perceived as useful for binary quadratic programming problems that are a priori unconstrained. For constrained problems, it is a common practice to relax linear equality constraints as penalty terms in the objective function. However, there has not yet been proposed a method for efficiently dealing with inequality constraints using the quantum adiabatic approach. In this paper, we give a method for solving the Lagrangian dual of a binary quadratic programming (BQP) problem in the presence of inequality constraints and employ this procedure within a branch-and-bound framework for constrained BQP (CBQP) problems.

arXiv:1509.05001•Quantum Information and Computation•Sep 1, 2016•7 citations

Sufficient optimal conditions for unconstrained quadratic binary problems

Liu Liu, Qiuling Xie, Chunli Liu

In this article, we present several sufficient optimal conditions for unconstrained quadratic binary problems, which can be applied in algorithms combining with SDP relaxations in branch-and-bound approaches for the primal problem. These optimal conditions can work for many situations when the Lagrangian duality gap is not zero.

International Symposium on Operations Research and its Applications in Engineering, Technology and Management (ISORA)•Jan 1, 2015•0 citations

Bounds for Binary Integer Programming via Unconstrained Quadratic Pseudo-Boolean Optimization

Sirilak Phonin, Chulin Likasiri

This research proposes a method for finding bounds in binary integer programming (BIP) and quadratic binary integer programming (QBIP). Our approach utilizes a max-flow technique within the framework of quadratic pseudo-Boolean optimization. We apply Lagrange multipliers to transform these problems into a quadratic pseudo-Boolean format, enabling us to create a corresponding network. We develop sufficient conditions under which a flow can or cannot be established in this network. The upper bound of the original problem is obtained through a feasible flow within the network. Additionally, we provide the optimality conditions for the solutions discussed in this paper. We have derived the closed forms for the various functions and values commonly used in our proposed method, as well as a lower bound for both BIP and QBIP, which can assist in solving these problems. This paper includes examples that illustrate both networks containing flows and those that do not, as well as examples that demonstrate lower and upper bound solutions as identified by our method. Furthermore, since our approach can also be applied to Quadratic Unconstrained Binary Optimization (QUBO), we provide the closed forms for the frequently used functions and values in that context, along with an example showcasing its application to a quadratic unconstrained optimization problem.

Mathematics•Aug 17, 2026•1 citation

A Polynomial-Time Algorithm for Unconstrained Binary Quadratic Optimization

Juan Ignacio Mulero-Martínez

In this paper, an exact algorithm in polynomial time is developed to solve unrestricted binary quadratic programs. The computational complexity is $O\left( n^{\frac{15}{2}}\right) $, although very conservative, it is sufficient to prove that this minimization problem is in the complexity class $P$. The implementation aspects are also described in detail with a special emphasis on the transformation of the quadratic program into a linear program that can be solved in polynomial time. The algorithm was implemented in MATLAB and checked by generating five million matrices of arbitrary dimensions up to 30 with random entries in the range $\left[ -50,50\right] $. All the experiments carried out have revealed that the method works correctly.

arXiv:2005.07030•May 13, 2020•0 citations
For boolean quadratic programming (BQP), we will show that there is no duality gap between the primal and dual problems under some conditions by using the classical Lagrangian duality. A benchmark generator is given to create random BQP problems which can be solved in polynomial time. Several numerical examples are generated to demonstrate the effectiveness of the proposed method.
We investigate in this paper the Lagrangian duality properties of linear equality constrained binary quadratic programming. We derive an underestimation of the duality gap between the primal problem and its Lagrangian dual or SDP relaxation, using the distance from the set of binary integer points to certain affine subspace, while the computation of this distance can be achieved by the cell enumeration of hyperplane arrangement. Alternative Lagrangian dual schemes via the exact penalty and the squared norm constraint reformulations are also discussed.
Binary Quadratic Programs (BQPs) are a class of NP-hard problems that arise in a wide range of applications, including finance, machine learning, and logistics. These problems are challenging to solve due to the combinatorial search space and nonlinearity. In fact, this class of optimization problems is so challenging that, in many instances, standard algorithms struggle to identify feasible solutions within a reasonable time. Primal heuristic algorithms have been developed to quickly identify feasible solutions to BQPs. In this paper, we propose Cover-Relax-Search, an efficient primal heuristic for BQPs. This approach is inspired by multiple local search algorithms, including Undercover. We evaluate the \emph{Cover-Relax-Search} algorithm on multiple BQP benchmarks and show that our proposed heuristic identifies high-quality solutions at a faster speed and significantly reduces the primal integral compared to state-of-the-art solvers and other local search baselines.
Quantum adiabatic evolution is perceived as useful for binary quadratic programming problems that are a priori unconstrained. For constrained problems, it is a common practice to relax linear equality constraints as penalty terms in the objective function. However, there has not yet been proposed a method for efficiently dealing with inequality constraints using the quantum adiabatic approach. In this paper, we give a method for solving the Lagrangian dual of a binary quadratic programming (BQP) problem in the presence of inequality constraints and employ this procedure within a branch-and-bound framework for constrained BQP (CBQP) problems.
This research proposes a method for finding bounds in binary integer programming (BIP) and quadratic binary integer programming (QBIP). Our approach utilizes a max-flow technique within the framework of quadratic pseudo-Boolean optimization. We apply Lagrange multipliers to transform these problems into a quadratic pseudo-Boolean format, enabling us to create a corresponding network. We develop sufficient conditions under which a flow can or cannot be established in this network. The upper bound of the original problem is obtained through a feasible flow within the network. Additionally, we provide the optimality conditions for the solutions discussed in this paper. We have derived the closed forms for the various functions and values commonly used in our proposed method, as well as a lower bound for both BIP and QBIP, which can assist in solving these problems. This paper includes examples that illustrate both networks containing flows and those that do not, as well as examples that demonstrate lower and upper bound solutions as identified by our method. Furthermore, since our approach can also be applied to Quadratic Unconstrained Binary Optimization (QUBO), we provide the closed forms for the frequently used functions and values in that context, along with an example showcasing its application to a quadratic unconstrained optimization problem.
In this paper, an exact algorithm in polynomial time is developed to solve unrestricted binary quadratic programs. The computational complexity is $O\left( n^{\frac{15}{2}}\right) $, although very conservative, it is sufficient to prove that this minimization problem is in the complexity class PPP. The implementation aspects are also described in detail with a special emphasis on the transformation of the quadratic program into a linear program that can be solved in polynomial time. The algorithm was implemented in MATLAB and checked by generating five million matrices of arbitrary dimensions up to 30 with random entries in the range $\left[ -50,50\right] $. All the experiments carried out have revealed that the method works correctly.