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

Authors: Fred Glover, Jin-Kao Hao

Addresses: OprTek Systems, Inc., 1919 Seventh Street, Boulder, CO 80302, USA. ' Laboratoire d'Etude et de Recherche en Informatique (LERIA), Universite d'Angers, 2 Boulevard Lavoisier, 49045 Angers Cedex 01, France

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.

Keywords: 0-1 optimisation; unconstrained quadratic programming; metaheuristics; computational efficiency; tabu search.

DOI: 10.1504/IJMHEUR.2010.033120

International Journal of Metaheuristics, 2010 Vol.1 No.1, pp.3 - 10

Published online: 08 May 2010 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article