Universität Wien

040676 KU Metaheuristics (MA) (2017W)

4.00 ECTS (2.00 SWS), SPL 4 - Wirtschaftswissenschaften
Continuous assessment of course work
Moodle

Registration/Deregistration

Note: The time of your registration within the registration period has no effect on the allocation of places (no first come, first served).

Details

max. 30 participants
Language: English

Lecturers

Classes (iCal) - next class is marked with N

Lectur: Gast Prof. Celso Ribeiro

  • Wednesday 04.10. 15:00 - 16:30 PC-Seminarraum 5 Oskar-Morgenstern-Platz 1 1.Untergeschoß
  • Wednesday 11.10. 15:00 - 16:45 PC-Seminarraum 5 Oskar-Morgenstern-Platz 1 1.Untergeschoß
  • Wednesday 11.10. 16:50 - 18:15 PC-Seminarraum 5 Oskar-Morgenstern-Platz 1 1.Untergeschoß
  • Wednesday 18.10. 15:00 - 16:45 PC-Seminarraum 5 Oskar-Morgenstern-Platz 1 1.Untergeschoß
  • Wednesday 18.10. 16:50 - 18:15 PC-Seminarraum 5 Oskar-Morgenstern-Platz 1 1.Untergeschoß
  • Wednesday 08.11. 15:00 - 16:45 PC-Seminarraum 5 Oskar-Morgenstern-Platz 1 1.Untergeschoß
  • Wednesday 08.11. 16:50 - 18:15 PC-Seminarraum 5 Oskar-Morgenstern-Platz 1 1.Untergeschoß
  • Wednesday 15.11. 15:00 - 16:45 PC-Seminarraum 5 Oskar-Morgenstern-Platz 1 1.Untergeschoß
  • Wednesday 15.11. 16:50 - 18:15 PC-Seminarraum 5 Oskar-Morgenstern-Platz 1 1.Untergeschoß
  • Wednesday 22.11. 15:00 - 16:45 PC-Seminarraum 5 Oskar-Morgenstern-Platz 1 1.Untergeschoß
  • Wednesday 22.11. 16:50 - 18:15 PC-Seminarraum 5 Oskar-Morgenstern-Platz 1 1.Untergeschoß
  • Wednesday 29.11. 15:00 - 18:15 PC-Seminarraum 5 Oskar-Morgenstern-Platz 1 1.Untergeschoß
  • Wednesday 06.12. 15:00 - 18:15 PC-Seminarraum 5 Oskar-Morgenstern-Platz 1 1.Untergeschoß
  • Wednesday 13.12. 15:00 - 18:15 PC-Seminarraum 5 Oskar-Morgenstern-Platz 1 1.Untergeschoß

Information

Aims, contents and method of the course

Metaheuristics are general high-level procedures that coordinate simple heuristics and rules to find high-quality solutions to difficult optimization problems. They are based on distinct paradigms and offer different mechanisms to go beyond the first solution obtained that cannot be improved by local search. They are frequently built upon a number of common building blocks such as greedy algorithms, randomization, neighborhoods and local search, reduced neighborhoods and candidate lists, intensification, diversification, path-relinking, and periodical restarts. Metaheuristics are among the most effective solution strategies for solving combinatorial optimization problems in practice and very frequently produce much better solutions than those obtained by the simple heuristics and rules they coordinate.
Metaheuristics are particularly attractive in the efficient and effective solution of logistic decision problems in supply chains, transportation, telecommunications, vehicle routing and scheduling, manufacturing and machine scheduling, timetabling, sports scheduling, facility location and layout, and network design, among other areas.
The first goal of this course is to give the students a general idea of the class of problems that are amenable to be efficiently solvable by metaheuristics. With this goal in view, the course starts by a gentle and intuitive introduction to complexity theory. The second goal is to present the main metaheuristics and their building blocks, so as that the students could be able to propose or even develop simple solution strategies for practical problems. The students will learn the main concepts relevant for the design and application of metaheuristics. Finally, the third goal consists in showing some applications of metaheuristics.
1. A gentle introduction to the analysis of algorithms and complexity theory
2. Greedy algorithms
3. Local search
4. Building blocks: randomization, intensification, path-relinking, diversification, restarts
5. Greedy randomized adaptive search procedures (GRASP)
6. Simulated annealing
7. Tabu search
8. Genetic algorithms
9. Application seminars: scheduling sports competitions, routing in transportation networks, private virtual circuit routing in communication networks, data mining

Assessment and permitted materials

1. Lectures (lecturer)
2. Application seminars (lecturer)
3. Paper presentations (students)

Minimum requirements and assessment criteria

Examination topics

The evaluation methods and exact weights will be determined at the first course following a discussion with the students. They will depend on the background of the students and on the size of the group. They will involve the study of application papers, short oral
Celso C. Ribeiro Course description: Metaheuristics
2
presentations, and an application project. The active participation of the students in the discussions and in the application project will be encouraged. At the end of this course, students will know what metaheuristics are, why they are needed, how to design them, and how to evaluate their quality.

Reading list

1. M. G. C. Resende and Celso C. Ribeiro (2016), Optimization by GRASP: Greedy Randomized Adaptive Search Procedures, Springer, 312 pages.
2. M. Gendreau and J.-Y. Potvin (2010), editors, Handbook of Metaheuristics, 2nd edition, Springer, 648 pages.
3. E. K. Burke and G. Kendall (2014), editors, Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques, 2nd edition, Springer, 716 pages.
4. H. H. Hoos and T. Stützle (2005), Stochastic Local Search: Foundations and Applications, Elsevier, 658 pages.

Association in the course directory

Last modified: Mo 07.09.2020 15:29