Computational Intractability: NP-completeness and
integer programming with scheduling applications
Spring
2010
Prof.
David
Avis
Thursday
8:45
-
10:15
Description:
Most practical problems in discrete optimization, such as scheduling problems, fall into the NP-hard class of computationally intractable problems. While this means that we cannot normally expect efficient algorithms for these problems, they must nevertheless be solved. Scheduling problems, for example, must routinely be solved by transportation companies, sports schedulers, computer hardware, etc. Approaches to solving intractable problems often involve approximation, heuristics, and/or the use of exponential algorithms such as integer programming. In this course we focus on the latter approach, which has recently shown impressive success in solving rather large-scale problems.
This course begins with a concise review of
NP-completeness and an introduction to linear and integer programming,
including cutting plane algorithms. In the second part of the course,
we apply these tools to a wide variety of problems related to
scheduling.
Students will develop their own models for various applied problems and
attempt to solve them using state-of-the-art software.
Send comments/questions to avis@i.kyoto-u.ac.jp
March 17, 2010