SUBJECT
Title
Integer programming I
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
Basic modeling techniques. Hilbert bases, unimodularity, total dual integrality. General heuristic algorithms: Simulated annealing, Tabu search. Heuristic algorithms for the Traveling Salesman Problem, approximation results. The Held-Karp bound. Gomory-Chvátal cuts. Valid inequalities for mixed-integer sets. Superadditive duality, the group problem. Enumeration 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.