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

Optimization methods & software

Global equilibrium search applied to the unconstrained binary quadratic optimization problem

Pãnos M. Pardalos, Oleg A. Prokopyev, Oleg V. Shylo, Vladimir P. Shylo

Published Dec 22, 2007• 32 citations
Publisher

Abstract

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.

DOI
10.1080/10556780701550083

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

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

Heuristic algorithms for the unconstrained binary quadratic programming problem

J. E. Beasley

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

•Jan 1, 1998•151 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

Multistart Tabu Search Strategies for the Unconstrained Binary Quadratic Optimization Problem

Gintaras Palubeckis

Annals of Operations Research•Aug 27, 2004•147 citations

Fast two-flip move evaluations for binary unconstrained quadratic optimisation problems

Fred Glover, Jin‐Kao Hao

We provide a method for efficiently evaluating two-flip moves that simultaneously change the values of two 0-1 variables in search methods for binary unconstrained quadratic optimisation problems (UQP). We extend a framework recently proposed by the authors for creating efficient evaluations of one-flip moves to yield a method requiring significantly less computation time than a direct sequential application of one-flips. A tabu search algorithm that combines one-flip and two-flip moves, in a study currently in process, has made use of this extension to produce very competitive results on some UQP benchmark instances.

International Journal of Metaheuristics•Jan 1, 2010•14 citations
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.
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.
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.
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
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.
We provide a method for efficiently evaluating two-flip moves that simultaneously change the values of two 0-1 variables in search methods for binary unconstrained quadratic optimisation problems (UQP). We extend a framework recently proposed by the authors for creating efficient evaluations of one-flip moves to yield a method requiring significantly less computation time than a direct sequential application of one-flips. A tabu search algorithm that combines one-flip and two-flip moves, in a study currently in process, has made use of this extension to produce very competitive results on some UQP benchmark instances.