학술논문
An iterated greedy algorithm for the binary quadratic programming problem
Document Type
Conference
Source
The 6th International Conference on Soft Computing and Intelligent Systems, and The 13th International Symposium on Advanced Intelligence Systems Soft Computing and Intelligent Systems (SCIS) and 13th International Symposium on Advanced Intelligent Systems (ISIS), 2012 Joint 6th International Conference on. :2183-2188 Nov, 2012
Subject
Language
Abstract
The binary quadratic programming problem (BQP) is an NP-hard problem and has a large number of applications. In this paper, an iterated greedy algorithm with k-opt local search (IGKLS) is proposed for the BQP. Iterated greedy (IG) algorithm has already been applied to a variety of optimization problems, and shown to be simple but with excellent search performance. The proposed iterated greedy algorithm consists of two central phases, destruction and construction phases. As a local search algorithm, k-opt local search is applied after the construction phase. The computational results showed that the proposed iterated greedy algorithm outperformed state-of-the-art methods for huge size BQP instances.