Path relinking for unconstrained binary quadratic programming |
| |
Authors: | Yang Wang Zhipeng Lü Fred Glover Jin-Kao Hao |
| |
Institution: | 1. LERIA, Université d’Angers, 2 Boulevard Lavoisier, 49045 Angers, France;2. School of Computer Science and Technology, Huazhong University of Science and Technology, 430074 Wuhan, China;3. OptTek Systems, Inc., 2241 17th Street Boulder, CO 80302, USA |
| |
Abstract: | This paper presents two path relinking algorithms to solve the unconstrained binary quadratic programming (UBQP) problem. One is based on a greedy strategy to generate the relinking path from the initial solution to the guiding solution and the other operates in a random way. We show extensive computational results on five sets of benchmarks, including 31 large random UBQP instances and 103 structured instances derived from the MaxCut problem. Comparisons with several state-of-the-art algorithms demonstrate the efficacy of our proposed algorithms in terms of both solution quality and computational efficiency. It is noteworthy that both algorithms are able to improve the previous best known results for almost 40 percent of the 103 MaxCut instances. |
| |
Keywords: | UBQP Path relinking Tabu search MaxCut |
本文献已被 ScienceDirect 等数据库收录! |
|