document: The scheduling process we adopt matches a multiple stage stochastic programming approach. Standard two-stage stochastic programs with linear or convex functions are often solved using the L-shaped method or Bender's decomposition [44,6,7]. However, our recourse decision (scheduled cancellations) is still anticipative to further uncertainty, namely the second shift surgery durations, unavailability and cancellations. As such, the decision problem can be viewed as a three-stage recourse model [5,6]. Solving the scheduling problem is further complicated because the recourse function is integer. Laporte and Louveaux [26] propose modified L-shaped decomposition with adjusted optimal cuts for two stage stochastic program with integer recourse. Angulo et al. [1] alternately generate optimal cuts of the linear sub-problem and the integer sub-problem, which improves the practical convergence (see also [15,8]). We follow a sample average approximation approach (SAA) which uses this framework. Moreover, we prove and exploit a specific relationship between the first-stage realization and the optimal number of scheduled cancellations to speed up the computation of integer cuts. We use Jensen's inequality [17] to upper bound the minus second (and third) stage cost, a technique that was proposed by Batun et al. [3].
extractive_keyphrases: decision problem integer cuts integer recourse linear or convex functions multiple stage stochastic programming approach recourse decision recourse function saa sample average approximation approach scheduled cancellations scheduling problem scheduling process two stage stochastic program
abstractive_keyphrases: bender's decomposition first-stage realization generate optimal cuts of the linear sub-problem and the integer sub-problem integer sub-problem jensen's inequality linear sub-problem l-shaped method modified l-shaped decomposition three-stage recourse model two-stage stochastic programs upper bound the minus second (and third) stage cost