# 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.

```
# Meeting schedule
schedules = {
"meeting1": ("10:00", "13:00"),
"meeting2": ("10:00", "12:00"),
"meeting3": ("10:00", "11:00"),
"meeting4": ("11:00", "13:00"),
"meeting5": ("11:00", "12:00"),
"meeting6": ("11:00", "15:00"),
"meeting7": ("12:00", "16:00"),
"meeting8": ("12:00", "15:00"),
"meeting9": ("13:00", "15:00"),
"meeting10": ("13:00", "14:00"),
"meeting11": ("14:00", "17:00"),
"meeting12": ("15:00", "19:00"),
"meeting13": ("15:00", "17:00"),
"meeting14": ("15:00", "16:00"),
"meeting15": ("16:00", "18:00"),
"meeting16": ("16:00", "18:00"),
"meeting17": ("17:00", "19:00"),
"meeting18": ("17:00", "18:00"),
"meeting19": ("18:00", "19:00"),
}
# Number of meetings
num_meetings = len(schedules)
# Number of meeting rooms
num_rooms = 8
```

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.

```
# Convert time to numeric time units
def time2num(time: str):
h, m = map(float, time.split(":"))
return h + m / 60
```

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.

```
# Check if there is any overlap between the two meeting times
def check_overlap(meeting_name1: str, meeting_name2: str) -> bool:
start1, end1 = map(time2num, schedules[meeting_name1])
start2, end2 = map(time2num, schedules[meeting_name2])
return start1 < end2 and start2 < end1
```

```
import itertools
# Obtain a list of meeting names
mtg_names = list(schedules.keys())
# Store the index of meetings with overlapped schedules as a tuple
overlaps = [
(idx1, idx2)
for idx1, idx2 in itertools.combinations(range(num_meetings), 2)
if check_overlap(mtg_names[idx1], mtg_names[idx2])
]
```

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.

```
from amplify import VariableGenerator
gen = VariableGenerator()
q = gen.array("Binary", shape=(num_meetings, num_rooms))
```

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 $

```
from amplify import one_hot
room_constraints = one_hot(q, axis=1)
```

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\} $

```
from amplify import equal_to, sum as amplify_sum
# Impose the constraint that q[i][r] * q[j][r] = 0 for all (i, j) in overlaps
overlap_constraints = amplify_sum(
[equal_to(q[i, :] * q[j, :], 0, axis=()) for (i, j) in overlaps]
)
```

The two constraint objects `room_constraints`

and `overlap_constraints`

generated
above are combined into a logical model to be solved in the end.

```
model = room_constraints + overlap_constraints
```

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

```
from amplify import FixstarsClient, solve
from datetime import timedelta
# Set the client
client = FixstarsClient()
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx" # If you are using it in a local environment, please enter the access token for Amplify AE
client.parameters.timeout = timedelta(milliseconds=1000) # timeout is 1000 ms
# Solve the problem
result = solve(model, client)
# If result is empty, it means that no solution satisfying the constraints was obtained.
if len(result) == 0:
raise RuntimeError("Given constraint conditions are not satisfied")
```

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

```
# Assign solution in the form of the original decision variable
solution = q.evaluate(result.best.values)
solution
```

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.

```
import numpy as np
# room_list[i] is the index of the meeting room assigned to meeting i
room_list = (solution @ np.arange(num_rooms)).astype(int)
# Create a dictionary of meeting names and room indices
room_assignment = {
meeting_name: room_idx for meeting_name, room_idx in zip(mtg_names, room_list)
}
room_assignment
```

```
#
# Visualize meeting room assignment
#
%matplotlib inline
import string
import matplotlib
import matplotlib.pyplot as plt
def plot_mtg_schedule():
room_names = [f"Room {c}" for c in string.ascii_uppercase[:num_rooms]]
cmap = matplotlib.colormaps["coolwarm"].resampled(num_rooms)
fig, ax = plt.subplots(nrows=1, ncols=1, figsize=(15, 10))
for mtg_name, room in room_assignment.items():
start = time2num(schedules[mtg_name][0])
end = time2num(schedules[mtg_name][1])
ax.fill_between(
[room + 0.55, room + 1.45],
start,
end,
edgecolor="black",
linewidth=3.0,
facecolor=cmap(room),
)
ax.text(
room + 0.6, start + 0.1, f"{schedules[mtg_name][0]}", va="top", fontsize=10
)
ax.text(
room + 1.0,
(start + end) * 0.5,
mtg_name,
ha="center",
va="center",
fontsize=15,
)
# Set First Axis
ax.yaxis.grid()
ax.set_xlim(0.5, len(room_names) + 0.5)
ax.set_ylim(19.1, 7.9)
ax.set_xticks(range(1, len(room_names) + 1))
ax.set_xticklabels(room_names)
ax.set_ylabel("Time")
# Set Second Axis
axis_x = ax.secondary_xaxis("top")
axis_y = ax.secondary_yaxis("right")
axis_x.set_xticks(ax.get_xticks())
axis_x.set_xticklabels(ax.get_xticklabels())
axis_y.set_ylabel("Time")
plt.show()
plot_mtg_schedule()
```