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 lotsizing,
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
(branchandbound), theory of cutting planes, latticebased
approaches including basis reduction, algebraic geometry
methods, polyhedral geometry, and computational
complexity. We will also emphasize the use of
stateoftheart software packages to model and solve
reallife 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
casebycase basis for this requirement. Familiarity with
programming language(s), or packages such as Octave/Matlab
will be helpful, but not required.
