|
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, 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
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 Matlab or Python
will be helpful, but not required.
|