Heuristic algorithms¶
Part 4 of the course, volume 4 of the lecture notes: chapters 29–33.
Heuristic algorithms: constructive heuristics, local search, metaheuristics and MIP-based heuristics, applied to the problems of the course.
Lecture notes (PDF) Exercises (PDF)
-
29. Heuristic algorithms: definitions
The problems and the assumptions · Primal and dual bounds · Classification of heuristic algorithms · Solution representation and search space
-
30. Constructive heuristics
The problems and the assumptions · The greedy paradigm · The 0/1 knapsack problem: which order? · The bin packing problem: first sort, then pack
-
31. Local search
The problems, the assumptions and the starting solutions · Local search: the scheme · Neighbourhoods for the four problems · First improvement and best improvement
-
32. Metaheuristics
The problems and the assumptions · How to escape from a local optimum · Simulated annealing · Tabu search
-
33. MIP heuristics for the classical problems
MIP-based heuristics · The problems and their MIP models · Rounding · Diving