Organizing problems and defining requirements

Overview

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.

Topic: Automatically Create "School Class Timetable"
STEP 1. verbalize the problem (requirements definition)
STEP 2. write down and define what you want the computer to handle
STEP 3. Estimate the number of bits required

Topic: Automatically Create "School Class Timetable"

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.

Attention!

Timetabling is a combinatorial optimization problem that determines the best combination of a teacher for a subject (e.g., Mr. John's math) and a time block (e.g., 5th Grade, Class 2, the 2nd block on Tuesday). We will set ($+1$) if the teacher is allocated to the time block or ($-1$) if not.

Next, think about which conditions are necessary for solving this problem.

STEP1. verbalize the problem (requirements definition)

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.

Subjects and teachers

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.

Classes

There are two classes each for six grades, for a total of 12 classes.
Note that the number of subjects is the same from grade to grade and class to class, and subject teachers can be assigned to any grade and class.

Working duty

Each teacher must work five blocks or more per week.

Timetable

The maximum number of classes conducted in one day is six.
There are five days a week, from Monday to Friday.

Constraints

Each timetable must allocate five blocks each for Japanese, English, and mathematics, and two blocks each for the other subjects.
No more than two consecutive blocks of the same subject are in the same class.
To avoid overwork for teachers, the same teacher must not work for more than five consecutive blocks.

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.

STEP 2. write down and define what you want the computer to handle

(1) Let the teachers be group A, and assign a code number starting from "A" to each subject teacher.

Japanese A01~A08, English A09~A18, Mathematics A19~A27,
Science A28~A31, Social Studies A32~A39, Physical Education A40~A44, Art A45~A49, Music A50~A54, Life A55~A59

(2) Let the time blocks be group B, and assign a code number starting from "B" to each blocks.

Class number 01-12
Number the frames Monday 1st period = 01, 2nd period = 02, Tuesday 1st period = 07, Friday 6th period = 30
Class 1, Monday 1st period = B0101, 2nd period = B0102, Tuesday 1st period = B0107, Friday 6th period = B0130

(3) Assign each element of group A (from A01 to A40) to any element of group B (B0101 to B1230)

(4) This process must follow the constraints below;

A teacher cannot be allocated to multiple blocks held at the same time.
In one timetable (one class), any five blocks must have teacher numbers selected from A01 to A08. Also, any other five blocks must have numbers selected from A09 to A18, any other five blocks must be from A19 to A27, any other two blocks from A28 to A31, and so on. Note that multiple blocks can have the same teacher number.
The same teacher must not be in the same class three blocks in a row.
The same teacher can only put in four blocks at maximum in a row.

Now we have a clear idea of what you want the computer to handle.

STEP 3. Estimate the number of bits required

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.

Summary

Verbalize the problem to solve with a computer. (requirements definition)
Identify what you want the computer to handle.
Estimate how many spin (corresponding to $+1/-1$ Ising variable) elements are needed

What is a combinatorial optimization problem?

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.