Stochastic weekly operating room planning with an exponential number of scenarios

In this paper, we consider a two-stage stochastic weekly operating room planning problem with an exponential number of scenarios. The objective function is to minimize the sum of the fixed opening cost of operating rooms and the expected overtime costs that are computed in the second stage. We propose a state-variable model to formulate the two-stage stochastic operating room planning problem and prove its validity. The main advantage of the proposed state-variable model is that it has a pseudo-polynomial number of variables and constraints that are significantly fewer than the number of variables and constraints in an equivalent scenario-based stochastic programming model. We improve the quality of the proposed model by developing an enhanced model that includes remarkably fewer variables and constraints. We also strengthen the model by developing several valid inequalities, including worst-case scenario and symmetry-breaking cuts. We carried out extensive computational experiments to evaluate the performance of the proposed model. The computational results show that the proposed model is capable of finding optimal solutions of instances with 50 surgeries and 1.55E+40 scenarios that is a significant improvement over the state-of-the-art models. The results revealed that the model finds feasible solutions with an average optimality gap of 0.78% for instances with 80 surgeries and 1.48E+64 scenarios.