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

• Lectures: Mondays and Wednesdays 14-16 during study period II
• Tutorials: Fridays 12-14
• Place: Exactum, seminar room B222
• Course code: 582632
• Credit units: 4 ECTS
• Lecturer: Dr. Matti Järvisalo, matti.jarvisalocs.helsinki.fi
• Course Assistant: M.Sc. Markus Heinonen
• Language: The course is given in English by default (given that there are participants who do not speak Finnish).
• Material: Lecture slides, tutorials. The course is not based on any single book. For additional references, see Further reading.

• Prerequisites: Courses from the CS curriculum which provide useful background include Design and Analysis of Algorithms, Introduction to Artificial Intelligence, and Models of Computation. Additionally, basic knowledge in linear algebra and logic is an asset.

Course Requirements

• Exam 12.12. at 16:00. The exam covers the contents of the lectures and tutorials.
• You can earn extra points for the exam by actively attending the tutorials.

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!	pdf	Review of tutorials 1-5, Demos

Further Reading

Here are some pointers to related books.

• Christos H. Papadimitriou, Kenneth Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Dover, 1998.
• Daniel Kroening, Ofer Strichman. Decision Procedures: An Algorithmic Point of View. Springer, 2008.
• Holger H. Hoos, Thomas Stützle. Stochastic Local Search: Foundations and Applications. Morgan Kaufmann / Elsevier, 2004.
• More pointers to be added