Integer Programming

Integer Programming

3-4 hours of lectures per week.

Lecturer

Kim Allan Andersen

Content

Integer programming deals with problems of maximizing or minimizing a function of many variables subject to (a) equality and inequality constraints and (b) integrality restrictions on some or all of the variables. Because of the robustness of the general model, a remarkably rich variety of problems can be represented by discrete optimization models.

It turns out that integer programming is NP-hard. This means that there are instances which are very hard to solve, and instead of using an exact algorithm one might be forced to use some kind of heuristic to solve the problem. In this course we will study the theory of valid inequalities (used to characterize the ocnvex hull of a set of integral points), the general duality theory for integer programming, and some classical examples of integer programming problems, among those the traveling salesman problem. Furthermore, we will study a few algorithms designed to solve well-structured problems. If time permits, we will also discuss complexity theory in some detail.

Prerequisites

Convex analysis and Mathematical programming. Advisable prerequisite: Mathematical programming II.

Literature

G. L. Nemhauser and L. A. Wolsey, Integer and Combinatorial Optimization, John Wiley & Sons, 1988.

Evaluation

Satisfactory answers to a number of assignments (exercises) must be produced.ECTS-credits
10.

Semester
Fall 2002.