Propagating logic-based Benders' decomposition approaches for distributed operating room scheduling

Abstract

We develop three novel logic-based Benders' decomposition (LBBD) approaches and a cut propagation mechanism to solve large-scale location-allocation integer programs (IPs). We show that each LBBD can be implemented in four different possible ways, yielding distinct LBBD variants with completely different computational performances. LBBDs decompose the IP model into an integer location and knapsack-based allocation master problem and multiple packing IP sub-problems. We illustrate the performance of our LBBDs on the distributed operating room (OR) scheduling (DORS) problem, where patients and ORs are collaboratively scheduled across a network of hospitals, and the goal is to select patients with the highest priority scores and schedule them in the current planning horizon, while determining the number of surgical suites and operating rooms required to accommodate the schedule at minimum cost. We quantitatively demonstrate that the new Benders' cuts, cut propagation, and implementation can individually or collectively yield a computational time impact of at least two orders of magnitude. We also demonstrate that our LBBDs are 10–100x faster than IP+Gurobi and are more successful at finding optimal solutions. Finally, we show that DORS increases the average OR utilization across the network to more than 95%.