040676 KU Metaheuristics (MA) (2021W)
Continuous assessment of course work
Labels
MIXED
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).
- Registration is open from Mo 13.09.2021 09:00 to Th 23.09.2021 12:00
- Registration is open from Mo 27.09.2021 09:00 to We 29.09.2021 12:00
- Deregistration possible until Fr 15.10.2021 23:59
Details
max. 30 participants
Language: English
Lecturers
Classes (iCal) - next class is marked with N
+++ UPDATE (22.11.2021) +++
In light of the recent development of the COVID-19 pandemic and the corresponding measures implemented by the university and the government, it was decided that both the exam (15.12.2021) and the preceding Q&A-Session (01.12.2021) will NOT take place on-site anymore, but will be held ONLINE.
- Wednesday 06.10. 11:30 - 13:00 Digital
- Wednesday 13.10. 11:30 - 13:00 Digital
- Wednesday 20.10. 11:30 - 13:00 Digital
- Wednesday 27.10. 11:30 - 13:00 Digital
- Wednesday 03.11. 11:30 - 13:00 Digital
- Wednesday 10.11. 11:30 - 13:00 Digital
- Wednesday 17.11. 11:30 - 13:00 Digital
- Wednesday 24.11. 11:30 - 13:00 Digital
-
Wednesday
01.12.
11:30 - 13:00
Digital
PC-Seminarraum 5 Oskar-Morgenstern-Platz 1 1.Untergeschoß -
Wednesday
15.12.
11:30 - 13:00
Digital
Hörsaal 15 Oskar-Morgenstern-Platz 1 2.Stock
Hörsaal 3 Oskar-Morgenstern-Platz 1 Erdgeschoß
PC-Seminarraum 3 Oskar-Morgenstern-Platz 1 1.Untergeschoß
PC-Seminarraum 5 Oskar-Morgenstern-Platz 1 1.Untergeschoß - Wednesday 12.01. 11:30 - 13:00 Digital
- Wednesday 19.01. 11:30 - 13:00 Digital
- Wednesday 26.01. 11:30 - 13:00 Digital
Information
Aims, contents and method of the course
Assessment and permitted materials
+++ UPDATE (22.11.2021) +++
The exam (15.12.2021) will NOT take place on-site anymore, but will be held ONLINE. It will take place in Zoom (like all the other lectures). The mode of the exam will be changed from closed-book to open-book. For more details see Moodle!---* [45%] Exam
- 90 minutes
- pen-and-paper, closed book
* [45%] Project work (choose one):
- Mini-Coding-Project: implement a metaheuristic for an optimisation problem
- Literature work: read a scientific article, summarise, analyse and criticise it
* [10%] Oral presentation of project
The exam (15.12.2021) will NOT take place on-site anymore, but will be held ONLINE. It will take place in Zoom (like all the other lectures). The mode of the exam will be changed from closed-book to open-book. For more details see Moodle!---* [45%] Exam
- 90 minutes
- pen-and-paper, closed book
* [45%] Project work (choose one):
- Mini-Coding-Project: implement a metaheuristic for an optimisation problem
- Literature work: read a scientific article, summarise, analyse and criticise it
* [10%] Oral presentation of project
Minimum requirements and assessment criteria
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%
1: 87% to 100%
2: 75% to <87%
3: 63% to <75%
4: 50% to <63%
5: <50%
Examination topics
* Analysis of algorithms and complexity theory (basics)
* Local search methods
* Nature-inspired metaheuristics
* Construction-based metaheuristics
* Local search methods
* Nature-inspired metaheuristics
* Construction-based metaheuristics
Reading list
* 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
* 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
Association in the course directory
Last modified: Fr 12.05.2023 00:13
In light of the recent development of the COVID-19 pandemic and the corresponding measures implemented by the university and the government, it was decided that both the exam (15.12.2021) and the preceding Q&A-Session (01.12.2021) will NOT take place on-site anymore, but will be held ONLINE. Both will take place in Zoom (like all the other lectures) and the mode of the exam will be changed from closed-book to open-book.---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 metaheuristicsFor 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 (digital, mainly presentation by lecturer with some interactive elements, 06.10. - 24.11.2021)
* 1 Q&A-Session (in person, optional, 01.12.2021)
* 1 Exam (in person, 15.12.2021)
* 2 dates for project work presentations (digital, 12.01. & 19.01.2022)ATTENTION: The lectures and the project work presentations will be digital (via a conferencing tool in Moodle), while the exam and the Q&A-Session will be in person (i.e., at the university in a classroom).