Diversification-driven tabu search for unconstrained binary quadratic problems

作者：Glover Fred^*; Lue Zhipeng; Hao Jin Kao

来源：4OR-A Quarterly Journal of Operations Research, 2010, 8(3): 239-253.

DOI：10.1007/s10288-009-0115-y

• UBQP
• Tabu search
• Diversification-driven
• Long-term memory

This paper describes a Diversification-Driven Tabu Search (D(2)TS) algorithm for solving unconstrained binary quadratic problems. D(2)TS is distinguished by the introduction of a perturbation-based diversification strategy guided by long-term memory. The performance of the proposed algorithm is assessed on the largest instances from the ORLIB library (up to 2500 variables) as well as still larger instances from the literature (up to 7000 variables). The computational results show that D(2)TS is highly competitive in terms of both solution quality and computational efficiency relative to some of the best performing heuristics in the literature.

• 出版日期2010-10