Toshihide Ibaraki

IFORS Distinguished Lecture

APORS Conference
New Delhi, India
December 8-10, 2003

Towards the General Engine for Solving Real World Combinatorial Problems
Toshihide Ibaraki
Kyoto University, Japan

Abstract

There is a common understanding that computers can solve any problem in this world. Although this is false in the rigorous sense, there have been attempts in this direction, such as GPS (general problem solver) in artificial intelligence and mathematical programming in operations research, so that some wide class of problems can be handled in a unified framework.

We have also been building a system that consists of solvers for various standard combinatorial problems, in the hope of providing a general engine for many types of combinatorial problems abundant in the real world. The system is an outcome of the observations in the algorithm and complexity theories that

* a single solver (e.g., integer programming) cannot handle all combinatorial problems, but on the other hand,
* algorithms based on metaheuristics (e.g., local search, iterated local search, tabu search and genetic algorithms) can be efficient and robust enough to solve appropriately defined standard problems.

In this approach, the choice of standard problems is very important. So far we developed metaheuristic algorithms for

* constraint satisfaction problem (CSP)
* resource constrained project scheduling problem (RCPSP)
* vehicle routing problem (VRP)
* 2-dimensional rectangle packing problem (2PP)
* generalized assignment problem (GAP)
* set covering problem (SCP)
* maximum satisfiability problem (MAXSAT)

Each of these standard problems is very general, and furthermore it can admit additional side constraints and secondary objective functions. Nevertheless, the algorithms are made efficient by exploiting special structures of such standard problems.

The system is still under development, but has been successfully applied to various real world problems such as production scheduling in factories, work force scheduling, and routing problems of ships and vehicles.

About the Awardee

Toshihide Ibaraki received the B.E., M.E., and Ph. D. degrees in Engineering from Kyoto University, in 1963, 1965 and 1970, respectively. Since 1969, he has been with the Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University, except for two and a half years from 1983 to 1985, during which time he was with Department of Computer and Information Sciences, Toyohashi University of Technology. Currently, he is a professor of Kyoto University. From April 2001 to March 2003, he was the dean of Graduate School of Informatics, Kyoto University.

He has held a number of visiting appointments with University of Illinois, University of Waterloo, Simon Fraser University, Rutgers University, University of Canterbury and others. He is the author of “Enumerative Approaches to Combinatorial Optimization”, Baltzer AG., a coauthor of “Resource Allocation Problems: Algorithmic Approaches”, MIT Press, and the author of several books in Japanese. His interest includes algorithms, optimization, computational complexity and their applications.