Kungl Tekniska högskolan / Optimization and Systems Theory /

This is a printer-friendly version of (none)

« Back
 


SF3843 Integer programming - practical algorithms, 7.5hp

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 linear optimization (SF2812) 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.
Lectures are given Thursdays 9.15-11.00 in Room 3721, Lindstedtsvägen 25.
Note! The lecture on September 29 will be given 10.15-12.00.

Lecture 0 Sep 22 I.1 The scope of integer and combinatorial optimization
    I.2 Linear programming
    I.4.1 Polyhedral theory
Lecture 1 Sep 29 I.4.2-8 Polyhedral theory
Lecture 2   I.5 Computational complexity
Lecture 3 Oct 6 I.6 Polynomial-time algorithms for linear programming
Lecture 4 Oct 13 II.1.1 The theory of valid inequalities
Lecture 5 Oct 20 II.2.1-2 Strong valid inequalities for structured integer programs
Lecture 6 Oct 27 II.3.1,6 Duality and the value function
Lecture 7 Nov 4 II.3.7 Duality and the value function
    II.4.1-2 General algorithms
Lecture 8 Nov 11 II.5.1-2 Special-purpose algorithms
Lecture 9 Nov 18 II.5.3 Special-purpose algorithms
    II.5.4-5 Special-purpose algorithms
Lecture 10 Nov 25 II.6.1-2 Applications of special-purpose algorithms
Lecture 11 Dec 2 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.

Optimization and Systems Theory, KTH
Anders Forsgren, andersf@kth.se