EURO 2025 Leeds
Abstract Submission

1417. A Benders Decomposition Approach for the Integrated Healthcare Timetabling Problem

Invited abstract in session MC-10: Integrated Healthcare Timetabling Competition II, stream Automated Timetabling.

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

Authors (first author is the speaker)

1. Simon Paulus
Research and Teaching Area Combinatorial Optimization, RWTH Aachen University
2. Felix Engelhardt
Research and Teaching Area Combinatorial Optimization, RWTH Aachen University
3. Tabea Brandt
Lehr- und Forschungsgebiet Kombinatorische Optimierung, RWTH Aachen
4. Johanna Leweke
Research and Teaching Area Combinatorial Optimization, RWTH Aachen University

Abstract

The Integrated Healthcare Timetabling Problem (IHTP) is a challenge set out as part of the Integrated Healthcare Timetabling Competition (IHTC). The IHTP combines three fundamental optimisation problems in hospitals: surgical case planning, patient admission scheduling and nurse-to-room assignment. It addresses the broader trend of moving towards integrated planning healthcare.
Each of the three partial problems has multiple hard and soft constraints that get aggregated into an overall objective. Since mixed-integer linear programming is an established technique for either of the partial problems, we formulate the problem as a mixed-integer linear program (MILP). By definition, the MILP structure allows for a natural Bender’s decomposition. Here, the nurse assignment problem, which only contains soft constraints and therefore is always feasible, is chosen as the sub-problem, and the combined case planning and patient admission as the master problem.
In this talk, we explain specific modelling choices that contribute to the MILP performance. We also show how we modified the classical Bender’s approach to deal with an integer subproblem – a known but notoriously tricky case to implement. We then provide computational results and discuss the advantages and disadvantages of using a quasi-exact MILP method compared to heuristic solution approaches.

Keywords

Status: accepted

Back to the list of papers