Branch and Price for Chance-Constrained Bin Packing

References

• Adler M, Gibbons PB, Matias Y (2002) Scheduling space-sharing for Internet advertising. J. Scheduling 5(2):103–119.Crossref, Google Scholar
• Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MWP, Vance PH (1998) Branch-and-price: Column generation for solving huge integer programs. Oper. Res. 46(3):316–329.Link, Google Scholar
• Batun S, Denton BT, Huschka TR, Schaefer AJ (2011) Operating room pooling and parallel surgery processing under uncertainty. INFORMS J. Comput. 23(2):220–237.Link, Google Scholar
• Benders JF (1962) Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik 4(1):238–252.Crossref, Google Scholar
• Calafiore GC, El Ghaoui L (2006) On distributionally robust chance-constrained linear programs. J. Optim. Theory Appl. 130(1):1–22.Crossref, Google Scholar
• Codato G, Fischetti M (2006) Combinatorial Benders’ cuts for mixed-integer linear programming. Oper. Res. 54(4):756–766.Link, Google Scholar
• Coffman EG Jr, Garey MR, Johnson DS (1978) An application of bin-packing to multiprocessor scheduling. SIAM J. Comput. 7(1):1–17.Crossref, Google Scholar
• Degraeve Z, Jans R (2007) A new Dantzig-Wolfe reformulation and branch-and-price algorithm for the capacitated lot-sizing problem with setup times. Oper. Res. 55(5):909–920.Link, Google Scholar
• Delage E, Ye Y (2010) Distributionally robust optimization under moment uncertainty with application to data-driven problems. Oper. Res. 58(3):595–612.Link, Google Scholar
• Dell’Olmo P, Kellerer H, Speranza MG, Tuza Z (1998) A 1312 approximation algorithm for bin packing with extendable bins. Inform. Processing Lett. 65(5):229–233.Crossref, Google Scholar
• Deng Y, Shen S, Denton B (2020) Chance-constrained surgery planning under uncertain or ambiguous surgery duration. INFORMS J. Comput. Forthcoming.Google Scholar
• Denton BT, Miller AJ, Balasubramanian HJ, Huschka TR (2010) Optimal allocation of surgery blocks to operating rooms under uncertainty. Oper. Res. 58(4-part-1) 802–816.Google Scholar
• Dinh T, Fukasawa R, Luedtke J (2018) Exact algorithms for the chance-constrained vehicle routing problem. Math. Programming 172(1–2):105–138.Crossref, Google Scholar
• Hashemi Doulabi SH, Rousseau L-M, Pesant G (2016) A constraint-programming-based branch-and-price-and-cut approach for operating room planning and scheduling. INFORMS J. Comput. 28(3):432–448.Link, Google Scholar
• Jiang R, Guan Y (2016) Data-driven chance constrained stochastic program. Math. Programming 158(1–2):291–327.Crossref, Google Scholar
• Kong Q, Lee C-Y, Teo C-P, Zheng Z (2013) Scheduling arrivals to a stochastic service delivery system using copositive cones. Oper. Res. 61(3):711–726.Link, Google Scholar
• Lamiri M, Xie X, Zhang S (2008) Column generation approach to operating theater planning with elective and emergency patients. IIE Trans. 40(9):838–852.Crossref, Google Scholar
• Liu X, Küçükyavuz S, Luedtke J (2016) Decomposition algorithms for two-stage chance-constrained programs. Math. Programming 157(1):219–243.Crossref, Google Scholar
• Luedtke J (2014) A branch-and-cut decomposition algorithm for solving chance-constrained mathematical programs with finite support. Math. Programming 146(1–2):219–244.Crossref, Google Scholar
• Luedtke J, Ahmed S (2008) A sample approximation approach for optimization with probabilistic constraints. SIAM J. Optim. 19(2):674–699.Crossref, Google Scholar
• Lulli G, Sen S (2004) A branch-and-price algorithm for multistage stochastic integer programming with application to stochastic batch-sizing problems. Management Sci. 50(6):786–796.Link, Google Scholar
• Mak H-Y, Rong Y, Zhang J (2015) Appointment scheduling with limited distributional information. Management Sci. 61(2):316–334.Link, Google Scholar
• Nursing Solutions Inc. (2016) 2016 national healthcare and RN retention report. Report, Nursing Solutions, Inc., East Petersburg, PA.Google Scholar
• Pagnoncelli, BK, Ahmed S, Shapiro A (2009) Sample average approximation method for chance constrained programming: Theory and applications. J. Optim. Theory Appl. 142(2):399–416.Crossref, Google Scholar
• Prékopa A (1995) Stochastic Programming (Kluwer Academic Publishers, Dordrecht, Netherlands).Crossref, Google Scholar
• Qiu F, Ahmed S, Dey SS, Wolsey LA (2014) Covering linear programming with violations. INFORMS J. Comput. 26(3):531–546.Link, Google Scholar
• Ryan DM, Foster BA (1981) An integer programming approach to scheduling. Wren A, ed. Computer Scheduling of Public Transport, Urban Passenger Vehicle and Crew Scheduling (North Holland Publishing Company, Amsterdam), 269–280.Google Scholar
• Scarf H (1958) A min-max solution of an inventory problem. Arrow KJ, Karlin S, Scarf H, eds. Studies in the Mathematical Theory of Inventory and Production (Stanford University Press, Stanford, CA), 201–209.Google Scholar
• Shylo OV, Prokopyev OA, Schaefer AJ (2012) Stochastic operating room scheduling for high-volume specialties under block booking. INFORMS J. Comput. 25(4):682–692.Link, Google Scholar
• Silva EF, Wood RK (2006) Solving a class of stochastic mixed-integer programs with branch and price. Math. Programming 108(2–3):395–418.Crossref, Google Scholar
• Singh KJ, Philpott AB, Wood RK (2009) Dantzig-Wolfe decomposition for solving multistage stochastic capacity-planning problems. Oper. Res. 57(5):1271–1286.Link, Google Scholar
• Song Y, Luedtke JR, Küçükyavuz S (2014) Chance-constrained binary packing problems. INFORMS J. Comput. 26(4):735–747.Link, Google Scholar
• Strum DP, May JH, Sampson AR, Vargas LG, Spangler WE (2003) Estimating times of surgeries with two component procedures: Comparison of the lognormal and normal models. Anesthesiology 98(1):232–240.Crossref, Google Scholar
• Takriti S, Ahmed S (2004) On robust optimization of two-stage systems. Math. Programming 99(1):109–126.Crossref, Google Scholar
• Vanderbeck F (2000) On Dantzig-Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm. Oper. Res. 48(1):111–128.Link, Google Scholar
• Vanderbeck F, Wolsey LA (1996) An exact algorithm for IP column generation. Oper. Res. Lett. 19(4):151–159.Crossref, Google Scholar
• Wang Y, Tang J, Fung RYK (2014) A column-generation-based heuristic algorithm for solving operating theater planning problem under stochastic demand and surgery cancellation risk. Internat. J. Production Econom. 158:28–36.Crossref, Google Scholar
• Zhang Y, Jiang R, Shen S (2018) Ambiguous chance-constrained binary programs under mean-covariance information. SIAM J. Optim. 28(4):2922–2944.Crossref, Google Scholar