Integer and Combinatorial Optimization Course Description:
Theory and applications of integer and combinatorial optimization including enumerative, cutting plane, basis reduction, relaxation, and matching methods.
Textbook:
Integer and Combinatorial Optimization, by Laurence A. Wolsey, George L. Nemhauser. Wiley Series in Discrete Mathematics and Optimization, ISBN: 0471359432, 9780471359432.
Topic Outline and Schedule:The
following is a rough plan. As the course progresses, I may include new
topics and/or delete some of the ones listed here.
|
Topics
|
Weeks
|
|
1. Graphs
|
1
|
|
2. Elementary Combinatorial Algorithms
|
2, 3
|
|
3. Linear Programming
|
4, 5
|
|
4. Integer Programming Formulation
|
6, 7
|
|
5. Cutting Plane Algorithm
|
8
|
|
6. Branch and Bound Algorithm
|
9
|
|
7. Branch and Cut Algorithm
|
10
|
|
8. Lagrangian Relaxation
|
11
|
|
9. Integer Simplex Algorithm
|
12
|
|
10. Integral Basis Algorithm
|
13
|
|
11. Network Simplex Algorithm
|
14
|
|
12. Negative Cost Cycle Algorithm
|
15
|
|
13. Maximum Flow Problem
|
16
|
