After successful completion of the course, students are able to...
understand diverse heuristic algorithms for solving hard optimization problems, to apply them in practice, and to adapt them to new problems.
This lecture deals with heuristic methods to solve optimization problems. The presented approaches are especially suitable for problems arising in practice. On the one hand such problems are often too complex to be solved in an exact way because of the increasing amount of computation time needed by conventional exact techniques. On the other hand it is often sufficient or even required to come up with a good solution in reasonable time.
In this course we primarily focus on discrete application problems and application in areas such as transport optimization, scheduling, network design, cutting and packing.
The methods considered in the course include:
- Construction Heuristics
- Local Search
- Simulated Annealing
- Tabu-Search
- Guided Local Search
- Variable Neighborhood Search
- Very Large Neighborhood Search
- Greedy Randomized Adaptive Search Procedure
- Genetic Algorithms
- Evolutionary Strategies
- Ant Colony Optimization
- Hybridization of different approaches, parallelization
- Analysis and Tuning of metaheuristics
Beside the theoretical basics this lecture focuses on practical applications and the connection of metaheuristics with problem-specific heuristics as well as some examples of suitable combinations with exact methods.
Also we will discuss how to properly tune heuristics and to evaluate and compare them by means of experiments and appropriate statistical methods.
Introduction and explanation of general methods, discussion of examples, theoretical exercises, hands-on programming exercises, presentation and discussion of solutions.
ECTS-Breakdown
20.0h Lectures
30.5h Exercises and recap of the lecture contents
60.0h Programming exercises
2.0h Exercise interviews / Examination
----
112.5h
Hotline for any questions concerning this course: heuopt (at) ac.tuwien.ac.at
Assignments / Oral Exam / Grading
During the course four assignments are given out:
- Two pen & paper exercise sheets with theoretical tasks and
- Two programming exercises where you solve an optimization problem by implementing optimization algorithms.
The pen & paper exercises should be solved alone while the programming exercises are meant to be solved in teams of two students. For all four assignments concise reports should be prepared and handed in.
The four assignments are discussed in interview sessions:
- First interview session between 13th and 14th of November 2024: pen & paper sheet 1
- Second interview session between 27th and 28th of November 2024: programming exercise 1
- Third interview session between 11th and 12th of December 2024: pen & paper sheet 2
- Fourth interview session between 14th and 15th of January 2025: programming exercise 2
In each of the interview sessions, the assignments are discussed - based on the uploaded reports. Additionally, in the course of the discussion of the pen & paper sheets, questions about the corresponding course topics are asked. Each of the Pen and Paper exercises contributes 20% to the final grade while the programming exercises contribute 30% each. To pass the course you need to achieve at least 50% of the points of the pen & paper sheets and at least 50% of the points of the programming exercises.
The registration for the interview sessions is possible on TUWEL where several time slots for each interview session will be offered.