Discrete Optimization

Abstract

This course gives an introduction to discrete optimization problems.A discrete optimization problem is the task to optimize a linear function over the integer points in a polyhedron. This topic is very rich in terms of the underlying theoretical tools that one can use to understand and solve such problems.

Objective

The goal of this course is to obtain an understanding of the theory of discrete optimization that underlies algorithms to solve such problem. Discrete optimization is a rich topic that includes lattice theory, approximation algorithms and polyhedral combinatorics.

Content

Part 1: From linear to integer optimization Linear and Integer optimization problems are strongly related via underlying polyhedra. This is the classical setting of polyhedral combinatorics. Part 2: Binary optimization We study various topics and techniques related to linear problems in variables that can attain values zero or one only. This is the classical setting of approximation algorithms and cutting plane procedures. Part 3: General integer optimization This part is devoted to a study of integer optimization in general integer variables. We will discuss lattice theory and the theory of integral generating sets in cones to understand the subject.

Resources