Universität Wien

040676 KU Metaheuristics (MA) (2024S)

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

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

  • Dienstag 05.03. 11:30 - 13:00 Seminarraum 14 Oskar-Morgenstern-Platz 1 2.Stock
  • Dienstag 19.03. 11:30 - 13:00 Seminarraum 14 Oskar-Morgenstern-Platz 1 2.Stock
  • Dienstag 09.04. 11:30 - 13:00 Seminarraum 14 Oskar-Morgenstern-Platz 1 2.Stock
  • Dienstag 16.04. 11:30 - 13:00 Seminarraum 14 Oskar-Morgenstern-Platz 1 2.Stock
  • Dienstag 23.04. 11:30 - 13:00 Seminarraum 14 Oskar-Morgenstern-Platz 1 2.Stock
  • Dienstag 30.04. 11:30 - 13:00 Seminarraum 14 Oskar-Morgenstern-Platz 1 2.Stock
  • Dienstag 07.05. 11:30 - 13:00 Seminarraum 14 Oskar-Morgenstern-Platz 1 2.Stock
  • Dienstag 14.05. 11:30 - 13:00 Seminarraum 14 Oskar-Morgenstern-Platz 1 2.Stock
  • Dienstag 21.05. 11:30 - 13:00 Seminarraum 14 Oskar-Morgenstern-Platz 1 2.Stock
  • Dienstag 28.05. 11:30 - 13:00 Seminarraum 14 Oskar-Morgenstern-Platz 1 2.Stock
  • Dienstag 04.06. 11:30 - 13:00 Seminarraum 14 Oskar-Morgenstern-Platz 1 2.Stock
  • Dienstag 11.06. 11:30 - 13:00 Seminarraum 14 Oskar-Morgenstern-Platz 1 2.Stock
  • Dienstag 18.06. 11:30 - 13:00 Seminarraum 14 Oskar-Morgenstern-Platz 1 2.Stock
  • Dienstag 25.06. 11:30 - 13:00 Seminarraum 14 Oskar-Morgenstern-Platz 1 2.Stock

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. The outline of the covered topics will be:
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

For assessment, students will have to do a project work (in groups of up to 3 people), which they also have to present, and there will be an exam.

The course will be structured as follows:
* 8 lectures (mainly presentation by lecturer with some interactive elements, 05.03. - 14.05.2024)
* 1 Q&A-Session (21.05.2024)
* 1 Exam (28.05.2024)
* 2 dates for project work presentations (18.06. & 25.06.2024)
* Deadline for handing in the project work: 28.06.2024

Art der Leistungskontrolle und erlaubte Hilfsmittel

* [45%] Exam
- 90 minutes
- pen-and-paper, closed book
* [45%] Project work (choose one):
- Mini-Coding-Project: implement a metaheuristic for an optimization problem
- Literature work: read a scientific article, summarize, analyze, and criticize it
* [10%] Oral presentation of project

Mindestanforderungen und Beurteilungsmaßstab

In order to obtain a positive grade on the course, at least 50% of the overall points have to be achieved. The grades are distributed as follows:
1: 87% to 100%
2: 75% to <87%
3: 63% to <75%
4: 50% to <63%
5: <50%

Prüfungsstoff

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

Literatur

* Handbook of Metaheuristics, Michel Gendreau & Jean-Yves Potvin, International Series in Operations Research & Management Science, Springer, ISBN 978-3-319-91085-7
* Handbook of Metaheuristics, Fred Glover & Gary A. Kochenberger, Kluwer’s International Series, ISBN 1-4020-7263-5
* Stochastic Local Search, Foundations and Applications, Holger H. Hoos & Thomas Stützle, Elsevier, ISBN 1-55860-872-9
* Search Methodologies, Introductory Tutorials in Optimization and Decision Support Techniques, Edmund K. Burke & Graham Kendall, Springer, ISBN 0-387-23460-8

Zuordnung im Vorlesungsverzeichnis

Letzte Änderung: Di 13.02.2024 14:05