Iterated Tabu Search for the Unconstrained Binary Quadratic Optimization Problem

Article type: Research Article

Authors: Palubeckis, Gintaras

Affiliations: Department of Practical Informatics, Kaunas University of Technology, Studentų 50, 51368 Kaunas, Lithuania, e-mail: gintaras@soften.ktu.lt

Abstract: 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.

Keywords: binary quadratic optimization, iterated tabu search, heuristics

Journal: Informatica, vol. 17, no. 2, pp. 279-296, 2006