The case for strategic oscillation

Fred Glover () and Jin-Kao Hao ()

Annals of Operations Research, 2011, vol. 183, issue 1, 163-173

Abstract: We study a “hard” optimization problem for metaheuristic search, where a natural neighborhood (that consists of moves for flipping the values of zero-one variables) confronts two local optima, separated by a maximum possible number of moves in the feasible space. Once a descent method reaches the first local optimum, all sequences of feasible moves to reach the second, which is the global optimum, must ultimately pass through solutions that are progressively worse until reaching the worst solution of all, which is adjacent to the global optimum. We show how certain alternative neighborhoods can locate the global more readily, but disclose that each of these approaches encounters serious difficulties by slightly changing the problem formulation. We also identify other possible approaches that seem at first to be promising but turn out to have deficiencies. Finally, we observe that a strategic oscillation approach for transitioning between feasible and infeasible space overcomes these difficulties, reinforcing recent published observations about the utility of solution trajectories that alternate between feasibility and infeasibility. We also sketch features of such an approach that have implications for future research. Copyright Springer Science+Business Media, LLC 2011

Keywords: Zero-one optimization; Strategic oscillation; Hard problems; Global minima; Tabu search (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (19)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-009-0597-1 (text/html)
Access to full text is restricted to subscribers.

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:spr:annopr:v:183:y:2011:i:1:p:163-173:10.1007/s10479-009-0597-1

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-009-0597-1

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().