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