#### Heuristic algorithms for the unconstrained binary quadratic programming
problem

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.

J E Beasley