Discrete Optimization

Discrete optimization is a branch of optimization in applied mathematics. As opposed to continuous optimization, the variables used in the mathematical program (or some of them) are restricted to assume only discrete values, such as the integers. During the first period of the spring semester 2011, I will give a course on this topic, intended for Ph.D. students.

The course will consist of seven lectures, starting Wednesday, January 19, 2011. We will meet once a week. The lectures will be given in English.

Time and place

Wednesday, 10-12 am in MH:333. First lecture: January 19, 2011.

Lecture notes and exercises

Lecture 1: ppt pdf. Lecture 2: ppt pdf. Lecture 3: ppt pdf. Johannes UlÚn's lecture notes. Lectures 4 and 5: ppt pdf. Johannes UlÚn's lecture notes 4 and 5. Lecture 6: ppt pdf. Johannes UlÚn's lecture notes 6. Lecture 7: ppt pdf. Johannes UlÚn's lecture notes 7.

Exercise 1. Due date: February 2, 2011. Exercise 2. Due date: February 16, 2011. Exercise 3. Due date: March 2, 2011.


Participants will be assumed to have taken basic undergraduate courses in mathematics. Also, familiarity with standard optimization techniques from the undergraduate courses ''Linear and Combinatorial Optimization'' and ''Optimization'' will be helpful.


The course will focus on theory and methods for discrete optimization problems, in particular, submodular functions will play a central role. Submodularity can be regarded as the discrete analogue to convexity.
Preliminary content:
Note that the overlap with ''Linear and Combinatorial Optimization'' will be kept to a minimum and hence linear programming and its applications to, for example, assignment and transportation problems will not be covered.


The course will be based on research articles.


Hand-ins. To get a passing grade, attending 80% of the lectures is required as well.

Contact information

Fredrik Kahl
Mathematics LTH
Centre for Mathematical Sciences
Lund University
Box 118
SE-221 00 LUND

Room: 346
Direct Phone: +46 46 22 244 51
Dept. Phone: +46 46 22 285 37
Fax: +46 46 22 240 10
e-mail: fredrik@maths.lth.se