In this article, we explain how to organize information of the problem that you want to solve, which will be done in the requirements definition stage, using the "school class timetable" as a motif.
By organizing the relevant information, you can begin to understand the issue's characteristics and the fact that it is a combinatorial optimization.
Let's go through how to clarify the problem to input the assignment into the computer as an optimization problem.
When teachers create timetables in schools, some use specialized software, but most are working on their hands to ensure that they can take into account the conditions without conflicts.
For the sake of setting up an example of a combinatorial optimization problem that is a somewhat complex yet easy-to-think-about, let's assume we are creating a class timetable for a subject-teacher system in a fictitious high school.
Since this is a "subject teacher system," a subject teacher must be assigned to a particular time block for a class and there must be no other conflicts.
Given these conditions and constraints, we can formulate the problem as a combinatorial optimization to determine each teacher to be assigned ($+1$) or not ($-1$) to each time block for a week.
Next, think about which conditions are necessary for solving this problem.
The requirement definition is to verbalize a problem in the real world. We want a computer to process the solution of the timetable problem, but in terms of the use of IT, the computer will not work with vague instructions. To accurately convey what we want, we start by carefully verbalizing the prerequisite information for creating the timetable, which is a real problem. We will organize the given information as follows.
There are nine subjects: Japanese, English, Mathematics, Science, Social Studies, Physical Education, Art, Music, and Life. All of these are conducted by specialized teachers. There are eight teachers each for Japanese, English, and mathematics, and four each for the other subjects.
Thus, by verbalizing the issue, the rules become clear. When the rules are clarified in words, it is easier to respond to changes in faculty or minor additions or changes in the rules.
Now we have a clear idea of what you want the computer to handle.
There is an upper limit to the number of bits the annealing machine can compute.
As you know, an annealing machine is a method that assigns one spin to one element to derive the best energy for a given pattern. So we need to know in advance how many elements to set to $+1$ or $-1$.
In this case, there are 40 teachers, 30 periods per week, and 12 classes.
Since the school is to have 12 of these classes in session at the same time, we can assume that $40 \times 12 \times 30 = 14,400$ elements (the pattern of which classes are assigned to each class frame), or spins, are needed to make the assignments.
This article is part of the ACW Skills Roadmap. Use the skills roadmap to learn with ACW.
Did you find the article helpful? Please share it with others.
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.
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.