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

Authors: Fred Glover, Jin-Kao Hao

Addresses: OptTek Systems Inc., 2241 17th 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 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.

Keywords: zero-one optimisation; unconstrained quadratic programming; metaheuristics; computational efficiency; two-flip moves; tabu search.

DOI: 10.1504/IJMHEUR.2010.034201

International Journal of Metaheuristics, 2010 Vol.1 No.2, pp.100 - 107

Published online: 19 Jul 2010 *

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