Integer Programming
Contents 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 that 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 convex 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 travelling 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.
Qualifications Convex Analysis and
Mathematical Programming. Advisable prerequisite:
Mathematical Programming II. Textbooks Nemhauser, G.L. 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 2001.