IE 511

Optimization of linear systems over discrete decision domains. Topics to be covered include Modeling, Polyhedral theory, Integral Polyhedra, Totally Unimodular Matrices, Total Dual Integrality, Computational Complexity, Cutting plane method, Branch and Bound method, and Lagrangian Dual. Structured integer programs involving Matchings, Knapsack, Cuts and Matroids will be studied as applications. Course Information: 4 graduate hours. No professional credit. Prerequisite: IE 411 or MATH 482.

This course is about the optimization of linear systems involving discrete variables. After introducing Integer Linear Programs (ILPs) via examples, we will review the key results in Complexity Theory. We will identify conditions that yield tractable families of ILPs, and we will look at algorithms that solve the general ILP instance. Some programming experience is desirable, but not required. Topics covered include Optimization of linear systems involving integer variables and discrete alternatives. Modeling; computational complexity; matroids; branch and bound methods; Langrangian and surrogate duality; cutting plane methods and polyhedral theory; special structured problems such as knapsack, set packing and covering, and traveling salesman problems. Prerequisite: IE 411 or MATH 482.

8/23/2016