This is an advanced level course within the specialization area Algorithms and Machine Learning.
Contents: Combinatorial search spaces and optimization problems. Exhaustive and heuristic methods. Linear and integer programming.
Notice that this course in given in English for the first time. The course contents differs to some extend from previous years.
The links to the lecture and tutorial material are password protected - if you do not know the username-password combination, please ask the lecturer.
A revised all-in-one slide package of all lectures: [one slide per page] [four slides per page]
Date | Topic | Slides |
Oct 31 | Practical arrangements. Introduction: Constraint satisfaction and optimization problems. |
|
Nov 2 | Computational Problems. Combinatorial Search Spaces. |
|
Nov 7 | Exhaustive Search I: Optimization via search. Backtracking, branch-and-bound. Complete search for SAT: DPLL, CDCL. |
|
Nov 9 | Exhaustive Search II: Complete Search for CSPs. Automated Planning. Boolean Modelling: Boolean Circuits. |
|
Nov 14 | Local Search I: Neighborhoods, local and global optima. Methods: simulated annealing, tabu search, genetic algorithms, ... |
|
Nov 16 | Local Search II: Methods continued: Ant colony optimization. Local search for SAT and CSPs. |
|
Nov 21 | Linear and Integer Programming. Modelling. Gaussian Elimination. |
|
Nov 23 | LP normal forms. Feasible solutions and polytopes. Duality. |
|
Nov 28 | Solving LPs: Simplex | |
Nov 30 | Solving IPs: LP relaxations, cutting planes, Gomory cuts. Total unimodularity. |
|
Dec 5 | Implemented systems. Course review and feedback. | |
Dec 7 | Tutorials instead of lecture | See tutorials |
A revised all-in-one package: [all tutorials and their solutions] (last revision: Dec 12)
Date | Exercise sheet | Solutions |
Nov 4 | ||
Nov 11 | ||
Nov 18 | ||
Nov 25 | ||
Dec 2 | ||
Dec 7 Wednesday 14-16! | Review of tutorials 1-5, Demos |
Here are some pointers to related books.