Make the most out of information "combination maximization"

Mutsunori Yagiura
Professor

【Graduate School of Informatics】
Department of Mathematical Informatics
【School of Informatics】
Department of Natural Informatics

The "best combination" is the key to work efficiency and conservation of resources

-What kind of research do you do?

"Combination optimization" which seeks to find the best solution and method wherever possible based on the various conditions we are given. A familiar example would be thinking of a route with the shortest time possible to take when couriers, etc., deliver goods. This is the type of thing we study. The study is mainly thinking about "geometrical packing" such as how do we pack given multi-shaped items into containers without wasting space? How do we efficiently cut out parts for clothes from a large piece of fabric? How do we load trucks and airplanes leaving no space? Also, when considering the problem of how to cut metal sheets to produce vehicles without wasting any material, simply reducing the waste by 1% can reduce costs by several hundred million yen per annum. This type of problem with production efficiency is important because it also links to environmental problems.

In business, for example, there are places that develop software to create work schedules for nurses. The hospital needs nurses to be present at all time slots. However, there are restrictions such as nurses only being able to work within the scope of the laws that prevent them from working beyond their physical means. Thinking of the best work schedule while considering both these factors is a most difficult skill. Combination optimization techniques are used to enable this type of schedule to be designed automatically.

The ability required to design algorithms is approximately equal to logical thinking to solve puzzles

-What kind of knowledge is required? What type of person is it best suited?

We use mathematics and programming knowledge but you do not necessarily need to be good at both. I think that if you like one of them, it will lead you to liking combination optimization. To resolve some problem using a computer, you have to make an "algorithm" that decides how the computer works. An "algorithm" is a calculation procedure performed to achieve a purpose such as resolving a problem and is similar to procedures or specifications to write a program. A program has various language rules where the syntax must be used correctly. However, to ensure that algorithms can be written in any language only the important part of the procedure is written using terms that can be understood by humans such as "substitute 7 for variable x". An image of an algorithm is that it can be written on paper with a pencil and then tested to see if it works properly on a computer. Mathematics is also used to prove that the algorithm works correctly and fast. The history of the algorithm is very old. It was used during the B.C. era to discover prime numbers and look for the greatest common divisor, etc. It was originally a mathematical term.

I think that people who like puzzles such as Sudoku or nonograms are also suited to this field of research. This is because puzzle elements such as attacking a problem from the least likelihood and logically discarding unlikely choices to finally arrive at an answer, is available in combination optimization research.

Technology that supports various fields such as car navigation, railroad diagrams and professional sports

-In what form does your research appear in our lives?

The easiest one to see is car navigation systems that search for the shortest route to our destination. It is said that if we did not have an algorithm for this, car navigation systems would not have existed. How should we put together railroad diagrams so we can have good connections between trains and efficiently manage carriages? In professional sports such as baseball or soccer, how should we set up home and away games throughout the entire league to ensure efficient movement and equality? Furthermore, how can we justify English text in documents using document layout software, which is something scientific type people often use? Optimization is applied to these scenarios and supports various fields.

I cannot forget the pleasant feeling when I was able to prove something through trial and error, this is why I cannot stop

-Why have you set your sights on this research?

Mathematical engineering was something I chose for the simple reason that I like mathematics and I was pulled in by the fact that it has to do with numbers so I thought it would be interesting and after joining I happened to encounter this field in the research department (laughs). One of the reasons for choosing this field is that optimization is a study that is useful for making various items efficient such as production, distribution and services and I believed that its attraction would lead me to further study and continued research. Actually, I have already told some of my students this but the reason I chose the research department is that I like computers and mathematics and also for other various reasons or other (laughs). However, there are many people who see this field as interesting because you can see its application compared to pure mathematics.

When I had good results from an experiment, the pleasant feeling of when I was able to prove something after trial and error, is significant. Speaking of the metal sheets at a vehicle manufacturing plant as I mentioned earlier, the metal sheets are not of a uniform thickness and the manufacturer needs to cut from the center of the sheet, etc., as much as possible depending on the product. It is a difficult enough problem to simply reduce waste but the problem becomes increasingly difficult when adding this type of constraint. When the problem becomes difficult like this, being able to solve the problem brings even greater pleasure. I cannot stop working on such problems (laughs).

Speaking of nurses, when optimizing only with a plan to create a schedule that satisfies the needs of the hospital to have the least amount of nursing staff, this is good for the hospital but it will probably not be necessarily pleasant for the nurses who work there. It is actually important to consider various factors, for example, consideration for equality between nurses is often requested but this is not easy. My mother majored in psychology and I thought about doing it as well. It might be possible to do something about this by combining psychology, for example, when thinking about whether there is a feeling of equality.

Just having information has no meaning. Change it into alive information and create new value

-Do you have a message for students wishing to join the School of Informatics?

Computers when I was a student cost over several million yen and had a lower performance than current day laptops. I used this type of computer to perform experiments. Tasks that were theoretically interesting but could not be used or were said to be impossible because they would take too much time can now be performed. This is because it has become easier to obtain high performance computers that can achieve this. Furthermore, it is now possible to accumulate all information including traffic information, weather information and information about people shopping in real time at large volume. This means that we can carefully optimize based on even more accurate data. I believe that this will definitely advance further in the future. Whether we can capitalize on this technology depends on whether we can create good algorithms.

Currently a lot of information is available. However, just having information is not enough to use it. We have to extract knowledge that has some meaning from the information and then optimize based on the given information or find a good strategy to give it meaning. With this in mind, I think you could say that we are researching based on the question "how can we use this information?" I would definitely like people who want to use the technology of the future and are enthusiastic towards creating things that produce new value, such as devices that surpasses the car navigation system, to come and study with us.