Get notified of new posts

The IHTC 2024 (1)¶

Last year I decided to participate in an Optimization contest about scheduling patients to operation rooms called Integrated Healthcare Timetabling Competition 2024. I didn't do extremely well. This was not a surprise to me: I am aware of how competitive these competitions can be.

That doesn't mean that I did not try hard, though! And since I took it as an opportunity to try engines that I'm not very comfortable using, I actually learn lots.

In this post I will try to go back to the competition and ~~convince myself that I did not do that bad~~ summarize what I did. Hopefully it will be useful for others in the future. I put a (1) in the name because I could not fit everything I did in a single post, I will potentially revisit this topic in the future with my other approaches (see the end of the post for the other approaches / topics).

The problem itself¶

There are probably many scientific articles that explain both the problem and better performing methods than the ones here. A will include some references at the end of the post. But I also leave here, the main site for the contest, the open-access article where they summarize the results and best methods.

The problem is described in the page of the contest, in particular in this document. I will do my best to summarize it here but I do recommend reading the full document as I don't think I will be as exhaustive.

I will split the description in two parts, but the problem, as its name implies, integrates both into a single decision. I will use parts of a solution to help explain it.

The Scheduling / Theater assignment part¶

This one joins the "Patient-to-Room Assignment" and the "Surgical Case Planning" as explained in the organizers article.

A set of Patients require one surgery each. After the surgery (which takes place the day the patient arrives), each patient need to stay at a Room in the hospital for a number of days (how many depends on the patient). Each patient has its own set of relevant attributes: they have an assigned Surgeon, and a given duration (in minutes) for their surgery. They have a window of days when they can have the surgery (some Patientss surgery are optional). Patients also have many other characteristics that make them more or less compatible with Nurses, Rooms, and other Patients (e.g., age group, gender, nurse skill level required, workload for nurse).

Example of patient input data. Taken from the organizers.

Each surgery is carried out in any one of potentially many Operating Theaters. These have a daily capacity, measured by the maximum number of minutes it can be used for surgeries. The surgery requires the patient's Surgeon to be present, of course. Surgeons also have a daily capacity. We want to avoid assigning too many different Operating Theaters to the same Surgeon during the same day.

The Room where the patient stays after the surgery has a maximum number of patients that can fit inside. Also, Rooms are unisex and it's better to put patients of the same age range together.

The scheduling decision is to decide, for each Patient: which day it will start their surgery (if it is carried out), in which Operating Room and in which Room they stay.

The time horizon for the planning consists of a number of weeks (2 to 4 weeks). There are some patients (called Occupants) at the start of the planning horizon that are already in the hospital, taking space in a room and requiring Nurses, but not requiring a surgery.

As example, the following figures show the assignment of patients to rooms and surgeons workload.

Patient to room and daySurgeon workloadOperating Theater workload

Each line represents the stay of a Patient. The number of lines at any given day cannot surpass the capacity and there cannot be two patients of the same gender. E.g., room r4 doesn't exceed the capacity of 3 and the blue and red lines never intersect.

Days in X axis (scale not shown), Rooms in Y axis (`r4` and `r5`). Each line is a patient stay.

The following figure shows the workload of Surgeons.

Days in X axis, Workload in Y axis. On chart per `Surgeon`.

Days in X axis, Workload in Y axis. On chart per `Operating Theater`.

The Timetable part¶

This one covers the "Nurse-to-Patient Assignment" as presented by the organizers.

A set of Nurses is required to attend patients in the Rooms. Nurses work in shifts (3 shifts per day) and they already know which shift of which day they are working (e.g., Nurse A works the morning of day 3 and the afternoon of day 4). Nurses have attributes that make them more or less suitable for Patients (i.e., skills, available workload).

We want to minimize the number of different Nurses that take care of any individual Patient.

The timetable decision consists of assigning a Nurse for each Room and shift.

Nurse to RoomNurse workloadPatient skill level

`Nurses` assigned to `Rooms`. Days in X axis, Shift in Y axis. One chart per `Room`. The content is the assigned `Nurse`.

The workload of a Patient is not constant during their stay. The chart shows the aggregated workload for each Nurse. It can be seen that Nurse n00 has a three shifts were the Nurse is overloaded.

`Nurse` workload per shift. Shifts in X axis, Workload in Y axis. One chart per `Nurse`.

The skill levels of a Patient are not constant during their stay. In dotted lines is the provided skill level by the Nurse that is assigned to the Room of the Patient. In red are the gaps between the Nurse's level and the required one. Patient a0 has three shifts were his required skill level was not met.

`Patient` skill level requirements per shift. Shifts in X axis, Skill level in Y axis. One chart per `Patient`.

CPSAT model for the Scheduling / Theater assignment¶

While writing the model, I realized that it would be completely unreadable to put everything here. So I will only show the parameters, variables and constraints of the first part: the room scheduling and operating room assignment (no Nurses here, then).

I will also refrain from being very very precise on the sets and possible combinations, edge cases, etc. The problem is explained in many places and my intention is to provide a feeling the modelling approach rather than a full reproducible model. I will skip occupants, too. In practice, they imply small modifications to the room usage constraints during the first periods of the planning horizon: capacity, gender and age constraints.

The repository with the code has everything that's needed to test, run, reproduce the model. Go to this file, specifically to check the CP-SAT formulation.

Main parameters¶

\[ \begin{array}{ll} \hline \text{Sets & Parameter} & \text{Description} \\ \hline \mathcal{S} & \text{All surgeons} \\ \mathcal{O} & \text{All operating theaters} \\ \mathcal{D} \subset \mathbf{Z} & \text{All days} \\ \mathcal{P} & \text{All patients} \\ \mathcal{R} & \text{All rooms} \\ \mathcal{P}^m \subset \mathcal{P} & \text{All mandatory patients} \\ \mathcal{P}_g \subset \mathcal{P} & \text{All patients of gender $g$} \\ \mathcal{P}_r \subset \mathcal{P} & \text{All patients that can stay in room $r$} \\ \mathcal{P}_s \subset \mathcal{P} & \text{All patients for surgeon } s\\ RC_r \in \mathbf{Z} & \text{Capacity of room } r \\ S_p \in \mathcal{S} & \text{Surgeon of patient } p \\ SD_p \in \mathbf{Z} & \text{Surgery duration for patient } p \\ \mathcal{D}_p \in \mathbf{D} & \text{Potential admission days for patient } p \\ Y_p \in \mathbf{Z} & \text{Age group for patient } p \\ SC_{s,d} \in \mathbf{Z} & \text{Capacity of surgeon $s$ in day $d$} \\ OC_{o,d} \in \mathbf{Z} & \text{Capacity of operating theater $o$ in day $d$} \\ \ell_p & \text{Length of stay of patient } p \\ \hline \end{array} \]

Variables¶

As expected, there are variables relating to the room, operating room and admission assigned for each patient $p$. And many other secondary variables to count the capacity use of Surgeons, Operating Theaters and Rooms.

\[ \begin{array}{lll} \hline \text{Variable} & \text{Domain} & \text{Description} \\ \hline a_{p,d} & \{0,1\} & \text{1 if patient } p \text{ starts in day } d \\ ai_{p} & \mathcal{D} & \text{Start day of patient } p \\ ain_{p,r} & \text{Interval} & \text{Optional fixed-sized interval for patient } p \text{ stay in room } r \\ r_{p,r} & \{0,1\} & \text{1 if patient } p \text{ assigned to room } r \\ t_{p,o} & \{0,1\} & \text{1 if patient } p \text{ assigned to operating theater } o \\ at_{p,o,d} & \{0,1\} & \text{1 if patient } p \text{ assigned to operating theater } o \text{ in day } d \\ s_{s,o,d} & \{0,1\} & \text{1 if surgeon } s \text{ assigned to operating theater } o \text{ in day } d \\ to_{o,d} & \{0,1\} & \text{1 if operating theater } o \text{ is open in day } d \\ st_{s,o,d} & \{0,1\} & \text{1 if surgeon works in operating theater } o \text{ in day } d \\ y_{r,d}^{min} & \mathbf{Z} & \text{Min age of patients in room $r$ during day $d$} \\ y_{r,d}^{max} & \mathbf{Z} & \text{Max age of patients in room $r$ during day $d$} \\ y_{r,d}^{dif} & \mathbf{Z} & \text{Max difference of age of patients in room $r$ during day $d$} \\ \hline \end{array} \]

Constraints¶

Both the binary $a_{p,d} \in \{0,1\}$ and the integer $ai_{p} \in \mathcal{D}$ represent the same decision. So we link them: if the former is true, then the latter needs to have a day assigned accordingly:

\[ \forall p \in \mathcal{P}, \forall d \in \mathcal{D}_p: a_{p,d} = 1 \ \implies \ ai_{p} = d \\ \]

We now create an optional interval for each patient and each room that defines the time the patient is staying in the room, if assigned to that room (i.e., if $r_{p,r}=1$).

\[ \forall p \in \mathcal{P}, \forall r \in \mathcal{R}: ain_{p,r} = \text{IntervalVar}\bigl(start = ai_{p}, \ size = \ell_p, \ \text{isPresent} = r_{p,r}\bigr) \]

We use the Cumulative constraint in CP-SAT to limit the patient intervals, such that the room capacity is never surpassed.

We use this constraint too to limit that no two patients with different gender can be in the same room at the same time. We do this second part by creating the constraint for each room, each gender and each member of the opposite gender. Each member of the opposite gender will use the whole capacity.

\[ \forall r \in R, \ \forall g \in G, \ \forall p' \in P_r \setminus P_g: \quad \mathrm{Cumulative}\Big( \{\, (ain_p, 1) \mid p \in P_g \cap P_r \,\} \ \cup \ \{\, (ain_{p'}, RC_r) \,\}, \ RC_r \Big) \]

Then, we need to link all variables that relate rooms, theaters and surgeons assignments.

If and only if patient $p$ is assigned to operating theater $o$ in day $d$ ($at_{o,p,d} = 1$), then the admission for that day ($a_{p,d}$) and the operating theater assignment ($t_{p,o}$) need to be true.
If patient $p$'s admission is in day $d$ ($a_{p,d}=1$) and is assigned to operation theater $o$ ($t_{p,o}=1$), then:
- Surgeon $S_p$ is assigned to theater $o$ in day $d$ ($st_{S_{p},o,d} = 1$) and
- Theater $o$ opens in day $d$ ($to_{o,d}=1$).

I'm omitting the =1 part for these boolean variables, but is should be assumed.

\[ \forall o \in \mathcal{O}, \forall p \in \mathcal{P}, \forall d \in \mathcal{D}_p: \quad \begin{cases} & at_{o,p,d} \ \Leftrightarrow \ (a_{p,d} \land \ t_{p,o}) \\ & (a_{p,d} \land \ t_{p,o}) \implies st_{S_{p},o,d} \\ & (a_{p,d} \land \ t_{p,o}) \implies to_{o,d} \\ \end{cases} \]

Most of the previous clauses were actually implemented as a Boolean OR clauses. For example,

\[ (a_{p,d} = 1 \land \ t_{p,o} = 1) \implies (st_{S_{p},o,d}=1) \\ \]

becomes:

\[ (st_{S_{p},o,d}=1) \lor \ (t_{p,o} = 0) \lor (a_{p,d}=0) \\ \]

The sum of the surgery duration $SD_p$ of each of the surgeon's patients $p \in \mathcal{P}_s$ in any given day $d$, cannot be greater then their daily capacity $SC_{s,d}$.

\[ \forall s \in \mathcal{S}, \ \forall d \in \mathcal{D}: \sum_{p \in \mathcal{P}_s} a_{p,d} \cdot SD_p \leq SC_{s,d} \]

The sum of the surgery durations $SD_p$ of all the operating theater's patients in any given day $d$, cannot be greater then their daily capacity $OC_{o,d}$.

\[ \forall o \in \mathcal{O}, \ \forall d \in \mathcal{D}: \sum_{p \in \mathcal{P}} at_{p,o,d} \cdot SD_p \leq OC_{o,d} \]

All mandatory patients need to be scheduled, with a room and an operating theater.

\[ \forall p \in \mathcal{P}^m: \quad \begin{cases} & \sum_{d \in \mathcal{D}} a_{p,d} = 1 \\ & \sum_{r \in \mathcal{R}} r_{p,r} = 1 \\ & \sum_{o \in \mathcal{O}} t_{p,o} = 1 \\ \end{cases} \]

Each optional patient can be scheduled at most once, and they get a theater and a room if and only if they are scheduled.

\[ \forall p \in \mathcal{P} \setminus \mathcal{P}^m: \quad \begin{cases} & \sum_{d \in \mathcal{D}} a_{p,d} \leq 1 \\ & \sum_{r \in \mathcal{R}} r_{p,r} = \sum_{d \in \mathcal{D}} a_{p,d} \\ & \sum_{o \in \mathcal{O}} t_{p,o} = \sum_{d \in \mathcal{D}} a_{p,d} \\ \end{cases} \]

Then, we need to declare the min/max/diff age for each room and day. This is a bit tricky since we need to first know which patient is where (which room) and when (which day). Ideally, I would have loved to use CPSAT Intervals here, since they seem to be a lot more efficient at this scheduling constraints. But I did not find a way to (ab)use the functionality in the right way.

If patient $p$ has admission in day $d$ and is assigned to room $r$, then during his whole stay ($d' \in \{\, d, d+1, \dots, d+\ell_p-1 \,\}$): (a) the max age group ($y^{max}_{r,d'}$) will be at least his age group ($Y_p$), and (b) the min age group ($y^{min}_{r,d'}$) will be at most his age group ($Y_p$). Otherwise, we do not enforce the constraint.

\[ \forall p \in \mathcal{P}, \forall d \in \mathcal{D}_p,\forall d' \in \{\, d, d+1, \dots, d+\ell_p-1 \,\}: \quad \begin{cases} (a_{p,d} \land r_{p,r}) \implies y_{r,d'}^{max} \geq Y_p \\ (a_{p,d} \land r_{p,r}) \implies y_{r,d'}^{min} \leq Y_p \end{cases} \]

Once we have the max and min age groups per room and day, we just calculate the difference:

\[ \forall p \in \mathcal{P}, \forall d \in \mathcal{D}: y_{r,d}^{diff} = y_{r,d}^{max} - y_{r,d}^{min} \]

Objective function¶

In this simplified model, we have five parts for our objective function, that are explained by the weights table below:

\[ \begin{array}{ll} \hline \text{Weights} & \text{Description} \\ \hline W^{o} & \text{Cost for opening an operating theater in a day} \\ W^{t} & \text{Cost for assigning one more theater per day to a surgeon} \\ W^{d} & \text{Cost of delaying the surgery one day} \\ W^{y} & \text{Cost of having a max age diference of 1 in a room and day} \\ W^{p} & \text{Reward for each optional patient scheduled} \\ \hline \end{array} \]

So we just need to sum all of the components into one single value:

\[ W^{o} \cdot \sum_{o \in \mathcal{O}, d \in \mathcal{D}} to_{o,d} + W^{t} \cdot \sum_{o \in \mathcal{O}, d \in \mathcal{D}, s \in \mathcal{S}} st_{s,o,d} + W^{d} \cdot \sum_{d \in \mathcal{D}, p \in \mathcal{P}} a_{p,d} \cdot d + W^{y} \cdot \sum_{d \in \mathcal{D}, r \in \mathcal{R}} y^{diff}_{r,d} - W^{p} \cdot \sum_{d \in \mathcal{D}, p \in \mathcal{P} - \mathcal{P}^m} a_{p,d} \]

How I used the CP model¶

I used the complete version of the CP model inside several decompositions. Below I put the different ways I used it.

Two-stage solving¶

This approach can be used to produce an initial solution or to improve an existing solution (with the help of the next approach, see below). As its name says, there are two stages:

the scheduling + assignment part (i.e., the model describe above) was the first pass.
the nurse timetable part (not described in this post) was the second pass, taking into account the (now fixed) decisions for (1).

The assumption behind it is that there is enough of a solution space even while fixing the patients information to correctly plan the nurses.

Time-window approach¶

This approach requires having a complete feasible solution already. It goes as follows:

select a time window ("from day X to day X+20").
select a sample of unplanned optional patients.
Fix everything that happens outside the time window. I.e., all patients that have an admission prior to day X and after day X+20. Likewise for nurse assignments.
(re)solve this new, smaller problem until a small time limit is reached. This can be done using the two-stage approach described above, or with the complete model. Use the the current solution as warm start.
Integrate the obtained solution into the fixed part.

The figure below shows an example of a time window. Patients p02, p23, p10 and p30 are fixed. All other are free.

Days in X axis (scale not shown), Rooms in Y axis (`r4` and `r5`). Each line is a patient stay. In yellow a candidate time window.

The rational behind this approach is that, especially in large problems, decisions that are very far in time are not very relevant to each other, and thus local changes inside a big enough time window should lead to good solutions.

For another time¶

This post is already a bit too long so I will leave it there. Things that I wanted to include: (1) me trying timefold for python for the first time to solve this problem, (2) the interactive quarto report that I made (and used for the figures above), (3) a graph-based shortest-path move using graph-tool, (4) the interactive GUI that I built to use the problem, (5) the rest of the CPSAT model that dealt with the Nurse assignments.

If you reached this far in this post, congratulations. Also, if any of these remaining topics is of interest to you, feel free to leave a comment with the request below.

I'm also very interested in knowing if this CPSAT implementation was the good one. So do reach out if you think of better alternative formulations. Or if something doesn't make sense.

Subscribe