MATH 7594

Integer Programming

Every three years. A Ph.D. level course that uses linear programming (5593), especially polyhedral theory, to introduce concepts of valid inequalities and superadditivity. Early group-theoretic methods by Gomory and Chvatals rounding function are put into modern context, including their role in algorithm design and analysis. Duality theory and relaxation methods are presented for general foundation and analyzed for particular problem classes. Among the special problems considered are knapsack, covering, partitioning, packing, fix-charge, traveling salesman, generalized assignment matchings. Matroids are introduced and some greedy algorithms are analyzed. Additional topics, which vary, include representability theory, heuristic search and complexity analysis. Note: This course assumes that students have the equivalent of graduate-level coursework in linear programming (e.g. MATH 5593). Term offered: spring of odd years.

Units: 3.0

Hours: 3 to 3