Mixed integer programming based heuristics for the Patient Admission Scheduling problem

The Patient Admission Scheduling (PAS) problem is a combinatorial optimization problem where elective patients are automatically assigned to beds for the duration of their stay considering not only the medical necessity but also the patient preferences. Due to its combinatorial nature, solving the previously published problem instances to optimality is a difficult task. In this paper, we present two Mixed Integer Programming (MIP) based heuristics namely Fix-and-Relax (F&R) and Fix-and-Optimize (F&O) where PAS problem instances are decomposed into sub-problems and then the sub-problems are optimized. Our approach uses patient decomposition considering patient length-of-Stay (LoS), room preference, admission date, specialism choice, and age, as well as time decomposition considering different optimization window sizes. Quick solutions generated by F&R heuristic are used as an input to the F&O heuristic and are improved in an iterative nature. Main goal of the study is to provide high quality solutions in shorter run times. Computational findings show that the proposed heuristics provide promising results towards the solution of the problem in faster CPU times than the previously reported values where less than 15 percent gap from the best known solutions is achieved for most of the test instances, and as low as 5 percent gap for some of the sample data.