IE 511 -
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.