KTH /
Engineering Science
/
Mathematics
/
Optimization and Systems Theory
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.
|
