Multi-neighborhood Local Search for the Patient Admission Problem

We propose a multi-neighborhood local search procedure to solve a healthcare problem, known as the Patient Admission problem. We design and experiment different combinations of neighborhoods, showing that they have diverse effectiveness for different sets of weights of the cost components that constitute the objective function. We also compute some lower bounds on benchmark instances based on the relaxation of some constraints and the solution of a minimum-cost maximum-cardinality matching problem on a bipartite graph. The outcome is that our results compare favorably with the previous work on the problem, improving on all the available instances, and are also quite close to the computed lower bounds