Universität Wien FIND

Bedingt durch die COVID-19-Pandemie können kurzfristige Änderungen bei Lehrveranstaltungen und Prüfungen (z.B. Absage von Vor-Ort-Lehre und Umstellung auf Online-Prüfungen) erforderlich sein. Melden Sie sich für Lehrveranstaltungen/Prüfungen über u:space an, informieren Sie sich über den aktuellen Stand auf u:find und auf der Lernplattform moodle. ACHTUNG: Lehrveranstaltungen, bei denen zumindest eine Einheit vor Ort stattfindet, werden in u:find momentan mit "vor Ort" gekennzeichnet.

Regelungen zum Lehrbetrieb vor Ort inkl. Eintrittstests finden Sie unter https://studieren.univie.ac.at/info.

040676 KU Metaheuristics (MA) (2021S)

4.00 ECTS (2.00 SWS), SPL 4 - Wirtschaftswissenschaften
Prüfungsimmanente Lehrveranstaltung
DIGITAL
Mi 12.05. 09:45-11:15 Digital

An/Abmeldung

Details

max. 30 Teilnehmer*innen
Sprache: Englisch

Lehrende

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

Mittwoch 03.03. 09:45 - 11:15 Digital
Mittwoch 10.03. 09:45 - 11:15 Digital
Mittwoch 17.03. 09:45 - 11:15 Digital
Mittwoch 24.03. 09:45 - 11:15 Digital
Mittwoch 14.04. 09:45 - 11:15 Digital
Mittwoch 21.04. 09:45 - 11:15 Digital
Mittwoch 28.04. 09:45 - 11:15 Digital
Mittwoch 05.05. 09:45 - 11:15 Digital
Mittwoch 19.05. 09:45 - 11:15 Digital
Mittwoch 26.05. 09:45 - 11:15 Digital
Mittwoch 02.06. 09:45 - 11:15 Digital
Mittwoch 09.06. 09:45 - 11:15 Digital
Mittwoch 16.06. 09:45 - 11:15 Digital
Mittwoch 23.06. 09:45 - 11:15 Digital
Mittwoch 30.06. 09:45 - 11:15 Digital

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 objective of this course is to provide students with the fundamental tools for designing, tuning, and testing heuristics and metaheuristics for hard combinatorial optimization problems. Besides that, we will also cover the fundamental concepts of complexity theory that are the key to understanding the need for approximate approaches and to design efficient heuristics and metaheuristics.
1. A gentle introduction to the analysis of algorithms and complexity theory
2. Historical and modern local search methods
3. Nature-inspired metaheuristics
4. Construction-based metaheuristics

Art der Leistungskontrolle und erlaubte Hilfsmittel

* Four short written tests during the course, no material allowed: 40% (4x10%)
* Project work (choose one): 45%
- programming a metaheuristic for an optimisation problem
- read and study a scientific paper
* Oral presentation of the project: 15%

Mindestanforderungen und Beurteilungsmaßstab

Appropriate points will be assigned to each part of the exam and to the possible homework, the grading will be scaled in 100%.
In order to pass the course (minimum requirement) students have to achieve at least 50% in total.

The other grades are distributed as follows:
4: 50% to <63%
3: 63% to <75%
2: 75% to <87%
1: 87% to 100%

Prüfungsstoff

* Analysis of algorithms and complexity theory (basics)
* Local search methods
* Nature-inspired metaheuristics
* Construction-based metaheuristics

Literatur

The teaching material (slides, sample code, further reading, etc.) is available on the e-learning platform Moodle.

Useful literature:
1. M. Gendreau and J.-Y. Potvin (2010), editors, Handbook of Metaheuristics, 2nd edition, Springer, 648 pages.
2. E. K. Burke and G. Kendall (2014), editors, Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques, 2nd edition, Springer, 716 pages.
3. H. H. Hoos and T. Stützle (2005), Stochastic Local Search: Foundations and Applications, Elsevier, 658 pages.

Zuordnung im Vorlesungsverzeichnis

Letzte Änderung: Mi 21.04.2021 11:25