Discrete Optimization (Autumn 2011)

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.

Course Information

Course Requirements

Lectures

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]

solutions/solutions1
Date Topic Slides
Oct 31 Practical arrangements.
Introduction:
Constraint satisfaction and optimization problems.
pdf
Nov 2 Computational Problems.
Combinatorial Search Spaces.
pdf
Nov 7 Exhaustive Search I:
Optimization via search.
Backtracking, branch-and-bound.
Complete search for SAT: DPLL, CDCL.
pdf
Nov 9 Exhaustive Search II:
Complete Search for CSPs.
Automated Planning.
Boolean Modelling: Boolean Circuits.
pdf
Nov 14 Local Search I:
Neighborhoods, local and global optima.
Methods: simulated annealing, tabu search, genetic algorithms, ...
pdf
Nov 16 Local Search II:
Methods continued: Ant colony optimization.
Local search for SAT and CSPs.
pdf
Nov 21 Linear and Integer Programming.
Modelling.
Gaussian Elimination.
pdf
Nov 23 LP normal forms.
Feasible solutions and polytopes.
Duality.
pdf
Nov 28 Solving LPs: Simplex pdf
Nov 30 Solving IPs:
LP relaxations, cutting planes, Gomory cuts.
Total unimodularity.
pdf
Dec 5 Implemented systems. Course review and feedback. pdf
Dec 7 Tutorials instead of lecture See tutorials

Tutorials

A revised all-in-one package: [all tutorials and their solutions] (last revision: Dec 12)

Date Exercise sheet Solutions
Nov 4 pdf pdf
Nov 11 pdf pdf
Nov 18 pdf pdf
Nov 25 pdf pdf
Dec 2 pdf pdf
Dec 7 Wednesday 14-16! pdfReview of tutorials 1-5, Demos

Further Reading

Here are some pointers to related books.