Computational Intractability: NP-completeness and integer programming with scheduling applications
Spring 2013Description:
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
April 5, 2013