**********************************

Interviewee: Toshihide Ibaraki

Interviewer:  Hiroyoshi Miwa

Interview Date: February 2009

**********************************


*** Your full name, address and e-mail address:

Toshihide Ibaraki
Email: ibaraki@kwansei.ac.jp

*** Your highest degree, awarding institution and year:

Doctor of Engineering, Kyoto University, 1970.

*** How many research papers have you published (includingpapers accepted for publication)? How many of them in the field of optimization?

About 400 papers (in English and Japanese) have been published in Journals and international conferences. About half of them are related to the field of optimization and its applications.

Published 3 books in English, and 11 books in Japanese. Contributed to chapters in many other books. Edited a number of books and journal issues.

*** When and how did you get interested in optimization?

When I was an undergraduate student, i.e., early sixties, there was no course on optimization in the department of electrical engineering of Kyoto University, where I was studying. My first exposition to optimization was when I read the book "Applied Dynamic Programming" written by R. Bellman and S. E. Dreyfus. I was quite impressed by its generality and many practical applications. My research topic for undergraduate thesis was logic design of a computer by using Boolean algebra, which then led to the topics of threshold logic of my master thesis. This area was invented by several Japanese researchers including S. Muroga, then a professor at Univ. of Illinois. A threshold function is defined by a linear inequality, and its synthesis is naturally related to linear programming. I was then invited to Univ. of Illinois in the late sixties to work with Prof. Muroga. During this time I studied linear programming and integer programming for the first time. As logic design is inherently discrete, many problems in this area can be handled as integer programming problems. It was the time when R. E. Gomory proposed cutting plane methods and E. Balas proposed branch-and-bound approach. We used integer programming to design optimal logic circuits using NOR gates, as well as to solve other applications. I was gradually attracted into integer programming algorithms and, more generally, combinatorial optimization, rather than particular applications in logic design.

*** What kinds of topics excite your research interests? How did you develop these interests?

My interest was then shifted to algorithmic aspects of combinatorial optimization, in particular dynamic programming and branch-and-bound algorithms. In this period, R. Karp wrote a fascinating paper that formulated dynamic programming as a finite automaton with a monotone cost function. I was quite excited with this observation, and I wrote a number of papers in this line. Many of them are included in my book "Theory of Combinatorial Optimization" written in Japanese and published from the Inst. of Electronics and Communication Engineers of Japan. I also made similar study on branch-and-bound algorithms in a general framework. My results in this area are summarized in the book "Enumerative Approaches to Combinatorial Optimization" published from Baltzer as two volumes in Annals of Operations Research.

In the middle seventies, S. Cook and R. Karp came up with a notion of NP-completeness, creating a new field of computational complexity. This has immediately attracted many researchers, and I was among the early people who applied the theory to many problems. I spent most of the time in the eighties developing algorithms for integer programming, fractional programming, scheduling problems and others, and proving NP-hardness of various combinatorial optimization problems.

Because the structure of graphs and networks can be found in many problems in the real world, topics such as network flows, cuts, connectivities also became my favorite subjects, which we studied mainly from algorithmic point of view. In this area, H. Nagamochi is a powerful partner and, with him, we recently published "Algorithmic Aspects of Graph Connectivity" from Cambridge University Press.

From the nineties to the first decade of the new century, my research interest has been gradually shifted to the application side, and we tried to develop heuristic algorithms for various combinatorial optimization problems. In these years, local-search based heuristic algorithms, now called metaheuristics, became popular, although they do not have solid theoretical basis. These algorithms include genetic algorithms, simulated annealing, tabu search and so forth. As it is very complicated and time-consuming to develop good metaheuristic algorithms, we were inclined to target those problems as general as possible, so that our products can be used by many people to solve their problems. For this purpose we have chosen such standard problems as constraint satisfaction problem, resource constrained project scheduling problem, vehicle routing problem and generalized assignment problem, to develop metaheuristic algorithms. Some of these turned out to be very useful and are currently used by many practitioners, partly because our codes are included in the commercial package NUOPT released from Mathematical Systems Inc. I am glad to see these outcomes. Jointly with M. Yagiura, we wrote a textbook "Combinatorial Optimization - Metaheuristics" published from Asakura Shoten.


*** What is one of the most interesting topics you have studied?

Like many other people, I was first interested in theoretical work, but later in applications. I think that the background I acquired from theoretical study is very useful for the purpose of developing algorithms for applications. For example, metaheuristic algorithms as mentioned above are too complicated to permit theoretical treatment, but they consist of many subparts, each of which may be theoretically evaluated. Without such help of theory, it would have not been possible to develop effective metaheurisitc systems. If you ask what I am at present most interested in, I would say it is how to apply those algorithms to solve real world problems.

*** What are your most representative papers or books?

In addition to some books I have already mentioned above, I wrote textbooks (in Japanese) such as "Algorithms and Data structures" and "Discrete Mathematics for Informatics", which are fortunately adopted in several universities. It is a fun to imagine the scene where young students are studying these topics while consulting the textbooks I wrote.

*** What are the most interesting unsolved problems in the optimization branch you are working on?

If you ask me to pick up just one problem, it is the problem of dualizing a monotone Boolean function. I encountered with this problem when I was studying database theory, but it is related to many other optimization problem. It is not known yet whether the problem is solvable in polynomial time or not, although M. Fredman and L. Khachiyan gave a pseudo polynomial time algorithm. Some people believe that, if P is not NP, this problem lies between two classes P and NP. But it may be possibly in P. This is quite intriguing and I would like to know the result.

*** What is your message to the young researchers?

Find out an interesting problem of your own, and pursue the goal. However, do not hesitate to change the goal, if you think it more appropriate and justifiable. Wide knowledge is necessary to justify your direction, of course, and it is your responsibility to acquire such knowledge.

*** Other comments?

I would like to emphasize my luck that I could work with a number of talented colleagues and students. Most of my work was done jointly with those people, though I do not name them individually here. I really enjoyed working with them, and I am grateful for their great help.