The corridor method: a dynamic programming inspired metaheuristic
Moshe Sniedovich, Stefan Voß · Control and Cybernetics · 2006
This paper presents a dynamic programming inspired metaheuristic called Corridor Method. It can be classified as a method-based iterated local search in that it deploys method-based neighborhoods. By this we mean that the search for a new candi- date solution is carried out by a fully-fledged optimization method and generates a global optimal solution over the neighborhood. The neighborhoods are thus constructed to be suitable domains for the fully-fledged optimization method used. Typically, these neighbor- hoods are obtained by the imposition of exogenous constraints on the decision space of the target problem and therefore must be com- patible with the optimization method used to search these neighbor- hoods. This is in sharp contrast to traditional metaheuristics where neighborhoods are move-based, that is, they are generated by sub- jecting the candidate solution to small changes called moves. While conceptually this method-based paradigm applies to any optimiza- tion method, in practice it is best suited to support optimization methods such as dynamic programming, where it is easy to con- trol the size of a problem, hence the complexity of algorithms, by means of exogenous constraints. The essential features of the Cor- ridor Method are illustrated by a number of examples, including the traveling salesman problem, where exponentially large neigh- borhoods are searched by a linear time/space dynamic programming algorithm.