IE 604 Integer Programming Select Term:
In this course, the students will learn the mathematics of discrete optimization including the representation of problems by mathematical models and the solution of these models. In computational complexity part, the concepts of polynomial computation and NP-completeness will be introduced, and equivalence of separation and optimization will be discussed. Then, basic approaches and algorithms for solving discrete optimization problems will be introduced. The branch-and-bound algorithm, the theory of valid inequalities, and the results known for simplest discrete sets that are necessary to understand the cutting planes generated by today’s commercial solvers will be covered. In polyhedral theory, the concepts of facets of polyhedra and the idea of representing the convex hull of a discrete set of points will be covered. Extended formulations and the reformulations that enable decomposition algorithms will be addressed.