Mastering Discrete Optimization and Generating Solutions to Real-Life Problems, founded on the Wisdom of One’s Predecessors

I do research on discrete optimization, which is a type of theoretical mathematics. The field of discrete optimization involves designing algorithms (problem-solving processes) that will yield the most appropriate solution out of a range of combinational objects  that fall within certain constraints. It is applied to a variety of problems that appear naturally in our everyday lives. Familiar examples include car navigation, public transportation route planning, and courier delivery schedules.

Since my student days, I have worked on solving a number of different problems. The world of discrete optimization is a profound one: there are some problems that are widely known to be readily solvable in an efficient manner, and others for which we still do not know if an efficient solution can be reached, despite many years of work by mathematicians across the globe. An example of the former type is the “minimum spanning tree problem,” and an example of the latter is the “traveling salesman problem” (see Figures 1 and 2).

As the figures show, both these problems involve identifying routes connecting multiple points. They may appear not to differ greatly, but solving them requires major differences in approach.

The minimum spanning tree problem is often used when building networks. Its objective is to connect all points without omission. The problem can be solved by extending the route like branches of a tree from point to point, while eliminating the overlaps.

The traveling salesman problem, on the other hand, involves identifying the shortest or most efficient way of moving around the points and returning to the origin. In theory this problem can be solved by working through all possible routes one by one, but this method becomes impossible if the number of points to be visited exceeds 30, as the number of routes become astronomical.

In this way, even slight variations in definitions and conditions can increase the complexity of a problem significantly, and require the design of new algorithms. This is what make discrete optimization so interesting.

The discipline of mathematics is often thought to be about calculating a single predetermined answer, but that’s not actually what it is.

The process starts by thinking about how to model and formulate a real-life problem as a mathematical one, in other words, what type of discrete optimization problems to be solved. For example, even for something as simple as determining a route from point A to point B, the result will be different depending on whether you want to minimize the distance travelled or minimize the costs involved. And in some cases, there are two or more optimal routes that satisfy the conditions prescribed.

Moreover, in cases such as the traveling salesman problem, where it is difficult to come up with an optimal solution (the best solution that satisfies the conditions), researchers seek to find an approximate solution (one that meets the conditions and is close to optimal).

Where there are multiple possible solutions, it is up to our individual judgment to choose which one is ultimately to be the “correct” answer.

“Standing on the shoulders of giants” is an expression often used in the world of academic research. It means to use the trove of wisdom accumulated by the great minds of the past as the basis for making new discoveries. 

This applies to the design of algorithms as well. Rather than creating an algorithm from scratch, it is more common to apply previous methods to the discovery of a new approach. I too hope to stand on the shoulders of giants to achieve new steps forward  and contribute to our overall stockpile of wisdom.

Finding ways of solving theoretical problems in mathematics might not be immediately useful in everyday life. But it provides the guiding principles for solving a range of problems that occur in the real world.

If we understand the previous methods clearly, we can apply them to mathematical modeling of the phenomenon we want to solve, and efficiently derive solutions to complex problems.

For example, for a graduation thesis project, one student set out to create a program that matches the work shifts of instructors at a tutoring school with the attendance schedules of their students. Even if you cannot come up with an original algorithm yourself, you can gain hints from the wisdom of previous scholars. In this particular case, the student found clues to solving the problem in an arrangement of the “nurse scheduling problem”, which a classic example in mathematical modeling.

What’s important is not only to acquire fundamental, widely-applicable knowledge, but also to think for yourself about how that knowledge can be connected to the task of solving concrete problems. The experience in tackling problems with a view to practical application that students gain while still at university is sure to be of help in the challenges they face in wide society. With this in mind, I believe that it is my practical wisdom to work closely with students and assist them in finding the optimal solutions for their future.

Recently, I have been doing research in the area of “game theory,” drawing on the experience and knowledge gained through my research on discrete optimization. Game theory is not about solving puzzles. It involves scenarios where there are multiple actors (players), with each one acting on the basis of their individual judgment. Researchers analyze the reasonable strategies adopted by each player.

Imagine, for example, that you wish to travel by car from point A to point B, and there are multiple routes you can take, each with virtually identical conditions. You want to select the route with the least traffic and avoid congestion, but if other drivers act on the same basis, that route will inevitably become crowded. So you need to determine your own behavior strategically while taking the behavior of others into account.

One optimal solution to a problem like this is a method in which all players can socially behave in the most efficient manner, rather than having specific players gain an advantage. We can mathematically model each player’s decision-making and behavioral principles, and analyze them to work out how to maximize the overall satisfaction for all players.

Even if you can derive such an optimal solution theoretically, it doesn’t necessarily mean people will behave in that way in practice. On a crowded escalator, the volume of people that can be moved within in certain time is actually greater if everyone on the escalator stands completely still, rather than having one side of the escalator open for people to walk up or down. Each individual player, however, is only interested in reducing her own time on the escalator, so believes that it is faster to walk rather than stand still. As a result, the escalator cannot transport the optimal number of people.

This is why, specific states (solution concepts) arise in game theory. One example is the Nash Equilibrium. It is an equilibrium in which no player alters their strategy, because they all judge that the current state is the most reasonable, and that any alteration of their strategy will result in a worse outcome for themselves. In my research recently I was able to prove the existence of a Nash Equilibrium in a certain type of game.

Game theory is highly applicable to many everyday situations. It is useful not only in sports but also in bargaining during business negotiations, and any other situation demanding strategic thinking. In the sense that it involves searching for the optimal solution in a given situation, game theory is related to discrete optimization, and I am enjoying the new challenges it brings.