WHU - Startseite | Logo

Computational Optimization Techniques

Metaheuristics, in their original form, are guided local improvement procedures to perform a robust search of a solution space. New developments in metaheuristic methods are proved to be so remarkably effective, that they have moved into the spotlight in recent years for solving complex combinatorial problems, particularly those encountered in practice. This course is designed to provide doctoral students with a broad coverage of the concepts and instrumentalities of this important and evolving area of optimization. In doing so, I hope to encourage an even wider adoption of metaheuristics for assisting in various research areas.
Course code
ELEC837
Course type
Doctoral Program Lecture
Weekly Hours
2,0
ECTS
3
Term
FS 2024
Language
Englisch
Lecturers
Prof. Dr. Liji Shen
Please note that exchange students obtain a higher number of credits in the BSc-program at WHU than listed here. For further information please contact directly the International Relations Office.

This course is designed to provide doctoral students with a broad coverage of the concepts andinstrumentalities of optimization. We will be addressing a variety of solution methodologiesthat tackle complex problems encountered in both theory and practice. In doing so, we hopeto encourage an even wider adoption of soft computing skills for assisting in various researchareas.


At the initial stage, mathematical programming with optimization software is developed to
guarantee solution optimality. As we progress to real-world and large-scaled settings that go
beyond the capacity of exact algorithms, we introduce efficient and powerful metaheurisitcs,
which, in their original form, are guided local improvement procedures to perform a robust
search of a solution space. New developments in metaheuristic methods are proved to be so
remarkably effective, that they have moved into the spotlight in recent years for solving the
hardest combinatorial problems, particularly those commonly found in practice.

Content

Session 1

  • Introduction to combinatorial optimization
  • Application of linear models
  • Defining mixed integer programming models
  • Examples: facility location, scheduling, transportation

Session 2

  • Introduction to metaheuristics
  • Trajectory methods
  • Evolutionary computation
  • Comparison and application

Session 3

  • Research proposal in diverse fields
  • Guest lectures on extended topics (hybridization, real-cases)
  • Final presentation and discussion
Date Time
Thursday, 16.05.2024 09:00 - 18:00
Friday, 17.05.2024 09:00 - 18:00
  • Building efficient and transformative mathematical models
  • Applying state-of-the-art optimization software
  • Familiarizing with metaheuristic framework
Recommended Reading:1) E. H. L. Aarts and J. K. Lenstra, editors. Local Search in Combinatorial Optimization. J. Wiley & Sons, Chichester, UK, 1997.2) F. Glover. Heuristics for integer programming using surrogate constraints. Decision Sciences, 8:156 – 166, 1977.3) C. Blum and A. Roli. Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys, 35(3):268–308, 2003.4) 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.5) M.G.C. Resende. Greedy randomized adaptive search procedures (grasp). Journal of Global Optimization, 6:109–133, 1999.6) 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.7) 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.8) D. deWerra and A. Hertz. Tabu search techniques: A tutorial and an application to neural networks. OR Spektrum, 11:131–141, 1989.9) M. Dell’Amico and M. Trubian. Applying tabu search to the job-shop scheduling problem. Annals of Operations Research, 41:231–252, 1993.10) F. Glover. Tabu search - part i. ORSA Journal on Computing, 1:190–206, 1989.11) F. Glover. Tabu search - part ii. ORSA Journal on Computing, 2:4–32, 1990.12) 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.13) S. Kirkpatrick, C. D. Gelatt, andM. P. Vecchi. Optimization by simulated annealing. Science, 220:671 – 680, 1983.14) R. Marti, M. Laguna, and F. Glover. Principles of scatter search. European Journal of Operational Research, 169:359–372, 2006.15) 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.16) M. Mitchell. An Introduction to Genetic Algorithms. The MIT Press, 1996.17) F. Glover. A template for scatter search and path relinking. Lecture Notes on Computer Science, 1363:1–51, 1998.18) M. Laguna. Scatter search. In Handbook of Applied Optimization, chapter 3.6.6, pages 183–193. Oxford University Press, 2002.19) M. Lundy and A.Mees. Convergence of an annealing algorithm.Mathematical Programming, 34:111 – 124, 1986.20) A. S. Manne. On the job shop scheduling problem. Operations Research, 8:219–223, 1960.21) 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.22) D. C. Mattfeld. Evolutionary Search and the Job Shop. Physica-Verlag, 1996.23) 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.24) 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.25) E. Taillard. Parallel taboo search techniques for the job shop scheduling problem. ORSA Journal on Computing, 6:108–117, 1994.26) A. Udomsakdigool and V. Kachitvichyanukul.Multiple colony ant algorithm for job-shop scheduling problem. International Journal of Production Research, 46(15):4155–4175, 2008.27) 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.
  • Embedded student presentations
  • Interactive teaching style
  • Extended implementation and visualization
Class discussion (20%)

Active participation and lively discussion in the
classroom are greatly encouraged.

Research proposal (40%)

The purpose of a research proposal is twofold. Students
are first required to summarize existing solution
methods in their individual research field, if
applicable, with an emphasis on the implementations
of metaheuristics. More importantly, the proposal
shall focus on a specific problem setting. Students
are to design new algorithms usingmetaheuristic
framework. For conventional combinatorial
problems, constructive suggestions and extensions
are expected.

Presentation (40%)

For refinement and further discussion, students
are to present their proposal in the third session.

90
WHU - Startseite | Logo