The corridor method: a dynamic programming inspired metaheuristic

• Autorzy: Sniedovich M. , Viß S.
• Języki publikacji: EN

Abstrakty

EN

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 candidate 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 neighborhoods are obtained by the imposition of exogenous constraints on the decision space of the target problem and therefore must be compatible with the optimization method used to search these neighborhoods. This is in sharp contrast to traditional metaheuristics where neighborhoods are move-based, that is, they are generated by subjecting the candidate solution to small changes called moves. While conceptually this method-based paradigm applies to any optimization method, in practice it is best suited to support optimization methods such as dynamic programming, where it is easy to control the size of a problem, hence the complexity of algorithms, by means of exogenous constraints. The essential features of the Corridor Method are illustrated by a number of examples, including the traveling salesman problem, where exponentially large neighborhoods are searched by a linear time/space dynamic programming algorithm.

Słowa kluczowe

EN

metaheuristics; dynamic programming; curse of dimensionality; very large neighborhoods; corridor method; global optimization; move-based; method-based; traveling salesman problem

PL

programowanie dynamiczne

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2006
• Tom: Vol. 35, no 3
• Strony: 551--578
• Opis fizyczny: Bibliogr. 23 poz.

Twórcy

autor

Sniedovich M.

autor

Viß S.

• Department of Mathematics and Statistics, The University of Melbourne, Australia,

Bibliografia

• AHUJA, R.K., ERGUN, O., ORLIN, J.B., and PUNNEN, A.P. (2002) A survey of large-scale neighborhood search techniques. Discrete Applied Mathematics 123(1-3), 75-102.
• BALAS, E. (1999) New classes of efficiently solvable generalized traveling salesman problems. Annals of Operations Research 86, 529-558.
• BALAS, E. and SIMONETTI, N. (2001) Linear time dynamic programming algorithms for new classes of restricted TSP's: a computational study. INFORMS Journal on Computing 13(1), 56-75.
• BELLMAN, R.E. (1957) Dynamic Programming. Princeton University Press.
• CARRAWAY, R.L., and MORIN, T.L. (1988) Theory and applications of generalized dynamic programming: an overview. International Journal of Computers and Mathematics with Applications 16, 779-788.
• CHOW, V.T., MAIDEMENT, D.M. and TAUXE, G.W. (1975) Computer time and memory for DP and DDDP in water resource systems analysis. Water Resources Research 11(3), 621-628.
• DANTZIG, G., FULKERSON, D. and JOHNSON, S. (1954) Solution of a Large Scale Traveling Salesman Problem. Operations Research 2, 393-410.
• CAREY, M.R. and JOHNSON, D.S. (1979) Computers and Intractability: a Guide to the Theory of NP-Completeness. W.H. Freeman.
• HEIDARI, M., CHOW, T., and KOKOTOVIC, P.V. (1971) Discrete differential dynamic programming approach to water resources systems optimization. Water Resources Research 7(2), 273-282.
• HOOS, H.H. and STUTZLE, T. (2004) Stochastic Local Search. Elsevier.
• IBARAKI. T. (1987) Enumerative Approaches to Combinatorial Optimization. J.C. Baltzer AC, Basel.
• KOSSMANN, D. and STOCKER, K. (2000) Iterative dynamic programming: a new class of query optimization algorithms. ACM Transactions on Database Systems 25(1), 43-82.
• LEUNG C., APPLETON, B and SUN, C. (2004) Fast Stereo Matching by Iterated Dynamic Programming and Quadtree Subregioning. In: A. Hoppe, S. Barman, and T. Ellis, eds. British Machine Vision Conference 1, 97-106, Kingston University, London.
• LUUS. R. (2000) Iterative Dynamic Programming. Chapman and Hall, London.
• MORIN, T.L. and MARSTEN, R.E. (1976) Branch and bound strategies for dynamic programming. Operations Research 24, 611-627.
• MARTIN, R.K., RARDIN, R.L. and CAMPBELL, B.A. (1990) Polyhedral characterization of discrete dynamic programming. Operations Research 38(1), 127-138.
• MILLER, C., TUCKER, A. and ZEMLIN, R. (1960) Integer Programming Formulation of Traveling Salesman Problems. Journal of the ACM 7, 326 -329.
• POTTS, C. and VAN DE VELDE, S. (1995) Dynasearch - iterative local improvement by dynamic programming. Technical Report. University of Twente.
• SHERALI, H.D. and DRISCOLL, P.J. (2002) On tightening the relaxations of Miller-Tucker-Zemlin formulations for asymmetric traveling salesman problems. Operations Research 50(4), 656-669.
• SNIEDOVICH, M. (1992) Dynamic Programming. Marcel Dekker, NY.
• VOSS, S. (2001) Meta-heuristics: The state of the art. In: Local Search for Planning and Scheduling, 1-23, LNAI 2148, Springer-Verlag.
• WINSTON, W.L. (1994) Operations Research: Applications and Algorithms, 3rd edition. Thompson International, Belmont.
• YAKOWITZ, S.J. (1982) Dynamic programming applications in water resources, Water Resources Research, 18, 673-696.