Premium
Toward unification of exact and heuristic optimization methods
Author(s) -
Hooker J. N.
Publication year - 2015
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12020
Subject(s) - unification , heuristic , mathematical optimization , dual (grammatical number) , component (thermodynamics) , computer science , constraint (computer aided design) , inference , mathematics , algorithm , artificial intelligence , thermodynamics , programming language , art , physics , geometry , literature
This paper argues that many exact and heuristic methods have common structure that permits some degree of unification. It interprets solution algorithms as primal–dual methods in which the primal component searches over problem restrictions, and the dual component obtains bounds on the optimal value. In particular, the concept of an inference dual provides the basis for constraint‐directed search, which is a feature of many exact and heuristic methods. The motivations for unification are (a) to encourage the exchange of algorithmic techniques between exact and heuristic methods and (b) to design solution methods that transition gracefully from exact to heuristic modes as problem instances scale up.