Math 567 -- Integer and Combinatorial Optimization
Course Description
Solving optimization problems with variables restricted to take
only integral values (as opposed to real values) is called integer
optimization. Integer and combinatorial optimization forms one of the
staple areas of optimization with tremendous scope for applications to
several real life situations. Techniques from this area have been used
to model and solve problems in electrical power systems, airline crew
scheduling, lot-sizing, transportation and logistics, and more
recently in computational and molecular biology. This graduate level
course aims to provide a detailed treatment of the theory, solution
methods, and applications of integer and combinatorial optimization.
Among others, the following topics will be covered: integer
programming formulations, binary expressions and conjunctive normal
form (CNF), enumerative methods including branch-and-bound, theory of
cutting planes, duality and Lagrangian relaxation, basis reduction,
and complexity and polyhedra. As a prerequisite, students should have
taken MATH 464 (or equivalent) or obtained the permission of the
instructor. There will be no lab sessions scheduled, but the students
will be asked to work with related software as part of the assignments
and class projects.
Announcements
Check out the TSP Page at GaTech - history and other interesting facts about TSP.Homeworks
Handouts
Column Basis Reduction handoutProject
Exams
Software
MATLAB
Tutorial from Mathworks page
Another
guide to MATLAB from UBC CS.