5B5860 Integer programming - practical algorithms, 5p

This course is primarily intended for graduate students in optimization and systems theory, or other graduate students with a good background in optimization.

Summary of contents

The course deals with theory and algorithms for linear integer programming problems and includes the theory of valid inequalities, duality and relaxations, general algorithms and special purpose algorithms for integer programming problems. In addition, areas like model formulation, linear programming, computational complexity and polyhedral theory are treated on a relatively superficial level.

Prerequisites

Suitable prerequisites is the course Applied mathematical programming - linear problems (5B1814) or similar knowledge.

Textbook

G. L. Nemhauser and L. A. Wolsey. Integer and Combinatorial Optimization. John Wiley & Sons, New York, 1988. (The majority of Chapters I and II are included in the course, as specified below.)

Preliminary schedule

The course will be taught in the form of 12 lectures of 90 minutes each. The preliminary schedule is given below, giving the relevant chapters from the textbook.
Lectures will be given on Tuesdays and Thursdays, 13.15-15.00, in Room 3721, Lindstedtsvägen 25, according to the schedule below.

Lecture 0 Mar 14 I.1 The scope of integer and combinatorial optimization
    I.2 Linear programming
    I.4.1 Polyhedral theory
Lecture 1 Mar 21 I.4.2-8 Polyhedral theory
Lecture 2 Mar 28 I.5 Computational complexity
Lecture 3 Mar 30 I.6 Polynomial-time algorithms for linear programming
Lecture 4 Apr 4 II.1.1 The theory of valid inequalities
Lecture 5 Apr 6 II.2.1-2 Strong valid inequalities for structured integer programs
Lecture 6 Apr 25 II.3.1,6 Duality and the value function
Lecture 7 Apr 27 II.3.7 Duality and the value function
    II.4.1-2 General algorithms
Lecture 8 May 2 II.5.1-2 Special-purpose algorithms
Lecture 9 May 4 II.5.3 Special-purpose algorithms
Lecture 10 May 9 II.5.4-5 Special-purpose algorithms
Lecture 11 May 11 II.6.1-2 Applications of special-purpose algorithms
Lecture 12 May 16 II.2.4 Strong valid inequalities for structured integer programs
    II.6.4 Applications of special-purpose algorithms

Examination

The examination is by five sets of homework assignments and an oral final exam.

Examiner

Anders Forsgren, room 3703, Lindstedtsvägen 25, tel. 790 71 27. E-mail: andersf@kth.se.
5B5860 Integer programming - practical algorithms
by Anders Forsgren.