Junichi Iijima

"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."