Fast two-flip move evaluations for binary unconstrained quadratic optimisation problems. (20th July 2010)

• Record Type: Journal Article
• Authors: Glover, Fred; Hao, Jin-Kao
• Is Part Of: International journal of metaheuristics. Volume 1:Number 2(2010)
• Page Start: 100
• Page End: 107
• Publication Date: 2010-07-20
• Subjects: zero-one optimisation -- unconstrained quadratic programming -- metaheuristics -- computational efficiency -- two-flip moves -- tabu search; Heuristic algorithms -- Periodicals; 006.3105
• Languages: English
• ISSNs: 1755-2176

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.