Adaptive Memory Tabu Search for Binary Quadratic Programs

Abstract

Recent studies have demonstrated the effectiveness of applying adaptive memory tabu search procedures to combinatorial optimization problems. In this paper we describe the development and use of such an approach to solve binary quadratic programs. Computational experience is reported, showing that the approach optimally solves the most difficult problems reported in the literature. For challenging problems of limited size, which are capable of being approached by exact procedures, we find optimal solutions considerably faster than the best reported exact method. Moreover, we demonstrate that our approach is significantly more efficient and yields better solutions than the best heuristic method reported to date. Finally, we give outcomes for larger problems that are considerably more challenging than any currently reported in the literature.