Introduction to My Research Interest: Combinatorial Optimization

When you are planning to go somewhere by car, you may consider "which route should I take to go to the destination as early as possible?" Such a problem of finding the best way is generally called an optimization problem. Among such problems, we are interested in combinatorial optimization problems, which are optimization problems that have combinatorial structures.

In our daily life and in wide range of industries, there are a lot of problems that can be modeled as a combinatorial optimization problem. Here are some examples:

Below is an example of packing boxes into a container.

an example layout of boxes

There are many variants of this type of problem of packing items into a container, depending on the shapes of items from 2- or 3-dimensional shapes (e.g., rectangles, polygons, boxes), and there are many real-world applications in packing, as well as cutting items form a big sheet of basic material. Below are some examples.

Below are example layouts of (1) the parts of trousers and (2) rectilinear shapes (shapes that consist only of horizontal and vertical line segments).

a cutting pattern of parts of trousers

a layout of rectilinear shapes

The target of optimization is not necessarily "efficiency". You can consider the problem of finding a longest route of railway trip that can be traveled just by a one-way ticket. This is one of the problems that attracts railway enthusiasts.

To solve such an optimization problem with a computer, you need to design a procedure to solve it, which is called an algorithm. An efficient algorithm is known to solve the problem of finding a shortest route between two places, and it is widely used in car navigation systems (after appropriate modifications so that the obtained routes are natural for drivers). On the other hand, it is believed to be hard to efficiently solve the problem of finding a shortest shopping route that starts from your home, visits all the shops you want to go, and then returns to your home, even though the two problems seem similar at first glance. It is one of our important research topics to design an efficient algorithm as in the former case, or to show that it is hard to design such an algorithm as in the latter case.

We are also interested in developing software to be used by people in universities. For example, dozens of workshops are held every year in Research Institute for Mathematical Sciences (RIMS) in Kyoto University, but the time slots and places of these seminars had been scheduled manually by a person until recently, spending a lot of time. We developed a software program to automate this scheduling process, and this software is now used in RIMS. We also developed software programs for an experimental course of our university. One of them is to assign students to subjects, considering the preferences of students, and another is to make a schedule of student groups under various constraints. These tasks had been done manually by assistant professors, spending a lot of time, but now they are automated by our software.

Our goal is to design efficient and general algorithms that can be applied to solve many real-world problems.