Course Description

Solving optimization problems with variables restricted to take integer values, as opposed to real values, is called integer optimization. The subject, also commonly called integer programming (IP), uses concepts form various areas of mathematics and computer science including linear algebra, combinatorics, geometry of numbers, algebraic geometry, as well as algorithms and data structures. IP techniques have been used to model and solve problems in electrical power systems, airline crew scheduling, economic lot-sizing, transportation and logistics, treatment of tumors using radiation, computational biology, and many other areas. This graduate level course aims to provide a detailed treatment of the theory, solution methods, and applications of integer and combinatorial optimization. Topics covered could include IP formulations, binary expressions and conjunctive normal form (CNF), enumerative methods (branch-and-bound), theory of cutting planes, lattice-based approaches including basis reduction, algebraic geometry methods, polyhedral geometry, and computational complexity. We will also emphasize the use of state-of-the-art software packages to model and solve real-life problems. The packages AMPL, CPLEX, and Gurobi will be introduced through several homework problems and project(s). As a prerequisite, students should have taken an undergraduate level course in Linear Optimization (MATH 364, MATH 464 which is preferred, or equivalent), or obtain the permission of the instructor. Exceptions could be made on a case-by-case basis for this requirement. Familiarity with programming language(s), or packages such as Octave/Matlab will be helpful, but not required.

Syllabus