SUBJECT
Title
Integer programming II
Type of instruction
lecture
Level
master
Faculty
Part of degree program
Credits
3
Recommended in
Semesters 1-4
Typically offered in
Autumn/Spring semester
Course description
Sperner systems, binary sets defined by inequalities. Lattices, basis reduction. Integer programming in fixed dimension. The ellipsoid method, equivalence of separation and optimization. The Lift and Project method. Valid inequalities for the Traveling Salesman Problem. LP-based approximation algorithms.
Readings
- G.L. Nemhauser, L.A. Wolsey: Integer and Combinatorial Optimization, John Wiley and Sons, New York, 1999.
- D. Bertsimas, R. Weismantel: Optimization over Integers, Dynamic Ideas, Belmont, 2005.