Simple and fast novel diversification approach for the UBQP based on sequential improvement local search

The unconstrained binary quadratic program (UBQP) is a challenging NP-hard problem. Due to its vast applicability and the theoretical interests it has grown in importance in the recent years. Various heuristics have been proposed as solution procedures. Most of the heuristics are based on local improvement procedures. To be able to reach optimal or near optimal solutions, researchers have implemented multi start and diversification strategies to explore a larger solution space. Diversification strategies in the literature concentrate on some manipulation of solutions (variables). In this paper, relationship between starting solution, the sequence of implementing local search, and the locally optimal solution x* is explored. A novel diversification approach based on the sequence to implement the local improvement is proposed. We implemented four versions of our diversification procedures within a simple tabu search and tested on several benchmark problems available on the Internet. Our extensive computational results show that the procedures can reach the best known solutions with high frequencies within very short CPU time. For 123 out of 125 of these problems the procedures reached the best known solutions quickly. For 44 of the 84 Max-Cut benchmark problems the procedures improved upon the available solutions in reasonably short CPU time. (C) 2017 Elsevier Ltd. All rights reserved.