Tabu search exploiting local optimality in binary optimization

Saïd Hanafi, Yang Wang, Fred Glover, Wei Yang and Rick Hennig

European Journal of Operational Research, 2023, vol. 308, issue 3, 1037-1055

Abstract: A variety of strategies have been proposed for overcoming local optimality in metaheuristic search. This paper examines characteristics of moves that can be exploited to make good decisions about steps that lead away from a local optimum and then lead toward a new local optimum. We introduce strategies to identify and take advantage of useful features of solution history with an adaptive memory metaheuristic, to provide rules for selecting moves that offer promise for discovering improved local optima. Our approach uses a new type of adaptive memory based on a construction called exponential extrapolation. The memory operates by means of threshold inequalities that ensure selected moves will not lead to a specified number of most recently encountered local optima. Associated thresholds are embodied in choice rule strategies that further exploit the exponential extrapolation concept and open a variety of research possibilities for exploration. The considerations treated in this study are illustrated in an implementation to solve the Quadratic Unconstrained Binary Optimization (QUBO) problem. We show that the AA algorithm obtains an average objective gap of 0.0315% to the best known values for the 21 largest Palubeckis instances. This solution quality is considered to be quite attractive because less than 20 s on average are taken by AA, which is 1 to 2 orders of magnitude less than the time required by most algorithms reporting the best known results.

Keywords: Metaheuristics; Local optimality; Adaptive memory; Tabu search; Binary optimization; QUBO (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221723000012
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:308:y:2023:i:3:p:1037-1055

DOI: 10.1016/j.ejor.2023.01.001

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().