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

Heuristic algorithms for the unconstrained binary quadratic programming problem

J. E. Beasley

Published Jan 1, 1998• 151 citations
OpenAlex

Abstract

In this paper we consider the unconstrained binary quadratic programming problem. This is the problem of maximising a quadratic objective by suitable choice of binary (zero-one) variables. We present two heuristic algorithms based upon tabu search and simulated annealing for this problem. Computational results are presented for a number of publically available data sets involving up to 2500 variables. An interesting feature of our results is that whilst for most problems tabu search dominates simulated annealing for the very largest problems we consider the converse is true. This paper typifies a "multiple solution technique, single paper" approach, i.e. an approach that within the same paper presents results for a number of different heuristics applied to the same problem. Issues relating to algorithmic design for such papers are discussed. Keywords: unconstrained binary (zero-one) quadratic programming

Related papers

Iterated Tabu Search for the Unconstrained Binary Quadratic Optimization Problem

Gintaras Palubeckis

Given a set of objects with profits (any, even negative, numbers) assigned not only to separate objects but also to pairs of them, the unconstrained binary quadratic optimization problem consists in finding a subset of objects for which the overall profit is maximized. In this paper, an iterated tabu search algorithm for solving this problem is proposed. Computational results for problem instances of size up to 7000 variables (objects) are reported and comparisons with other up-to-date heuristic methods are provided.

Informatica•Jan 1, 2006•64 citations

Global equilibrium search applied to the unconstrained binary quadratic optimization problem

Pãnos M. Pardalos, Oleg A. Prokopyev, Oleg V. Shylo +1 more

We describe a heuristic method for solving the unconstrained binary quadratic optimization problem based on a global equilibrium search framework. We investigate performance of the proposed approach and compare it with the best available solver [G. Palubeckis, Multistart tabu search strategies for the unconstrained binary quadratic optimization problem, Ann. Oper. Res., 131 (2004), pp. 259–282; G. Palubeckis, Unconstrained binary quadratic optimization. Available at http://www.soften.ktu.lt/∼gintaras/binqopt.html (Last accessed December 2006).] on well-known benchmarks instances. The reported computational results indicate a high efficiency of the heuristic.

Optimization methods & software•Dec 22, 2007•32 citations

Iterated Tabu Search Algorithm for Solving 0-1 Binary Quadratic Programming Problem

Zhang Ai-jun, Qin Xin-qiang, Gong Chun-qiong

This paper presents an iterated Tabu Search(TS) algorithm for the Binary Quadratic Programming(BQP) problem.The TS as the Local Search(LS) and a new perturbation strategy makes the search jump into a more promising area when TS falling into the local optimum.Experimental results show that the proposed algorithm can reach the best known solution on all the 30 large OR-library instances and comparisons with TS.Simulated Annealing(SA) and Memetic Algorithm(MA) demonstrate the competitiveness of the proposed algorithm.

Jisuanji gongcheng•Jan 1, 2012•0 citations

Perturbation Based Search Method For Solving Unconstrained Binary Quadratic Programming Problem

Muthu Solayappan, Kien Ming Ng, Kim Leng Poh

This paper presents a perturbation based search method to solve the unconstrained binary quadratic programming problem. The proposed algorithm was tested with some of the standard test problems and the results are reported for 10 instances of 50, 100, 250, & 500 variable problems. A comparison of the performance of the proposed algorithm with other heuristics and optimization software is made. Based on the results, it was found that the proposed algorithm is computationally inexpensive and the solutions obtained match the best known solutions for smaller sized problems. For larger instances, the algorithm is capable of finding a solution within 0.11% of the best known solution. Apart from being used as a stand-alone method, this algorithm could also be incorporated with other heuristics to find better solutions.

•Jan 23, 2008•1 citation

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

Efficient evaluations for solving large 0-1 unconstrained quadratic optimisation problems

Fred Glover, Jin‐Kao Hao

Abstract: We provide a method for efficiently evaluating moves that complement values of 0–1 variables in search methods for binary unconstrained quadratic optimisation problems. Our method exploits a compact matrix representation and offers further improvements in speed by exploiting sparse matrices that arise in large-scale applications. The resulting approach, which works with integer or real data, can be applied to improve the efficiency of a variety of different search processes, especially in the case of commonly encountered applications that involve large and sparse matrices. It also enables larger problems to be solved than could previously be handled within a given amount of available memory. Our evaluation method has been embedded in a tabu search algorithm in a sequel to this paper, yielding a method that efficiently matches or improves currently best-known results for instances from widely used benchmark sets having up to 7,000 variables.

International Journal of Metaheuristics•Jan 1, 2010•44 citations
In this paper we consider the unconstrained binary quadratic programming problem. This is the problem of maximising a quadratic objective by suitable choice of binary (zero-one) variables. We present two heuristic algorithms based upon tabu search and simulated annealing for this problem. Computational results are presented for a number of publically available data sets involving up to 2500 variables. An interesting feature of our results is that whilst for most problems tabu search dominates simulated annealing for the very largest problems we consider the converse is true. This paper typifies a "multiple solution technique, single paper" approach, i.e. an approach that within the same paper presents results for a number of different heuristics applied to the same problem. Issues relating to algorithmic design for such papers are discussed. Keywords: unconstrained binary (zero-one) quadratic programming
Given a set of objects with profits (any, even negative, numbers) assigned not only to separate objects but also to pairs of them, the unconstrained binary quadratic optimization problem consists in finding a subset of objects for which the overall profit is maximized. In this paper, an iterated tabu search algorithm for solving this problem is proposed. Computational results for problem instances of size up to 7000 variables (objects) are reported and comparisons with other up-to-date heuristic methods are provided.
We describe a heuristic method for solving the unconstrained binary quadratic optimization problem based on a global equilibrium search framework. We investigate performance of the proposed approach and compare it with the best available solver [G. Palubeckis, Multistart tabu search strategies for the unconstrained binary quadratic optimization problem, Ann. Oper. Res., 131 (2004), pp. 259–282; G. Palubeckis, Unconstrained binary quadratic optimization. Available at http://www.soften.ktu.lt/∼gintaras/binqopt.html (Last accessed December 2006).] on well-known benchmarks instances. The reported computational results indicate a high efficiency of the heuristic.
This paper presents an iterated Tabu Search(TS) algorithm for the Binary Quadratic Programming(BQP) problem.The TS as the Local Search(LS) and a new perturbation strategy makes the search jump into a more promising area when TS falling into the local optimum.Experimental results show that the proposed algorithm can reach the best known solution on all the 30 large OR-library instances and comparisons with TS.Simulated Annealing(SA) and Memetic Algorithm(MA) demonstrate the competitiveness of the proposed algorithm.
This paper presents a perturbation based search method to solve the unconstrained binary quadratic programming problem. The proposed algorithm was tested with some of the standard test problems and the results are reported for 10 instances of 50, 100, 250, & 500 variable problems. A comparison of the performance of the proposed algorithm with other heuristics and optimization software is made. Based on the results, it was found that the proposed algorithm is computationally inexpensive and the solutions obtained match the best known solutions for smaller sized problems. For larger instances, the algorithm is capable of finding a solution within 0.11% of the best known solution. Apart from being used as a stand-alone method, this algorithm could also be incorporated with other heuristics to find better solutions.
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.
Abstract: We provide a method for efficiently evaluating moves that complement values of 0–1 variables in search methods for binary unconstrained quadratic optimisation problems. Our method exploits a compact matrix representation and offers further improvements in speed by exploiting sparse matrices that arise in large-scale applications. The resulting approach, which works with integer or real data, can be applied to improve the efficiency of a variety of different search processes, especially in the case of commonly encountered applications that involve large and sparse matrices. It also enables larger problems to be solved than could previously be handled within a given amount of available memory. Our evaluation method has been embedded in a tabu search algorithm in a sequel to this paper, yielding a method that efficiently matches or improves currently best-known results for instances from widely used benchmark sets having up to 7,000 variables.