Meeting Room Assignment Problem¶

The meeting room assignment problem is a problem of assigning meeting rooms so that as many meetings as possible can be held, given multiple meeting schedules and multiple meeting rooms. In this task, we construct a QUBO model for this problem and try to solve the problem using an annealing machine.

First, assume that the start and end times of each meeting are given as data. Here, the time is given as a string in the format "10:40". In addition, we will have a dictionary of meeting schedule information with the meeting name as the key and the list of start and end times of the meeting as the value. We will also define the number of meetings and the number of available meeting rooms.

Next, we prepare a function time2num to return the given time as a number to compare the meeting times, and a function check_overlap to check if the schedules of given two meetings overlap.

Now we are ready to quantify the information from the given meetings. The next step is to figure out how to represent this problem as a combinatorial optimization problem.

As the first step, we consider how to express variables to indicate in which meeting room each meeting will be held. However, binary variables such as QUBO variables and Ising variables cannot have an arbitrary number of states. So, we assign decision variables as many as the number of meeting rooms to each meeting.

For example, let $q_{i, r}$ be the variable that represents that the meeting $i$ will be held in the meeting room $r$. We can think of it as assigning the meeting $i$ to the meeting room $r$ if $q_{i, r} = 1$, and not assigning it if $q_{i, r} = 0$.

Meeting \ Room	Room A	Room B	$\cdots$	Room H
meeting 1	$q_{0,0}$	$q_{0,1}$	$\cdots$	$q_{0,7}$
meeting 2	$q_{1,0}$	$q_{1,1}$	$\cdots$	$q_{1,7}$
$\vdots$	$\vdots$	$\vdots$	$\cdots$	$\vdots$
meeting 19	$q_{19,0}$	$q_{19,1}$	$\cdots$	$q_{19,7}$

Next, consider the restriction that multiple meetings cannot be assigned to the same meeting room on top of each other.

We construct a list of meetings with overlapped schedules. For example, if there is a schedule overlap between meetings $i$ and $j$, we construct a tuple $(i, j)$ and store it in this list. "The problem of assigning each meeting to a meeting room so that there is no schedule overlap" becomes "the problem of arranging meetings so that if two meetings $(i, j)$ are included in the above list, they are not assigned to the same meeting room".

In the following, we use the check_overlap function defined above to check for overlapped meeting schedules, and based on that, add two meetings $(i, j)$ that have overlapped schedules to the overlaps list.

Next, we define num_meetings × num_rooms QUBO variables, where num_rooms meeting rooms are associated with each of the num_meetings meetings. Let $q_{i, r}$ be the variable corresponding to the index $i$ of the meeting and $r$ of the meeting room.

We create constraints using QUBO variables.

First, since a meeting must be assigned to a single meeting room, we impose the following one-hot constraint:

$ \displaystyle\sum_{r=0}^{\text{Nr} - 1}q_{i, r} = 1 \quad \text{for all} \; i $

In addition, we need to give the constraints such that if the indices $(i, j)$ of two meetings are included in the overlap list overlaps of the meeting schedule defined earlier, they cannot be assigned the same meeting room.

These constraints are that if $(i, j)\in \text{overlaps}$, then $q_{i, r}$ and $q_{j, r}$ will not be $1$ at the same time, which leads to the following constraint:

$ q_{i, r} q_{j, r} = 0 \qquad \text{for}\quad (i, j) \in \text{overlaps}\quad{and}\quad r \in \{0, \cdots, N_r - 1\} $

The two constraint objects room_constraints and overlap_constraints generated above are combined into a logical model to be solved in the end.

Next, we set up the client and solve the model we have defined.

From the variable whose value is $1$ in the obtained solution, we can tell which meeting room each meeting was assigned to.

Let us make the solution more readable. We can take the matrix product of the above solution and the one-dimensional array [0, 1, 2, ...] to obtain an array consisting of the indices of the meeting rooms assigned to each meeting.