Course Title : Applied Systems Theory

Code 10C604
Course Year Master 1st
Term 2nd term
Class day & Period Tue 1st
Location A1-001
Credits 2
Restriction No Restriction
Lecture Form(s) Lecture
Language Japanese
Instructor E. Furutani
S.Tanaka

Course Description

The course deals with mathematical methods of system optimization mainly for combinatorial optimization problems. It covers such topics as the integer optimization and its typical problems, exact solution methods including the dynamic programming and the branch and bound method, approximate solution methods including the greedy method, meta-heuristics including the genetic algorithms, the simulated annealing method, and the tabu search.

Grading

In principle, the grading will be based on the absolute and comprehensive evaluation of the reports on the subjects given in the class.

Course Goals

To acquire the knowledge on formulation of combinatorial optimization problems into integer programming problems, basic concepts, algorithms, characteristics, and application procedures of exact solution methods, approximate solution methods, and meta-heuristics.

Course Topics

Theme Class number of times Description
combinatorial optimization problems and complexity 1-2 necessity and importance of combinatorial optimization, typical problems, complexity, classes P and NP, complexity of combinatorial optimization problems, limitation of exact solution methods, necessity of approximate solution methods and meta-heuristics
exact solution methods 3 principle of optimality, dynamic programming, branch and bound method, and their applications
integer programming 2-3 formulation into integer programming problem, relaxation problem, and cutting plane algorithm
approximate solution methods 1-2 greedy method, relaxation method, partial enumeration method, etc.
meta-heuristics 5-6 local search, basic ideas of meta-heuristics, genetic algorithms, simulated annealing method, tabu search, etc. Checking degrees of understanding of all the lecture topics closes the class.

Textbook

Textbook(supplemental)

M. Fukushima: Introduction to Mathematical Programming (in Japanese), Asakura, 1996.
Y. Nishikawa, N. Sannomiya, and T. Ibaraki: Optimization (in Japanese), Iwanami, 1982.
M. Yagiura, and T. Ibaraki: Combinatorial Optimization ---With a Central Focus on Meta-heuristics--- (in Japanese), Asakura, 2001.
B. Korte, and J. Vygen: Combinatorial Optimization ---Theory and Algorithms, Third Edition, Springer, 2006.

Prerequisite(s)

linear programming, nonlinear programming

Independent Study Outside of Class

Web Sites

Additional Information

Handouts and exercises are given at the class.