×

Logic-based Benders decomposition for large-scale optimization. (English) Zbl 1446.90108

Velásquez-Bermúdez, Jesús M. (ed.) et al., Large scale optimization in supply chains and smart manufacturing. Theory and applications. Cham: Springer. Springer Optim. Appl. 149, 1-26 (2019).
Summary: Logic-based Benders decomposition (LBBD) is a substantial generalization of the classical Benders decomposition that, in principle, allows the subproblem to be any optimization problem rather than specifically a linear or nonlinear programming problem. It is amenable to a wide variety of large-scale problems that decouple or otherwise simplify when certain decision variables are fixed. This chapter presents the basic theory of LBBD and explains how the classical Benders decomposition is a special case. It also describes branch and check, a variant of LBBD that solves the master problem only once. It illustrates in detail how Benders cuts and subproblem relaxations can be developed for some planning and scheduling problems. It then describes the role of LBBD in three large-scale case studies. The chapter concludes with an extensive survey of the LBBD literature, organized by problem domain, to allow the reader to explore how Benders cuts have been developed for a wide range of applications.
For the entire collection see [Zbl 1427.90005].

MSC:

90C06 Large-scale problems in mathematical programming
90B80 Discrete location and assignment
90B35 Deterministic scheduling theory in operations research

Software:

MiniZinc; MaxHS
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] L. Agussurja, A. Kumar, and H. C. Lau. Resource-constrained scheduling for maritime traffic management. In AAAI Conference on Artificial Intelligence, pages 6086-6093, 2018.
[2] L. Assunção, T. F. Noronha, A. C. Santos, and R. Andrade. A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs. Computers and Operations Research, 81:51-66, 2017. · Zbl 1391.90504 · doi:10.1016/j.cor.2016.12.010
[3] L. Assunção, T. F. Noronha, A. C. Santos, and R. Andrade. On the finite optimal convergence of logic-based Benders decomposition in solving 0-1 min-max regret optimization problems with interval costs. In International Symposium on Combinatorial Optimization (ISCO 2016), volume 9849 of Lecture Notes in Computer Science, pages 1-12, 2017. · Zbl 1419.90090
[4] F. Bacchus, S. Dalmao, T. Pitassi, and G. Katsirelos. Relaxation search: A simple way of managing optional clauses. In AAAI Conference on Artificial Intelligence, pages 835-841. 2014.
[5] L. Bai, J. E. Mitchell, and J.-S. Pang. On convex quadratic programs with linear complementarity constraints. Computational Optimization and Applications, 54:517-554, 2012. · Zbl 1295.90035 · doi:10.1007/s10589-012-9497-4
[6] M. A. Bajestani and J. C. Beck. Scheduling a dynamic aircraft repair shop with limited repair resources. Journal of Artificial Intelligence Research, 47:35-70, 2013. · Zbl 1276.68040 · doi:10.1613/jair.3902
[7] M. A. Bajestani and J. C. Beck. A two-stage coupled algorithm for an integrated planning and flowshop scheduling problem with deteriorating machines. Journal of Scheduling, 18:471-486, 2015. · Zbl 1328.90031 · doi:10.1007/s10951-015-0416-2
[8] P. Baptiste, C. Le Pape, and W. Nuijten. Constraint-Based Scheduling: Applying Constraint Programming to Scheduling Problems. Kluwer, Dordrecht, 2001. · Zbl 1094.90002 · doi:10.1007/978-1-4615-1479-4
[9] A. Y. Barlatt, A. M. Cohn, and O. Gusikhin. A hybridization of mathematical programming and dominance-driven enumeration for solving shift-selection and task-sequencing problems. Computers and Operations Research, 37:1298-1307, 2010. · Zbl 1178.90254 · doi:10.1016/j.cor.2009.09.013
[10] P. Beame, H. Kautz, and A. Sabharwal. Understanding the power of clause learning. In International Joint Conference on Artificial Intelligence (IJCAI 2003), 2003. · Zbl 1080.68651
[11] J. C. Beck. Checking up on branch-and-check. In D. Cohen, editor, Principle and Practice of Constraint Programming (CP), volume 6308 of Lecture Notes in Computer Science, pages 84-98, 2010.
[12] J. F. Benders. Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4:238-252, 1962. · Zbl 0109.38302 · doi:10.1007/BF01386316
[13] L. Benini, D. Bertozzi, A. Guerri, and M. Milano. Allocation and scheduling for MPSoCs via decomposition and no-good generation. In Principles and Practice of Constraint Programming (CP 2005), volume 3709 of Lecture Notes in Computer Science, pages 107-121. Springer, 2005. · Zbl 1153.68448
[14] L. Benini, M. Lombardi, M. Mantovani, M. Milano, and M. Ruggiero. Multi-stage Benders decomposition for optimizing multicore architectures. In L. Perron and M. A. Trick, editors, CPAIOR 2008 Proceedings, volume 5015 of Lecture Notes in Computer Science, pages 36-50. Springer, 2008. · Zbl 1142.68506
[15] L. Benini, M. Lombardi, M. Milano, and M. Ruggiero. Optimal resource allocation and scheduling for the CELL BE platform. Annals of Operations Research, 184:51-77, 2011. · Zbl 1214.90050 · doi:10.1007/s10479-010-0718-x
[16] D. Bergman and A. U. Raghunathan. A Benders approach to the minimum chordal completion problem. In L. Michel, editor, CPAIOR Proceedings, volume 9075 of Lecture Notes in Computer Science, pages 47-64. Springer, 2015. · Zbl 1464.90074
[17] K. E. C. Booth, T. T. Tran, and J. C. Beck. Logic-based decomposition methods for the travelling purchaser problem. In C.-G. Quimper, editor, CPAIOR 2016 Proceedings, volume 9678 of Lecture Notes in Computer Science, pages 55-64. Springer, 2016. · Zbl 1475.90012
[18] A. H. Borzabadi and M. E. Sadjadi. Optimal control of hybrid systems by logic-based Benders decomposition. In A. Giua, C. Mahulea, M. Silva, and J. Zaytoon, editors, Analysis and Design of Hybrid Systems, volume 3, pages 104-107, 2009. · doi:10.3182/20090916-3-ES-3003.00019
[19] H. Cambazard, E. Hebrard, B. O’Sullivan, and A. Papadopoulos. Local search and constraint programming for the post enrolment-based course timetabling problem. Annals of Operations Research, 194:111-135, 2012. · Zbl 1251.90120 · doi:10.1007/s10479-010-0737-7
[20] H. Cambazard, P.-E. Hladik, A.-M. Déplanche, N. Jussien, and Y. Trinquet. Decomposition and learning for a hard real time task allocation problem. In M. Wallace, editor, Principles and Practice of Constraint Programming (CP 2004), volume 3258 of Lecture Notes in Computer Science, pages 153-167. Springer, 2004. · Zbl 1152.68545
[21] E. Çoban and J. N. Hooker. Single-facility scheduling over long time horizons by logic-based Benders decomposition. In A. Lodi, M. Milano, and P. Toth, editors, CPAIOR 2010 Proceedings, volume 6140 of Lecture Notes in Computer Science, pages 87-91. Springer, 2010. · Zbl 1285.68154
[22] E. Çoban and J. N. Hooker. Single-facility scheduling by logic-based Benders decomposition. Annals of Operations Research, 210:245-272, 2013. · Zbl 1284.90023 · doi:10.1007/s10479-011-1031-z
[23] K. K. H. Cheung. A Benders approach for computing lower bounds for the mirrored traveling tournament problem. Discrete Optimization, 6:189-196, 2009. · Zbl 1159.90399 · doi:10.1016/j.disopt.2008.12.004
[24] Y. Chu and Q. Xia. A hybrid algorithm for a class of resource-constrained scheduling problems. In R. Barták and M. Milano, editors, CPAIOR 2005 Proceedings, volume 3524 of Lecture Notes in Computer Science, pages 110-124. Springer, 2005. · Zbl 1133.90335
[25] A. Ciré and J. N. Hooker. A heuristic logic-based Benders method for the home health care problem. Presented at Matheuristics 2012, Angra dos Reis, Brazil, 2012.
[26] A. A. Ciré, E. Çoban, and J. N. Hooker. Mixed integer programming vs logic-based Benders decomposition for planning and scheduling. In C. Gomes and M. Sellmann, editors, CPAIOR 2013 Proceedings, pages 325-331, 2013. · Zbl 1382.90061 · doi:10.1007/978-3-642-38171-3_22
[27] A. A. Ciré, E. Çoban, and J. N. Hooker. Logic-based Benders decomposition for planning and scheduling: A computational analysis. Knowledge Engineering Review, 31:440-451, 2016. · doi:10.1017/S0269888916000254
[28] E. Çoban, A. Heching, J. N. Hooker, and A. Scheller-Wolf. Robust scheduling with logic-based Benders decomposition. In M. Lübbecke, A. Koster, P. Letmangthe, R. Madlener, B. Peis, and G. Walther, editors, Operations Research Proceedings 2014, volume 4510, pages 99-105. Springer, 2014. · Zbl 1342.90049
[29] G. Codato and M. Fischetti. Combinatorial Benders cuts for mixed-integer linear programming. Operations Research, 54:756-766, 2006. · Zbl 1167.90601 · doi:10.1287/opre.1060.0286
[30] A. I. Corréa, A. Langevin, and L. M. Rousseau. Dispatching and conflict-free routing of automated guided vehicles: A hybrid approach combining constraint programming and mixed integer programming. In J. C. Régin and M. Rueher, editors, CPAIOR 2004 Proceedings, volume 3011 of Lecture Notes in Computer Science, pages 370-378. Springer, 2004. · Zbl 1094.90519
[31] J.-F. Côté, M. Dell’Amico, and M. Iori. Combinatorial Benders cuts for the strip packing problem. Operations Research, 62:643-661, 2014. · Zbl 1302.90173 · doi:10.1287/opre.2013.1248
[32] J. Davies and F. Bacchus. Postponing optimization to speed up MAXSAT solving. In C. Schulte, editor, Principles and Practice of Constraint Programming (CP 2013), volume 8124 of Lecture Notes in Computer Science, pages 247-262. Springer, 2013.
[33] J. Davies and F. Bacchus. Solving MAXSAT by solving a sequence of simpler SAT instances. In J. Lee, editor, Principles and Practice of Constraint Programming (CP 2011), volume 6876 of Lecture Notes in Computer Science. Springer, 2013.
[34] T. O. Davies, G. Gange, and P. J. Stuckey. Automatic logic-based Benders decomposition with MiniZinc. In M. Lübbecke, A. Koster, P. Letmangthe, R. Madlener, B. Peis, and G. Walther, editors, AAAI Conference on Artificial Intelligence, pages 787-793, 2017.
[35] T. O. Davies, A. R. Pearce, P. J. Stuckey, and N. Lipovetzky. Sequencing operator counts. In International Conference on Automated Planning and Scheduling (ICAPS), pages 61-69, 2015.
[36] M. Delorme, M. Iori, and Martello S. Logic basic Benders’ decomposition for orthogonal stock cutting problems. Computers and Operations Research, 78:290-298, 2017. · Zbl 1391.90514 · doi:10.1016/j.cor.2016.09.009
[37] T. Doi and T. Nishui. Two-level decomposition algorithm for shift scheduling problems. In IEEE International Conference on Systems, Man and Cybernetics, pages 3773-3778, 2014.
[38] A. Emeretlis, G. Theodoridis, P. Alefragis, and N. Voros. Mapping DAGs on heterogeneous platforms using logic-based Benders decomposition. In IEEE Computer Society Annual Symposium on VLSI (ISVLSI), pages 119-124. IEEE, 2015.
[39] M. M. Fazel-Zarandi and J. C. Beck. Solving a location-allocation problem with logic-based Benders decomposition. In I. P. Gent, editor, Principles and Practice of Constraint Programming (CP 2009), volume 5732 of Lecture Notes in Computer Science, pages 344-351, New York, 2009. Springer. · doi:10.1007/978-3-642-04244-7_28
[40] M. M. Fazel-Zarandi and J. C. Beck. Using logic-based Benders decomposition to solve the capacity- and distance-constrained plant location problem. INFORMS Journal on Computing, 24:387-398, 2012. · Zbl 1462.90065 · doi:10.1287/ijoc.1110.0458
[41] M. M. Fazel-Zarandi, O. Berman, and J. C. Beck. Solving a stochastic facility location/fleet management problem with logic-based Benders decomposition. IIE Transactions, 45:896-911, 2013. · doi:10.1080/0740817X.2012.705452
[42] A. Froger, M. Gendreau, J. E. Mendoza, E. Pinson, and L.-M. Rousseau. A branch-and-check approach for a wind turbine maintenance scheduling problem. Computers and Operations Research, 88:117-136, 2017. · Zbl 1391.90643 · doi:10.1016/j.cor.2017.07.001
[43] G. Benadé and J. N. Hooker. Optimization bounds from the branching dual. INFORMS Journal on Computing, to appear. · Zbl 1528.90203
[44] M. Gavanelli, M. Milano, B. O’Sullivan, and A. Holland. What-if analysis through simulation-optimization hybrids. In European Conference on Modeling and Simulation, 2012.
[45] B. Gendron, R. G. Garroppo, G. Nencioni, M. G. Scutellà, and L. Tavanti. Benders decomposition for a location-design problem in green wireless local area networks. Electronic Notes in Discrete Mathematics, 41:367-374, 2013. · Zbl 1346.90235 · doi:10.1016/j.endm.2013.05.114
[46] B. Gendron, A. Lucena, A. Salles da Cunha, and L. Simonetti. Benders decomposition, branch-and-cut, and hybrid algorithms for the minimum connected dominating set problem. INFORMS Journal on Computing, 26:645-657, 2014. · Zbl 1304.90217 · doi:10.1287/ijoc.2013.0589
[47] B. Gendron, M. G. Scutellà, R. G. Garroppo, G. Nencioni, and L. Tavanti. A branch-and-Benders-cut method for nonlinear power design in green wireless local area networks. European Journal of Operational Research, 255:151-162, 2016. · Zbl 1346.90235 · doi:10.1016/j.ejor.2016.04.058
[48] A. M. Geoffrion. Generalized Benders decomposition. Journal of Optimization Theory and Applications, 10:237-260, 1972. · Zbl 0229.90024 · doi:10.1007/BF00934810
[49] A. Goldwasser and A. Schutt. Optimal torpedo scheduling. Journal of Artificial Intelligence Research, 63:955-986, 2018. · Zbl 1490.90128 · doi:10.1613/jair.1.11268
[50] J. Gong, E. E. Lee, J. E. Mitchell, and W. A. Wallace. Logic-based multiobjective optimization for restoration planning. In W. Chaovalitwongse, K. C. Furman, and P. M. Pardalos, editors, Optimization and Logistics Challenges in the Enterprise, pages 305-324. 2009. · Zbl 1172.90483
[51] O. Guyon, P. Lemaire, E. Pinson, and D. Rivreau. Solving an integrated job-shop problem with human resource constraints. Annals of Operations Research, 213:147-171, 2014. · Zbl 1296.90046 · doi:10.1007/s10479-012-1132-3
[52] I. Hamdi and T. Loukil. Logic-based Benders decomposition to solve the permutation flowshop scheduling problem with time lags. In International Conference on Modeling, Simulation and Applied Optimization (ICMSAO), pages 1-7. IEEE, 2013.
[53] I. Hamdi and T. Loukil. Upper and lower bounds for the permutation flowshop scheduling problem with minimal time lags. Optimization Letters, 9:465-482, 2015. · Zbl 1310.90067 · doi:10.1007/s11590-014-0761-7
[54] I. Harjunkoski and I. E. Grossmann. A decomposition approach for the scheduling of a steel plant production. Computers and Chemical Engineering, 25:1647-1660, 2001. · doi:10.1016/S0098-1354(01)00729-3
[55] I. Harjunkoski and I. E. Grossmann. Decomposition techniques for multistage scheduling problems using mixed-integer and constraint programming methods. Computers and Chemical Engineering, 26:1533-1552, 2002. · doi:10.1016/S0098-1354(02)00100-X
[56] A. Heching and J. N. Hooker. Scheduling home hospice care with logic-based Benders decomposition. In C.-G. Quimper, editor, CPAIOR 2016 Proceedings, pages 187-197, 2016. · Zbl 1479.90094 · doi:10.1007/978-3-319-33954-2_14
[57] A. Heching, J. N. Hooker, and R. Kimura. A logic-based Benders approach to home healthcare delivery. Transportation Science, to appear.
[58] P.-E. Hladik, H. Cambazard, A.-M. Déplanche, and N. Jussien. Solving a real-time allocation problem with constraint programming. Journal of Systems and Software, 81:132-149, 2008. · doi:10.1016/j.jss.2007.02.032
[59] K. Hoffmann. Using hybrid optimization algorithms for very-large graph problems and for small real-time problems. INFORMS Optimization Society Conference, plenary talk, 2018.
[60] J. N. Hooker. Logic-Based Methods for Optimization: Combining Optimization and Constraint Satisfaction. Wiley, New York, 2000. · Zbl 0974.90001 · doi:10.1002/9781118033036
[61] J. N. Hooker. A hybrid method for planning and scheduling. Constraints, 10:385-401, 2005. · Zbl 1122.90054 · doi:10.1007/s10601-005-2812-2
[62] J. N. Hooker. An integrated method for planning and scheduling to minimize tardiness. Constraints, 11:139-157, 2006. · Zbl 1103.68811 · doi:10.1007/s10601-006-8060-2
[63] J. N. Hooker. Integrated Methods for Optimization. Springer, 2007. · Zbl 1122.90002
[64] J. N. Hooker. Planning and scheduling by logic-based Benders decomposition. Operations Research, 55:588-602, 2007. · Zbl 1167.90512 · doi:10.1287/opre.1060.0371
[65] J. N. Hooker. Integrated Methods for Optimization, 2nd ed. Springer, 2012. · Zbl 1263.90002 · doi:10.1007/978-1-4614-1900-6
[66] J. N. Hooker and G. Ottosson. Logic-based Benders decomposition. Mathematical Programming, 96:33-60, 2003. · Zbl 1023.90082 · doi:10.1007/s10107-003-0375-9
[67] J. N. Hooker and H. Yan. Logic circuit verification by Benders decomposition. In V. Saraswat and P. Van Hentenryck, editors, Principles and Practice of Constraint Programming: The Newport Papers, pages 267-288, Cambridge, MA, 1995. MIT Press.
[68] J. Hu, J. E. Mitchell, and J.-S. Pang. An LPCC approach to nonconvex quadratic programs. Mathematical Programming, 133:243-277, 2012. · Zbl 1244.90177 · doi:10.1007/s10107-010-0426-y
[69] J. Hu, J. E. Mitchell, J.-S. Pang, K. P. Bennett, and G. Kunapuli. On the global solution of linear programs with linear complementarity constraints. SIAM Journal on Optimization, 19:445-471, 2008. · Zbl 1163.90031 · doi:10.1137/07068463x
[70] B. Kafle, G. Gange, P. Schachte, H. Søndergaard, and P. J. Stuckey. A Benders decomposition approach to deciding modular linear integer arithmetic. In S. Gaspers and T. Walsh, editors, International Conference on Theory and Applications of Satisfiability Testing, pages 380-397, 2017. · Zbl 1496.68193 · doi:10.1007/978-3-319-66263-3_24
[71] C. Kardos, A. Kovács, and J. Váncza. Decomposition approach to optimal feature-based assembly planning. CIRP Annals, 66:417-420, 2017. · doi:10.1016/j.cirp.2017.04.002
[72] J. L. Kiddoo, E. Kwerel, S. Javid, M. Dunford, G. M. Epstein, C. E. Meisch, K. L. Hoffman, B. B. Smith, A. B. Coudert, R. K. Sultana, J. A. Costa, S. Charnonneau, M. Trick, I. Segal, K. Leyton-Brown, N. Newman, A. Frechette, D. Menon, and P. Salasznyk. Operations research enables auction to repurpose television spectrum for next-generation wireless technologies. INFORMS Journal on Applied Analytics, 49:7-22, 2019. · doi:10.1287/inte.2018.0972
[73] J. Kinable and M. Trick. A logic-based Benders approach to the concrete delivery problem. In H. Simonis, editor, CPAIOR 2014 Proceedings, volume 8451 of Lecture Notes in Computer Science, pages 176-192. Springer, 2014.
[74] C. Kloimüllner, P. Papazek, B. Hu, and G. R. Raidl. A cluster-first route-second approach for balancing bicycle sharing systems. In International Conference on Computer Aided Systems Theory (EUROCAST), volume 9520 of Lecture Notes in Computer Science, pages 439-446. Springer, 2015.
[75] C. Kloimüllner and G. R. Raidl. Full-load route planning for balancing bike sharing systems by logic-based Benders decomposition. Networks, 69:439-446, 2015.
[76] S. Li, R. R. Negenborn, and G. Lodewijks. A logic-based Benders decomposition approach to improve coordination of inland vessels for inter-terminal transport. In International Conference on Computational Logistics, volume 9855 of Lecture Notes in Computer Science, pages 96-115. Springer, 2016. · Zbl 1374.90058
[77] S. Li, R. R. Negenborn, and G. Lodewijks. Closed-loop coordination of inland vessels operations in large seaports using hybrid logic-based Benders decomposition. Transportation Research Part E, 97:1-21, 2017. · doi:10.1016/j.tre.2016.10.013
[78] C. Liu, D. M. Aleman, and J. C. Beck. Modelling and solving the senior transportation problem. In W.-J. van Hoeve, editor, CPAIOR 2018 Proceedings, volume 10848 of Lecture Notes in Computer Science, pages 412-428. Springer, 2018. · Zbl 1511.90058
[79] W. Liu, Z. Gu, J. Xu, X. Wu, and Y. Ye. Satisfiability modulo graph theory for task mapping and scheduling on multiprocessor systems. IEEE Transactions on Parallel and Distributed Systems, 22:1382-1389, 2011. · doi:10.1109/TPDS.2010.204
[80] W. Liu, M. Yuan, X. He, Z. Gu, and X. Liu. Efficient SAT-based mapping and scheduling of homogeneous synchronous dataflow graphs for throughput optimization. In Real-Time Systems Symposium, pages 492-504. IEEE, 2008.
[81] M. Lombardi and M. Milano. Stochastic allocation and scheduling for conditional task graphs in MPSoCs. In F. Benhamou, editor, Principles and Practice of Constraint Programming (CP 2006), volume 4204 of Lecture Notes in Computer Science, pages 299-313. Springer, 2006.
[82] M. Lombardi, M. Milano, M. Ruggiero, and L. Benini. Stochastic allocation and scheduling for conditional task graphs in multi-processor systems-on-chip. Journal of Scheduling, 13:315-345, 2010. · Zbl 1232.68017 · doi:10.1007/s10951-010-0184-y
[83] C. Luong. An Examination of Benders Decomposition Approaches in Large-scale Healthcare Optimization Problems. PhD thesis, University of Toronto, 2015.
[84] C. T. Maravelias. A decomposition framework for the scheduling of single- and multi-stage processes. Computers and Chemical Engineering, 30:407-420, 2006. · doi:10.1016/j.compchemeng.2005.09.011
[85] C. T. Maravelias and I. E. Grossmann. Using MILP and CP for the scheduling of batch chemical processes. In J. C. Régin and M. Rueher, editors, CPAIOR 2004 Proceedings, volume 3011 of Lecture Notes in Computer Science, pages 1-20. Springer, 2004. · Zbl 1094.90559
[86] J. Maschler and G. Raidl. Logic-based Benders decomposition for the 3-staged strip packing problem. In International Conference on Operations Research (German OR Society), 2015. · Zbl 1375.90263
[87] T. Nishi, Y. Hiranaka, and I. E. Grossmann. A bilevel decomposition algorithm for simultaneous production scheduling and conflict-free routing for automated guided vehicles. Computers and Operations Research, 38:876-888, 2011. · Zbl 1202.90142 · doi:10.1016/j.cor.2010.08.012
[88] T. Nishi, T. Sugiyama, and M. Inuiguchi. Two-level decomposition algorithm for crew rostering problems with fair working condition. European Journal of Operational Research, 237:465-473, 2014. · Zbl 1304.90099 · doi:10.1016/j.ejor.2014.02.010
[89] J. Nossack, D. Briskorn, and E. Pesch. Container dispatching and conflict-free yard crane routing in an automated container terminal. Transportation Science, 52:1059-1076, 2018. · doi:10.1287/trsc.2017.0811
[90] B. Peterson and M. Trick. A Benders’ approach to a transportation network design problem. In W.-J. van Hoeve and J. N. Hooker, editors, CPAIOR 2009 Proceedings, volume 5547 of Lecture Notes in Computer Science, pages 326-327, New York, 2009. Springer.
[91] M. Raap, M. Moll, M. Zsifkovits, and S. Pickl. Utilizing dual information for moving target search trajectory optimization. In B. Hardy, A. Qazi, and S. Ravizza, editors, 5th Student Conference on Operational Research (SCOR 2016), volume 50 of OpenAccess Series in Informatics (OASIcs), pages 1:1-1:10, Dagstuhl, Germany, 2016.
[92] R. Rahmaniani, T. G. Crainic, M. Gendreau, and W. Rei. The benders decomposition algorithm: A literature review. European Journal of Operational Research, 259:801-817, 2017. · Zbl 1402.90158 · doi:10.1016/j.ejor.2016.12.005
[93] G. R. Raidl, T. Baumhauer, and B. Hu. Speeding up logic-based Benders decomposition by a metaheuristic for a bi-level capacitated vehicle routing problem. In International Workshop on Hybrid Metaheuristics, volume 8457 of Lecture Notes in Computer Science, pages 183-197. Springer, 2014.
[94] G. R. Raidl, T. Baumhauer, and B. Hu. Boosting an exact logic-based Benders decomposition approach by variable neighborhood search. Electronic Notes in Discrete Mathematics, 47:149-156, 2015. · Zbl 1466.90057 · doi:10.1016/j.endm.2014.11.020
[95] R. V. Rasmussen. Scheduling a triple round robin tournament for the best Danish soccer league. European Journal of Operational Research, 20:795-810, 2008. · Zbl 1137.90513 · doi:10.1016/j.ejor.2006.12.050
[96] R. V. Rasmussen and M. A. Trick. A Benders approach to the constrained minimum break problem. European Journal of Operational Research, 177:198-213, 2007. · Zbl 1102.90026 · doi:10.1016/j.ejor.2005.10.063
[97] M. I. Restrepo, B. Gendron, and L. M. Rousseau. Combining Benders decomposition and column generation for multi-activity tour scheduling. Computers and Operations Research, 93:151-165, 2018. · Zbl 1391.90363 · doi:10.1016/j.cor.2018.01.014
[98] S. Riazi, C. Seatzu, O. Wigstrom, and B. Lennartson. Benders/gossip methods for heterogeneous multi-vehicle routing problems. In IEEE Conference on Emerging Technologies Factory Automation (ETFA), pages 1-6, 2013.
[99] M. Riedler and G. R. Raidl. Solving a selective dial-a-ride problem with logic-based Benders decomposition. Computers and Operations Research, 96:30-54, 2018. · Zbl 1458.90131 · doi:10.1016/j.cor.2018.03.008
[100] A. Riise, C. Mannino, and L. Lamorgese. Recursive logic-based Benders’ decomposition for multi-mode outpatient scheduling. European Journal of Operational Research, 257:439-455, 2017. · Zbl 1394.90302 · doi:10.1016/j.ejor.2016.08.024
[101] V. Roshanaei, D. M. Aleman, and D. Urbach. Logic-based Benders decomposition approaches with application to operating room scheduling. In INFORMS National Meeting, 2015. · Zbl 1394.90302
[102] V. Roshanaei, C. Luong, D. M. Aleman, and D. Urbach. Collaborative operating room planning and scheduling. INFORMS Journal on Computing, 29:558-580, 2017. · Zbl 1386.90062 · doi:10.1287/ijoc.2017.0745
[103] V. Roshanaei, C. Luong, D. M. Aleman, and D. Urbach. Propagating logic-based Benders decomposition approaches for distributed operating room scheduling. European Journal of Operational Research, 257:439-455, 2017. · Zbl 1394.90302 · doi:10.1016/j.ejor.2016.08.024
[104] M. Ruggiero, A. Guerri, D. Bertozzi, F. Poletti, and M. Milano. Communication-aware allocation and scheduling framework for stream-oriented multi-processor systems-on-chip. In Proceedings of the Conference on Design, Automation and Test in Europe, pages 3-8. European Design and Automation Association, 2006.
[105] R. Sadykov. A hybrid branch-and-cut algorithm for the one-machine scheduling problem. In J. C. Régin and M. Rueher, editors, CPAIOR 2004 Proceedings, volume 3011 of Lecture Notes in Computer Science, pages 409-415. Springer, 2004. · Zbl 1094.90562
[106] R. Sadykov. A branch-and-check algorithm for minimizing the weighted number of late jobs on a single machine with release dates. European Journal of Operational Research, 189:1283-1304, 2008. · Zbl 1144.90010 · doi:10.1016/j.ejor.2006.06.078
[107] D. Salvagnin and T. Walsh. A hybrid MIP/CP approach for multi-activity shift scheduling. In M. Milano, editor, Principles and Practice of Constraint Programming, volume 7514 of Lecture Notes in Computer Science, pages 633-646. Springer, 2012.
[108] R. Sarmad, O. Wigström, and S. Carla. Benders/gossip methods for heterogeneous multi-vehicle routing problems. In IEEE International Conference on Emerging Technologies and Factory Automation (ETFA), pages 1-6. IEEE, 2013.
[109] N. Satish, K. Ravindran, and K. Keutzer. A decomposition-based constraint optimization approach for statically scheduling task graphs with communication delays to multiprocessors. In Proceedings of the Conference on Design, Automation and Test in Europe, pages 57-62. EDA Consortium, 2007.
[110] S. Shen and J. C. Smith. A decomposition approach for solving a broadcast domination network design problem. Annals of Operations Research, 210:333-360, 2011. · Zbl 1308.90190 · doi:10.1007/s10479-011-0962-8
[111] S. Solak, C. Scherrer, and A. Ghoniem. The stop-and-drop problem in nonprofit food distribution networks. Annals of Operations Research, 221:407-426, 2014. · Zbl 1301.90007 · doi:10.1007/s10479-012-1068-7
[112] Z. C. Taşkın, J. C. Smith, S. Ahmed, and A. J. Schaefer. Cutting plane algorithms for solving a stochastic edge-partition problem. Discrete Optimization, 6:420-435, 2009. · Zbl 1179.90322 · doi:10.1016/j.disopt.2009.05.004
[113] S. Tarim, S. Armagan, and I. Miguel. A hybrid Benders decomposition method for solving stochastic constraint programs with linear recourse. In B. Hnich, M. Carlsson, F. Fages, and F. Rossi, editors, International Workshop on Constraint Solving and Constraint Logic Programming (CSCLP), pages 133-148. Springer, 2006. · Zbl 1180.68252
[114] D. Terekhov, J. C. Beck, and K. N. Brown. Solving a stochastic queueing design and control problem with constraint programming. In Proceedings of the 22nd National Conference on Artificial Intelligence (AAAI 2007), volume 1, pages 261-266. AAAI Press, 2007.
[115] D. Terekhov, J. C. Beck, and K. N. Brown. A constraint programming approach for solving a queueing design and control problem. INFORMS Journal on Computing, 21:549-561, 2009. · Zbl 1243.90047 · doi:10.1287/ijoc.1080.0307
[116] D. Terekhov, M. K. Doğru, U. Özen, and J. C. Beck. Solving two-machine assembly scheduling problems with inventory constraints. Computers and Industrial Engineering, 63:120-134, 2012. · doi:10.1016/j.cie.2012.02.006
[117] E. Thorsteinsson. Branch and check: A hybrid framework integrating mixed integer programming and constraint logic programming. In T. Walsh, editor, Principles and Practice of Constraint Programming (CP 2001), volume 2239 of Lecture Notes in Computer Science, pages 16-30. Springer, 2001. · Zbl 1067.68677
[118] C. Timpe. Solving planning and scheduling problems with combined integer and constraint programming. OR Spectrum, 24:431-448, 2002. · Zbl 1028.90017 · doi:10.1007/s00291-002-0107-1
[119] T. Tran, A. Araujo, and J. C. Beck. Decomposition methods for the parallel machine scheduling problem with setups. INFORMS Journal on Computing, 28:83-95, 2016. · Zbl 1338.90184 · doi:10.1287/ijoc.2015.0666
[120] T. T. Tran and J. C. Beck. Logic-based Benders decomposition for alternative resource scheduling with sequence dependent setups. In European Conference on Artificial Intelligence (ECAI), volume 242 of Frontiers in Artificial Intelligence and Applications, pages 774-779. IOS Press, 2012. · Zbl 1327.90075
[121] M. Trick and H. Yıldız. Benders cuts guided large neighborhood search for the traveling umpire problem. In P. Van Hentenryck and L. Wolsey, editors, CPAIOR Proceedings, volume 4510 of Lecture Notes in Computer Science, pages 332-345. Springer, 2007. · Zbl 1214.90106
[122] M. Trick and H. Yıldız. Benders cuts guided large neighborhood search for the traveling umpire problem. Naval Research Logistics, pages 771-781, 2011. · Zbl 1241.90059 · doi:10.1002/nav.20482
[123] S. van Dijk. Decomposition methods and rolling horizon approach for the yard crane scheduling problem. PhD thesis, Delft University of Technology, 2015.
[124] J. Verstichel, J. Kinable, P. De Causmaecker, and G. Vanden Berghe. A combinatorial Benders decomposition for the lock scheduling problem. Computers and Operations Research, 54:117-128, 2015. · Zbl 1348.90318 · doi:10.1016/j.cor.2014.09.007
[125] D. Wheatley, F. Gzara, and E. Jewkes. Logic-based Benders decomposition for an inventory-location problem with service constraints. Omega, 55:10-23, 2015. · doi:10.1016/j.omega.2015.02.001
[126] Q. Xia, A. Eremin, and M. Wallace. Problem decomposition for traffic diversions. In J. C. Régin and M. Rueher, editors, CPAIOR 2004 Proceedings, volume 3011 of Lecture Notes in Computer Science, pages 348-363. Springer, 2004. · Zbl 1094.90515
[127] T. H. Yunes. Software tools supporting integration. In P. van Hentenryck and M. Milano, editors, Hybrid Optimization: The Ten Years of CPAIOR, pages 393-424. Springer, New York, 2011. · doi:10.1007/978-1-4419-1644-0_12
[128] T. H. Yunes, I. Aron, and J. N. Hooker. An integrated solver for optimization problems. Operations Research, 58:342-356, 2010. · Zbl 1226.90047 · doi:10.1287/opre.1090.0733
[129] G. Zakeri, A. B. Philpott, and D. M. Ryan. Inexact cuts in Benders decomposition. SIAM Journal of Optimization, 10:643-657, 2000. · Zbl 0955.90088 · doi:10.1137/S1052623497318700
[130] J. Zhu, L. Zhang, D. Qiu, and H. Li. Task scheduling for multi- · doi:10.1109/JSEE.2012.00012
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.