EURO 2025 Leeds
Abstract Submission

EURO-Online login

1842. Using Graph Transformation and Mixed Integer Linear Programming to solve the IHTC 2024

Invited abstract in session MB-10: Integrated Healthcare Timetabling Competition I, stream Automated Timetabling.

Monday, 10:30-12:00
Room: Clarendon SR 1.06

Authors (first author is the speaker)

1. Maximilian Kratz
Department of Electrical Engineering and Information Technology, Real-Time Systems Lab
2. Steffen Zschaler
Department of Informatics, King's College London
3. Jens Kosiol
Philipps-Universität Marburg, Software Engineering Group
4. Andy Schürr
Department of Electrical Engineering and Information Technology, Real-Time Systems Lab

Abstract

In this talk, we present our solution to the International Healthcare Timetabling Competition (IHTC) 2024.
In IHTC 2024, competitors must calculate a valid roster for patients, nurses, and surgeons as well as a room schedule while ensuring various constraints are satisfied.
Our solution is based on GIPS, the "Graph-Based (M)ILP Problem Specification (GIPS) Tool", which combines Graph Transformation (GT) and Mixed Integer Linear Programming (MILP).
GIPS aims to allow users to easily and compactly specify optimization problems using graph-based modeling and a domain-specific language close to the respective problem domain.
In contrast to other approaches, GIPS does not need a (hand-written) low-level representation of graph structures like arrays or matrices for handling graph-based models.
For example, required or forbidden structural graph patterns can easily be specified using mechanisms like inheritance and typification.
GIPS translates a given compact specification to a MILP problem, which it solves with off-the-shelf constraint solvers.
One of the benefits of GIPS is that the high-level specification can be changed and adopted easily which can support a rapid prototyping workflow, easy incremental development of problem specifications, and adaptation to new contexts.
This talk will focus on showing how GIPS allows for compactly specifying the IHTC 2024 problem with its domain-specific language, using an iterative approach adding constraints step by step.

Keywords

Status: accepted

Back to the list of papers