Computational Optimization Techniques

I Metaheuristics in GeneralRecommended reading:E. H. L. Aarts and J. K. Lenstra, editors. Local Search in Combinatorial Optimization. J. Wiley \& Sons, Chichester, UK, 1997.F. Glover. Heuristics for integer programming using surrogate constraints. Decision Sciences, 8:156–166, 1977.C. Blum and A. Roli. Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys, 35(3):268–308, 2003.II Metaheuristics Based on Solution Construction i. Greedy Randomized Adaptive Search Procedure ii. Ant Colony OptimizationRecommended reading:G. Kontoravdis and J. F. Bard. A grasp for the vehicle routing problem with time windows. ORSA Journal on Computing, 7(1):10–23, 1995.M.G.C. Resende. Greedy randomized adaptive search procedures (grasp). Journal of Global Optimization, 6:109–133, 1999.C. Blum and M. Dorigo. The hyper-cube framework for ant colony optimization. IEEE Transactions on Systems, Man and Cybernetics, Part B, 34(2):1161–1172, 2004.III Metaheuristics Based on Solution Modification i. Tabu Search ii. Guided Local Search iii. Variable Neighbourhood Search iv. Threshold Accepting v. Simulated AnnealingRecommended reading:J. B. Chambers and J. W. Barnes. New tabu search results for the job shop scheduling problem. Technical report, University of Texas, Austin, 1996. Graduate Program in Operations Research and Industrial Engineering.D. de Werra and A. Hertz. Tabu search techniques: A tutorial and an application to neural networks. OR Spektrum, 11:131–141, 1989.M. Dell’Amico and M. Trubian. Applying tabu search to the job-shop scheduling problem. Annals of Operations Research, 41:231–252, 1993.F. Glover. Tabu search - part i. ORSA Journal on Computing, 1:190–206, 1989.F. Glover. Tabu search - part ii. ORSA Journal on Computing, 2:4–32, 1990.P. Hansen and N. Mladenovic. Variable neighborhood search. In Edmund K. Burke and Graham Kendall, editors, Search Methodologies - Introductory Tutorials in Optimization and Decision Support Techniques, chapter 8, pages 211–238. Springer Science + Business Media, Inc., 2005.S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 220:671–680, 1983.IV Metaheuristics Based on Solution Recombination i. Genetic Algorithm ii. Memetic Algorithm iii. Scatter SearchRecommended reading:R. Marti, M. Laguna, and F. Glover. Principles of scatter search. European Journal of Operational Research, 169:359–372, 2006.S. Kobayashi, I. Ono, and M. Yamamura. An efficient genetic algorithm for job shop scheduling problems. In Proceedings of the 6th ICGA, pages 506–511, 1995.M. Mitchell. An Introduction to Genetic Algorithms. The MIT Press, 1996.F. Glover. A template for scatter search and path relinking. Lecture Notes on Computer Science, 1363:1–51, 1998.M. Laguna. Scatter search. In Handbook of Applied Optimization, chapter 3.6.6, pages 183–193. Oxford University Press, 2002.V.Applications i. Machine Scheduling ii. Vehicle Routing iii. Personnel Rostering iv. Large Scaled Combinatorial OptimizationRecommended reading:M. Lundy and A. Mees. Convergence of an annealing algorithm. Mathematical Programming, 34:111–124, 1986.A. S. Manne. On the job shop scheduling problem. Operations Research, 8:219–223, 1960.H. Matsuo, C. J. Suh, and R. S. Sullivan. A controlled search simulated annealing method for the general job-shop scheduling problem. Working Paper \# 03-04-88, Graduate School of Business, The University of Texas, Austin, Texas, 1988.D. C. Mattfeld. Evolutionary Search and the Job Shop. Physica-Verlag, 1996.L. M. Rousseau and M. Gendreau. Using constraints-based operators to solve the vehicle routing problem with time windows. Journal of Heuristics, 8:43–58, 2002.S. Singh and R. Sharma. A review of different approaches to the facility layout problems. International Journal of Advanced Manufacturing Technology, 30(5-6):425–433, 2006.E. Taillard. Parallel taboo search techniques for the job shop scheduling problem. ORSA Journal on Computing, 6:108–117, 1994.A. Udomsakdigool and V. Kachitvichyanukul. Multiple colony ant algorithm for job-shop scheduling problem. International Journal of Production Research, 46(15):4155–4175, 2008.S. H. Zanakis, J. R. Evans, and A. A. Vazacopoulos. Heuristic methods and applications: A categorized survey. European Journal of Operational Research, 43:88–110, 1989.