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.

Prerequisites

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.

Content

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:

• Introduction to pseudo boolean optimization. Example: Markov random fields.
• Submodular functions. Lovasz extension and convexity.
• Graph cuts and maximal flows. Ishikawa's construction.
• Semidefinite programming relaxations. Goemans-Williamanson's approximation for max cut.
• Greedy algorithms, matroids and the maximization of submodular functions.
• Graph problems: Vertex cover, set cover and submodular extensions.
• Parametric flows.
• (Optional) Linear programming relaxations. Half integral solutions and totally unimodular matrices.
• (Optional) Randomized algorithms.
• (Optional) The elimination algorithm.

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.

Literature

The course will be based on research articles.

Exam

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