TOP > Research > Department of Systems and Social Informatics > Department of Computer Science and Mathematical Informatics > Mathematical Modeling and Analysis Group > YAGIURA, Mutsunori

Comprehensive List of Researchers "Information Knowledge"

Department of Computer Science and Mathematical Informatics

Name
YAGIURA, Mutsunori
Group
Mathematical Modeling and Analysis Group
Title
Professor
Degree
Dr. of Engineering
Research Field
Combinatorial optimization / Metaheuristics / General problem solver
YAGIURA, Mutsunori

Current Research

Metaheuristics for Combinatorial Optimization Problems
OUTLINE
Combinatorial optimization problems, which arise in such applications as scheduling, network optimization, and so forth, include a wide range of important issues in the field of informatics and engineering; hence it is crucial to devise efficient algorithms for them. However, many are known to be NP-hard, and obtaining their exact optimal solutions is computationally intractable.
One realistic way to deal with such problems is using heuristics, which can quickly obtain good (although not necessarily optimal) solutions. Greedy methods and local searches are basic methodologies often used for this purpose. As the speed of computers continues to grow rapidly, on recent computers such basic methods usually require very short computation time. This motivates people to spend more computation time to obtain better solutions. A recent trend uses metaheuristics for this purpose, which gives frameworks for combining basic heuristic tools into more sophisticated algorithms. Included among representative metaheuristic algorithms are genetic algorithms, simulated annealing, tabu search, and so on.
Our research objectives include devising efficient algorithms based on metaheuristics and developing general problem solvers that can handle a wide range of problems.

TOPICS

Efficient algorithms for representative problems
Representative combinatorial optimization problems often arise as the basic substructures of real problems, and so it is important to devise efficient algorithms that can obtain high quality solutions in short computation time. We have proposed sophisticated metaheuristic algorithms for such important obstacles as the generalized assignment problem, the set covering problem, etc. Our algorithms incorporate elaborate techniques including ejection chain neighborhoods, adaptive control of parameters, Lagrangian relaxation, and efficient data structures to search for large neighborhoods. As a result, our algorithms achieve competitive results with state of the art algorithms and can deal with large-scale problem instances with up to 1, 000, 000 variables.

General problem solvers based on metaheuristics
We are also developing general problem solvers that can deal with a wide range of problems. Since it takes much time and effort to develop a heuristic algorithm from scratch, it would be more convenient if we had solvers applicable to various problems. For this purpose we have been developing metaheuristic algorithms for the generalized variants of the vehicle routing problem with time windows, the rectangle packing problem, the cutting stock problem, and so on.

Wooden puzzle
We made the above wooden puzzle so that people can experience the difficulty of combinatorial optimization. The objective of the puzzle is to arrange the rectangular pieces to minimize wasted space. The nine pieces of the puzzle are sufficient to experience the difficulty of combinatorial problems.

FUTURE WORK
Metaheuristics receives much attention due to its effectiveness; however, very little is known about its theoretical aspects. Giving a theoretical explanation to its success as well as devising practical metaheuristic algorithms are important future directions of our research.
Figure : Wooden packing puzzle

Figure : Wooden packing puzzle

Career

  • 1993 Master of Engineering, Kyoto University
  • 1994 Assistant Professor, Kyoto University
  • 2000 Associate Professor (Lecturer), Kyoto University
  • 2005 Associate Professor, Nagoya University
  • 2011 Professor, Nagoya University
  • Best paper award from ORSJ

Academic Societies

  • ORSJ
  • IPSJ
  • IEICE
  • SSJ
  • INFORMS
  • ACM

Publications

  1. Combinatorial Optimization " Focusing Mainly on Metaheuristics (in Japanese), Asakura (2001).
  2. An ejection chain approach for the generalized assignment problem, INFORMS Journal on Computing, Vol. 16, No. 2, pp. 133-151 (2004).
  3. Effective local search algorithms for routing and scheduling problems with general time-window constraints, Transportation Science, Vol. 39, No. 2, pp. 206-232 (2005).