A Sequential Follower Refinement Algorithm for Robust Surgery Scheduling

An algorithm for the two-stage robust optimization surgery-to-operating room allocation problem is presented. The second-stage problem is an integer linear program whose convex hull is approximated using three types of specialized valid inequalities and Chvátal-Gomory cuts. The resulting linear relaxation of the second-stage problem is then dualized and integrated into the first-stage problem. The resulting mixed integer linear program, which is an approximation of the original problem, is then solved using a commercial solver. If the solution of this model is not optimal for the second-stage problem, valid inequalities for the second-stage problem are generated, yielding a type of column-generation based approach that we refer to as the sequential follower refinement (SFR) algorithm. Data from an academic medical center are used to compare the computational performance of SFR with the constraint and column generation (C&CG) algorithm, which is the only exact approach that has been specifically applied for this problem in the literature. An extensive numerical study of SFR and its computational characteristics is presented that shows that SFR yields better-quality solutions compared with C&CG, even as the termination criterion of SFR is met much sooner, especially for problems involving higher number of surgeries.