Title

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

Document Type

Article

Publication Title

Computers and Industrial Engineering

Abstract

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 multistart 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.

First Page

164

Last Page

175

DOI

10.1016/j.cie.2017.07.012

Publication Date

9-1-2017

This document is currently not available here.

Share

COinS