Efficient evaluations for solving large 0-1 unconstrained quadratic optimisation problems. (10th May 2010)

• Record Type: Journal Article
• Authors: Glover, Fred; Hao, Jin-Kao
• Is Part Of: International journal of metaheuristics. Volume 1:Number 1(2010)
• Page Start: 3
• Page End: 10
• Publication Date: 2010-05-10
• Subjects: 0-1 optimisation -- unconstrained quadratic programming -- metaheuristics -- computational efficiency -- tabu search; Heuristic algorithms -- Periodicals; 006.3105
• Languages: English
• ISSNs: 1755-2176

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.