IE511: Integer Programming (Spring 2024)
Instructor: Dr. Yatharth Dubey
Times: Lecture - Tuesday and Thursday 9:30-10:50am CT; Office Hours - by appointment (email)
Location: 206 Transportation Building
Course Description: The course will provide a comprehensive treatment of integer optimization including theory, algorithms and applications at the introductory graduate level. Some specific topics to be covered are: integer programming models, linear inequalities and polyhedra, perfect formulations, cutting planes, branch-and-bound, reformulations and relaxations.
Textbooks (recommended): Integer Programming by Conforti, Cornuéjols, Zambelli; Integer Programming by Wolsey; Theory of Linear and Integer Programming by Schrijver
Prerequisites: Mathematical maturity at the level of a beginning graduate student (ability to understand and write proofs) will be assumed. Familiarity with reading and writing mathematical proofs (e.g., proofs by induction and contradiction) and basic knowledge in linear algebra are required. Prior coursework in linear programming is highly recommended and exposure to basic combinatorics will be helpful.
Grading Policy: 60% homework; 40% exams
UIUC Academic Integrity Policy: Please see this link
Schedule:
Week 1 (1/16, 1/18): IP models, relaxations
Week 2 (1/23, 1/25): IP models, relaxations
Week 3 (1/30, 2/1): IP models
Week 4 (2/6. 2/8): Computational complexity
Week 5 (2/13, 2/15): Computational complexity, polyhedral theory
Week 6 (2/20, 2/22): Polyhedral theory
Week 7 (2/27, 2/29): Polyhedral theory
Week 8 (3/5, 3/7): Integral Polyhedra, MIDTERM
Week 9 (3/12, 3/14): NO CLASS - SPRING BREAK
Week 10 (3/19, 3/21): Integral Polyhedra
Week 11 (3/26, 3/28): Total Unimodularity
Week 12 (4/2, 4/4): Total Dual Integrality
Week 13 (4/9, 4/11): Forests and spanning trees, exact solution/branch-and-cut
Week 15 (4/16, 4/18): Cutting planes, Gomory-Chvatal cuts
Week 16 (4/23, 4/25): Covers and lifting
Week 17 (4/30): Lagrangian relaxation, Dantzig-Wolfe reformulation