Universität Wien

040676 KU Metaheuristics (MA) (2017W)

4.00 ECTS (2.00 SWS), SPL 4 - Wirtschaftswissenschaften
Prüfungsimmanente Lehrveranstaltung

An/Abmeldung

Hinweis: Ihr Anmeldezeitpunkt innerhalb der Frist hat keine Auswirkungen auf die Platzvergabe (kein "first come, first served").

Details

max. 30 Teilnehmer*innen
Sprache: Englisch

Lehrende

Termine (iCal) - nächster Termin ist mit N markiert

Lectur: Gast Prof. Celso Ribeiro

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

Information

Ziele, Inhalte und Methode der Lehrveranstaltung

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

Art der Leistungskontrolle und erlaubte Hilfsmittel

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

Mindestanforderungen und Beurteilungsmaßstab

Prüfungsstoff

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.

Literatur

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.

Zuordnung im Vorlesungsverzeichnis

Letzte Änderung: Mo 07.09.2020 15:29