# 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.

### 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.

## Contact information

Fredrik KahlMathematics 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