Mathematical Heuristics for Discrete Optimization Problems

Inhalt

In real-world applications, optimal decisions need to be taken within a complex system. Often these problems can be modeled with all necessary constraints as a discrete optimization problem. However, computing an optimal solution for such a problem is in many cases too time consuming. In this lecture, we focus on methods – so called heuristics – to obtain solutions in a short period of time. However, this comes at the cost of not obtaining optimal solutions. We will focus on single-population based heuristics and analyze these heuristics for different classical discrete optimization problems according to their performance. In many cases, we will prove that even simple heuristics produce an approximate solution. The goal of this course is to equip the students with a broad overview on different methods and on different classical optimization problem. This will enable them to solve real-world problems more efficiently. Methods adressed in the course include Local Search, Greedy Randomized Adaptive Search Procedures, Variable Neighborhood Search, Tabu Search, and Simulated Annealing.

Lernziele

• Students know standard heuristics
• Students can define an approximation ratio
• Students know optimiztion problems that are solved heuristically in practice, and they can name suitable heuristic methods for those.
• Students can select appropiate heuristic methods for specific problems. They can then implement those heuristics, adapt them to a specific context and use them to solve real-world problems
• Students can evaluate the quality of solutions
• Students can evaluate the quality of heuristics as solution method for specific problems based on theoretical properties and practical solution quality
• Students reflect on their ability to use algorithmic ideas in practice
• Students can select suitable heuristics for specific problems and use them to solve the respective problems.

Empfohlene Vorkenntnisse