When applying an annealing machine solution of an optimization problem to a real-world problem, the ultimate goal is to improve the user's work through the optimization process.
Even engineers who have experience in the sequence of defining requirements for real-world problems that users have, formulating them, and then executing the annealing machine, seem to find difficulty in defining requirements. In defining requirements for optimization processing, business knowledge (expertise possessed by users) and knowledge of optimization processing (expertise possessed by engineers) need to be brought together and discussed in depth toward a solution. In such cases, various problems that cannot be faced by solving optimization problems on the desk with an annealing machine arise.
This column is not strictly a full topic, but I hope to introduce some of the unique difficulties in defining requirements for optimization processes, and to bring you closer to the practice.
Defining requirements is a term often used in system development. When creating any system, the first step is for the developer to understand what the user wants to achieve through the system development, and while detailing the items to be considered, establish the necessary functions and performance in line with the user's business, as well as the policy to meet the budget and schedule. Once the requirements definition is complete, the system development process proceeds to a process called external design.
How does defining requirements for optimization processes differ from system development? In system development, the man-hours required to develop all functions, including hardware and its control software, are often enormous, so it is necessary to define the requirements as accurately as possible at the outset.
On the other hand, since there are conditions that cannot be defined in a single step in the requirements definition for optimization, it can be said that an approach similar to agile development, in which the requirements are formulated and executed without perfection, and then returning to the requirements definition, often fits well.
The formulation of a model to extract the performance of the annealing machine most efficiently while satisfying the user's business requirements, it is desirable to go through the optimization flow many times, from requirement definition to formulation to requirement definition, and from formulation to execution to formulation, in order to improve the degree of accuracy.
Let me give you an example of what happened when the COVID-19 epidemic led to shift work optimization at a Hitachi research laboratory. While we needed to limit the number of people coming to work, there were many people who needed to come to work for experiments, and we needed to decide who to let come to work and when.
Initially, we started by setting a maximum number of people in a room, and then each researcher would enter his/her preference (e.g., "I definitely want to do an experiment on this day," or "I want to do an experiment if possible, but not absolutely," etc.), and an annealing machine would be run to determine the shifts.
However, when we actually started operating the system, we began to receive requests for restrictions on who could work together (for example, a newcomer and an instructor) and, conversely, restrictions on who we did not want to work together (for example, two managers could not work at the same time because it would be a problem if they contracted coronas at the same time). Also, they have expressed a desire to work at least three days out of the week, although they do not have to specify the days they work.
Thus, the shift optimization application was upgraded to incorporate new constraints based on the researcher's wishes.
In addition, we are required to make adjustments to operate the business, rather than just hearing about the Ising modeling. In this case, we had to create a week's worth of shifts through optimization, but some people wanted their shifts by Thursday of the previous week, while others wanted to wait until Thursday to submit their preferences. In practice, we closed the input of requests on Thursday evening and released the shifts the next day, Friday morning.
Thus, in the requirements definition stage, it is necessary not only to formulate for optimization, but also to consider the conditions necessary for operation in the business. Only then can users feel that they have made an improvement when actually applying the system. As a result, we were able to demonstrate that shift work at the laboratory is viable and effective because of the speed of the optimization process.
In some cases, when a user is asked what they want to optimize to create a cost function for the Ising model it can be difficult for the user to give an answer. For example, if there is a user who wants to optimize a timetable, and the engineer did not know what the timetable was, they might ask the user
"You listed a lot of constraints, but I haven't yet heard from you what indicators you want to optimize. What do you want to optimize?"
When asked this, the user pondered for a moment and then said, "I just want to make a timetable.... What on earth do you want to know?
What this means is that this engineer wants to know what index to minimize or maximize in order to create a cost function for the Ising model, but the timetable problem consists only of constraints, and the timetable that this user wants to create is not a problem of the nature of maximize xx or minimize xx.
no such engineer exists who does not know what a timetable is, so this can be said to be an extreme analogy, but it is important to discard assumptions when interviewing the user. As the user may give them a combinatorial optimization problem that they have never seen before. It is also important to accumulate examples of what kind of optimization problems exist and to share them with the world.
Now that the existence of annealing machine optimization technology is becoming known to the public, users are increasingly attempting to apply annealing machines to tasks that used to be hand-computed by humans. However, in some cases, as a result of proceeding with the definition of requirements with the aim of solving the problem with an annealing machine, it turns out to be a linear problem (for details, see the section on Math for Annealing Machines).
If no second-order terms appear in the formulation, then it is a linear problem, and if second-order terms appear, then an annealing machine may be a good fit, but it is sometimes difficult to say until you solve the problem and compare the degree of effectiveness. During the optimization process, even if you have reached the execution stage, it is assumed that you will have to start over from the selection of optimization method, and repeating the optimization flow many times will lead to success.
Appropriate application of the best method to the requirements, which are the result of many clues obtained through a vast amount of communication, will lead to user value. By experiencing a variety of problems, we will be able to identify problems where annealing machines can be used effectively, and this will lead to the creation of new case studies that will contribute not only to user value, but also to new results that will make a difference in the world.
Combinatorial optimization will be explained by using two easy-to-understand examples of familiar combinatorial optimization problems. The importance of finding and using fast solution methods for combinatorial optimization processes in an IoT society will also be discussed.
In the wake of the COVID-19 epidemic, we present a use case in which an annealing machine is used to create shifts for researchers under constraints that take into account the risk of infection.
This article presents a use case in which an annealing machine is used to formulate a reinsurance portfolio that leverages the vast amount of data held by an insurance company to address natural catastrophe risks.
For beginners, this article explains the procedures and key points of the process of solving optimization problems with an annealing machine. The process involves dividing the problem into four stages: "organizing problem and defining problem," "formulation," "input data preparation," and "executing CMOS annealing machine".
This article provides an easy-to-understand explanation of the mathematical assumptions you need to understand, focusing on "quadratic" and "discrete," which are some of the characteristics of the problems that annealing machines excel at solving.