zbMATH — the first resource for mathematics

Implementing the branch-and-cut approach for a general purpose Benders’ decomposition framework. (English) Zbl 07354607
Summary: Benders’ decomposition is a popular mathematical and constraint programming algorithm that is widely applied to exploit problem structure arising from real-world applications. While useful for exploiting structure in mathematical and constraint programs, the use of Benders’ decomposition typically requires significant implementation effort to achieve an effective solution algorithm. Traditionally, Benders’ decomposition has been viewed as a problem specific algorithm, which has limited the development of general purpose algorithms and software solutions. This paper presents a general purpose Benders’ decomposition algorithm that is capable of handling many classes of mathematical and constraint programs and provides extensive flexibility in the implementation and use of this algorithm. A branch-and-cut approach for Benders’ decomposition has been implemented within the constraint integer programming solver SCIP using a plugin-based design to allow for a wide variety of extensions and customisations to the algorithm. The effectiveness of the Benders’ decomposition algorithm and available enhancement techniques is assessed in a comprehensive computational study.
90Bxx Operations research and management science
Full Text: DOI
[1] Achterberg, T., Constraint Integer Programming (2007), Technische Universität Berlin, Ph.D. thesis. · Zbl 1430.90427
[2] Ahmed, S., Garcia, R., Kong, N., Ntaimo, L., Parija, G., Qiu, F., & Sen, S. (2015). SIPLIB: a stochastic integer programming test problem library. See http://www2.isye.gatech.edu/ sahmed/siplib/Last accessed: 21-04-2020.
[3] Angulo, G.; Ahmed, S.; Dey, S. S., Improving the integer L-shaped method, INFORMS Journal on Computing, 28, 3, 483-499 (2016) · Zbl 1348.90498
[4] Ariyawansa, K. A.; Felt, A. J., On a new collection of stochastic linear programming test problems, INFORMS Journal on Computing, 16, 3, 291-299 (2004) · Zbl 1239.90081
[5] Bastubbe, M., Modular detection of model structure in integer programming, SCIP Workshop, RWTH Aachen (2018)
[6] Benders, J. F., Partitioning procedures for solving mixed-variables programming problems, Numerische Mathematik, 4, 1, 238-252 (1962) · Zbl 0109.38302
[7] Bergner, M.; Caprara, A.; Ceselli, A.; Furini, F.; Lübbecke, M.; Malaguti, E.; Traversi, E., Automatic Dantzig-Wolfe reformulation of mixed integer programs, Mathematical Programming, 149, 1-2, 391-424 (2015) · Zbl 1307.90114
[8] Berthold, T., Measuring the impact of primal heuristics, Operations Research Letters, 41, 6, 611-614 (2013) · Zbl 1287.90037
[9] Birge, J. R.; Dempster, M. A.; Gassmann, H. I.; Gunn, E.; King, A. J.; Wallace, S. W., A standard input format for multiperiod stochastic linear programs, Technical Report (1987), IIASA, Laxenburg, Austria
[10] Bodur, M.; Dash, S.; Günlük, O.; Luedtke, J., Strengthened Benders cuts for stochastic integer programs with continuous recourse, INFORMS Journal on Computing, 29, 1, 77-91 (2017) · Zbl 1364.90220
[11] Botton, Q.; Fortz, B.; Gouveia, L.; Poss, M., Benders decomposition for the hop-constrained survivable network design problem, INFORMS Journal on Computing, 25, 1, 13-26 (2013)
[12] Codato, G.; Fischetti, M., Combinatorial Benders’ cuts for mixed-integer linear programming, Operations Research, 54, 4, pp.756-766 (2006) · Zbl 1167.90601
[13] Cordeau, J.-F.; Stojković, G.; Soumis, F.; Desrosiers, J., Benders’ decomposition for simultaneous aircraft routing and crew scheduling, Transportation Science, 35, 4, 375-388 (2001) · Zbl 1069.90525
[14] Dolan, E. D.; Moré, J. J., Benchmarking optimization software with performance profiles, Mathematical Programming, 91, 2, 201-213 (2002) · Zbl 1049.90004
[15] Felt, A. (2015) Test-problem collection for stochastic linear programming. See https://www4.uwsp.edu/math/afelt/slptestset.htmlLast accessed: 21-04-2020.
[16] FICO FICO Xpress-Optimizer. (2020) See https://www.fico.com/en/products/fico-xpress-optimizationLast accessed: 21-04-2020.
[17] Fischetti, M.; Ljubić, I.; Sinnl, M., Redesigning Benders decomposition for large-scale facility location, Management Science, 63, 7, 2146-2162 (2017)
[18] Fortz, B.; Poss, M., An improved Benders decomposition applied to a multi-layer network design problem, Operations Research Letters, 37, 5, 359-364 (2009) · Zbl 1279.90025
[19] Froyland, G.; Maher, S. J.; Wu, C.-L., The recoverable robust tail assignment problem, Transportation Science, 48, 3, 351-372 (2014)
[20] Galati, M.; Ralphs, T.; Wang, J., Computational experience with generic decomposition using the DIP framework, Proceedings of ramp 2012 (2012)
[21] Gamrath, G.; Fischer, T.; Gally, T.; Gleixner, A. M.; Hendel, G.; Koch, T.; Witzig, J., The SCIP Optimization Suite 3.2, Technical Report (2016), Zuse Institute Berlin
[22] Geoffrion, A., Generalized Benders decomposition, Journal of Optimization Theory and Applications, 10, 4, 237-260 (1972) · Zbl 0229.90024
[23] Geoffrion, A. M.; Graves, G. W., Multicommodity distribution system design by Benders’ decomposition, Management Science, 20, 5, 822-844 (1974) · Zbl 0304.90122
[24] Gleixner, A.; Bastubbe, M.; Eifler, L.; Gally, T.; Gamrath, G.; Gottwald, R. L.; Witzig, J., The SCIP Optimization Suite 6.0, Technical Report (2018), Zuse Institute Berlin
[25] Gurobi (2020) Gurobi - The fastest solver. See https://www.gurobi.com/Last accessed: 21-04-2020.
[26] Hart, W. E.; Watson, J.-P.; Woodruff, D. L., Pyomo: modeling and solving mathematical programs in Python, Mathematical Programming Computation, 3, 3, 219 (2011)
[27] Helmberg, C. (2011). The ConicBundle library for convex optimization. http://www-user.tu-chemnitz.de/ helmberg/ConicBundle.
[28] Huchette, J.; Lubin, M.; Petra, C., Parallel algebraic modeling for stochastic optimization, Proceedings of the 1st first workshop for high performance technical computing in dynamic languages. Proceedings of the 1st first workshop for high performance technical computing in dynamic languages, HPTCDL ’14, 29-35 (2014), IEEE Press: IEEE Press Piscataway, NJ, USA
[29] IBM. (2020) IBM ILOG CPLEX optimization studio. See https://www.ibm.com/products/ilog-cplex-optimization-studioLast accessed: 21-04-2020.
[30] Jünger, M.; Thienel, S., The ABACUS system for branch-and-cut-and-price algorithms in integer programming and combinatorial optimization, Software: Practice and Experience, 30, 11, 1325-1352 (2000) · Zbl 1147.90416
[31] Kim, K.; Zavala, V. M., Algorithmic innovations and software for the dual decomposition method applied to stochastic mixed-integer programs, Mathematical Programming Computation, 10, 2, 225-266 (2018) · Zbl 1400.90236
[32] Ladányi, L.; Ralphs, T. K.; Trotter, L. E., Branch, cut, and price: Sequential and parallel, (Jünger, M.; Naddef, D., Computational combinatorial optimization: Optimal or provably near-optimal solutions (2001), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 223-260 · Zbl 1052.90107
[33] Laporte, G.; Louveaux, F. V., The integer L-shaped method for stochastic integer programs with complete recourse, Operations Research Letters, 13, 3, 133-142 (1993) · Zbl 0793.90043
[34] Lubin, M.; Martin, K.; Petra, C. G.; Sandıkçı, B., On parallelizing dual decomposition in stochastic integer programming, Operations Research Letters, 41, 3, 252-258 (2013) · Zbl 1286.90102
[35] Magnanti, T.; Wong, R., Accelerating Benders’ decomposition: Algorithmic enhancement and model selection criteria, Operations Research, 29, 3, 464-484 (1981) · Zbl 0455.90064
[36] Maher, S.; Miltenberger, M.; Pedroso, J. P.; Rehfeldt, D.; Schwarz, R.; Serrano, F., PySCIPOpt: Mathematical programming in Python with the SCIP Optimization Suite, Mathematical software - ICMS 2016, 9725, 301-307 (2016) · Zbl 1434.90005
[37] Maher, S. J., Enhancing large neighbourhood search heuristics for Benders’ decomposition, Technical Report (2019), Lancaster University
[38] Maher, S. J.; Desaulniers, G.; Soumis, F., Recoverable robust single day aircraft maintenance routing problem, Computers & Operations Research, 51, 130-145 (2014) · Zbl 1348.90445
[39] Markert, A., & Gollmer, R. (2008). Users guide to ddsip: A C package for the dual decomposition of two-stage stochastic programs with mixed-integer recourse.
[40] McDaniel, D.; Devine, M., A modified Benders’ partitioning algorithm for mixed integer programming, Management Science, 24, 3, 312-319 (1977) · Zbl 0371.90102
[41] Mercier, A.; Cordeau, J.; Soumis, F., A computational study of Benders’ decomposition for the integrated aircraft routing and crew scheduling problem, Computers & Operations Research, 32, 6, 1451-1476 (2005) · Zbl 1122.90355
[42] Álvarez Miranda, E.; Fernández, E.; Ljubić, I., The recoverable robust facility location problem, Transportation Research Part B: Methodological, 79, 93-120 (2015)
[43] Mulvey, J. M.; Ruszczyński, A., A new scenario decomposition method for large-scale stochastic optimization, Operations Research, 43, 3, 477-490 (1995) · Zbl 0843.90086
[44] Naoum-Sawaya, J.; Elhedhli, S., An interior-point Benders based branch-and-cut algorithm for mixed integer programs, Annals of Operations Research, 210, 1, 33-55 (2013) · Zbl 1284.90042
[45] Nemhauser, G. L.; Savelsbergh, M. W.; Sigismondi, G. C., MINTO, a Mixed INTeger Optimizer, Operations Research Letters, 15, 1, 47-58 (1994) · Zbl 0806.90095
[46] Pan, F.; Morton, D. P., Minimizing a stochastic maximum-reliability path, Networks, 52, 3, 111-119 (2008) · Zbl 1172.90345
[47] Papadakos, N., Practical enhancements to the Magnanti-Wong method, Operations Research Letters, 36, 4, 444-449 (2008) · Zbl 1155.90432
[48] Papadakos, N., Integrated airline scheduling, Computers & Operations Research, 36, 1, 176-195 (2009) · Zbl 1163.90007
[49] Puchinger, J.; Stuckey, P. J.; Wallace, M. G.; Brand, S., Dantzig-Wolfe decomposition and branch-and-price solving in G12, Constraints, 16, 1, 77-99 (2011) · Zbl 1213.90174
[50] Rahmaniani, R.; Crainic, T. G.; Gendreau, M.; Rei, W., The Benders decomposition algorithm: a literature review, European Journal of Operational Research, 259, 3, 801-817 (2017) · Zbl 1402.90158
[51] Ralphs, T.; Güzelsoy, M., The SYMPHONY Callable Library for Mixed Integer Programming, Proceedings of the ninth informs computing society conference, 61-76 (2005)
[52] Ralphs, T. K.; Ladányi, L.; Saltzman, M. J., Parallel branch, cut, and price for large-scale discrete optimization, Mathematical Programming, 98, 1-3, 253-280 (2003) · Zbl 1082.90102
[53] Santoso, T.; Ahmed, S.; Goetschalckx, M.; Shapiro, A., A stochastic programming approach for supply chain network design under uncertainty, European Journal of Operational Research, 167, 1, 96-115 (2005) · Zbl 1075.90010
[54] SCIP (2020) SCIP: Solving Constraint Integer Programs. http://scip.zib.de/ Last accessed: 21-04-2020.
[55] Thorsteinsson, E., Branch-and-check: A hybrid framework integrating mixed integer programming and constraint logic programming, Principles and practice of constraint programming - CP 2001, 16-30 (2001), Springer · Zbl 1067.68677
[56] Vanderbeck, F. (2005). BaPCod—A generic branch-and-price code. See https://raweb.inria.fr/rapportsactivite/RA2010/realopt/uid22.htmlLast accessed: 21-04-2020.
[57] Watson, J.-P.; Woodruff, D. L.; Hart, W. E., PySP: modeling and solving stochastic programs in Python, Mathematical Programming Computation, 4, 2, 109-149 (2012) · Zbl 1275.90049
[58] Xu, Y.; Ralphs, T. K.; Ladányi, L.; Saltzman, M. J., Computational experience with a software framework for parallel integer programming, The INFORMS Journal on Computing, 21, 3, 383-397 (2009) · Zbl 1243.90010
[59] Zverovich, V.; Fábián, C. I.; Ellison, E. F.D.; Mitra, G., A computational study of a solver system for processing two-stage stochastic LPs with enhanced Benders decomposition, Mathematical Programming Computation, 4, 3, 211-238 (2012) · Zbl 1275.90050
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.