Abstract
Mathematical decomposition methods have been extensively used in the last decades to solve large scale optimization problems. In this chapter, we study a special class of problems that, once reformulated through Benders decomposition, exhibit mixed-integer variables in the master problem and subproblems. In these problems, some master problem variables are bounded, and cardinality constraints restrict their use. We propose two decomposition-based algorithms to address these problems. The first algorithm generates classical optimality cuts from the linear programming relaxation of the subproblem. When no more of these classical cuts can be added, the algorithm adds a new type of integer Benders optimality cut to ensure the convergence of the method to an optimal solution. The second algorithm adds the relaxation of the Benders subproblem variables in the master problem and includes these variables in the composition of integer Benders optimality cuts. These approaches were tested on two problems: the multi-commodity facility location problem and the multi-activity shift scheduling problem. Computational results are presented on numerous instances with different characteristics to demonstrate the efficacy of these approaches.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Angulo, G., Ahmed, S., & Dey, S. S. (2016). Improving the integer L-shaped method. INFORMS Journal on Computing, 28(3), 483–499.
Boyer, V., Gendron, B., & Rousseau, L. M. (2014). A branch-and-price algorithm for the multi-activity multi-task shift scheduling problem. Journal of Scheduling, 17(2), 185–197.
Carøe, C. C., & Tind, J. (1998). L-shaped decomposition of two-stage stochastic programs with integer recourse. Mathematical Programming, 83(1), 451–464.
Cordeau, J. F., Stojković, G., Soumis, F., & Desrosiers, J. (2001). Benders decomposition for simultaneous aircraft routing and crew scheduling. Transportation Science, 35(4), 375–388.
Côté, M. C., Gendron, B., & Rousseau, L. M. (2011b). Grammar-based integer programming models for multiactivity shift scheduling. Management Science, 57(1), 151–163.
Elçi, Ö., & Hooker, J. (2022). Stochastic planning and scheduling with logic-based Benders decomposition. INFORMS Journal on Computing, 34(5), 2428–2442.
Gade, D., Küçükyavuz, S., & Sen, S. (2014). Decomposition algorithms with parametric Gomory cuts for two-stage stochastic integer programs. Mathematical Programming, 144(1–2), 39–64.
Gendron, B., Scutellà, M. G., Garroppo, R. G., Nencioni, G., & Tavanti, L. (2016). A branch-and-Benders-cut method for nonlinear power design in green wireless local area networks. European Journal of Operational Research, 255(1), 151–162.
Hooker, J. N., & Ottosson, G. (2003). Logic-based Benders decomposition. Mathematical Programming, 96(1), 33–60.
Kim, K., & Mehrotra, S. (2015). A two-stage stochastic integer programming approach to integrated staffing and scheduling with application to nurse management. Operations Research, 63(6), 1431–1451.
Laporte, G., & Louveaux, F. V. (1993). The integer L-shaped method for stochastic integer programs with complete recourse. Operations Research Letters, 13(3), 133–142.
Li, C., & Grossmann, I. E. (2019). A generalized Benders decomposition-based branch and cut algorithm for two-stage Benders programs with nonconvex constraints and mixed-binary first and second stage variables. Journal of Global Optimization, 75, 247–272.
Magnanti, T. L., & Wong, R. T. (1981). Accelerating Benders decomposition: Algorithmic enhancement and model selection criteria. Operations Research, 29(3), 464–484.
McDaniel, D., & Devine, M. (1977). A modified Benders’ partitioning algorithm for mixed integer programming. Management Science, 24(3), 312–319.
Papadakos, N. (2008). Practical enhancements to the Magnanti–Wong method. Operations Research Letters, 36(4), 444–449.
Qi, Y., & Sen, S. (2017). The ancestral Benders’ cutting plane algorithm with multi-term disjunctions for mixed-integer recourse decisions in stochastic programming. Mathematical Programming, 161(1–2), 193–235.
Rahmaniani, R., Crainic, T. G., Gendreau, M., & Rei, W. (2017). The benders decomposition algorithm: A literature review. European Journal of Operational Research, 259(3), 801–817.
Restrepo, M. I., Gendron, B., & Rousseau, L. M. (2018). Combining Benders decomposition and column generation for multiactivity tour scheduling. Computers and Operations Research, 93, 151–165.
Sen, S., & Higle, J. L. (2005). The C3 theorem and a D2 algorithm for large scale stochastic mixed-integer programming: Set convexification. Mathematical Programming, 104(1), 1–20.
Sen, S., & Sherali, H. D. (2006). Decomposition with branch-and-cut approaches for two-stage stochastic mixed-integer programming. Mathematical Programming, 106(2), 203–223.
Sherali, H. D., & Fraticelli, B. M. (2002). A modification of Benders’ decomposition algorithm for discrete subproblems: An approach for stochastic programs with integer recourse. Journal of Global Optimization, 22(1–4), 319–342.
Sherali, H. D., & Zhu, X. (2006). On solving discrete two-stage stochastic programs having mixed-integer first-and second-stage variables. Mathematical Programming, 108(2), 597–616.
Wolsey, L. A. (2020). Integer programming. John Wiley & Sons.
Zhang, M., & Küçükyavuz, S. (2014). Finitely convergent decomposition algorithms for two-stage stochastic pure integer programs. SIAM Journal on Optimization, 24(4), 1933–1951.
Acknowledgements
The authors would like to thank Serge Bisaillon for generating the MCFLP instances and for providing help in the implementation of the Benders decomposition algorithms.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this chapter
Cite this chapter
Restrepo, MI., Gendron, B., Rousseau, LM. (2024). Decomposition-Based Algorithms for Mixed-Integer Linear Programs with Integer Subproblems. In: Crainic, T.G., Gendreau, M., Frangioni, A. (eds) Combinatorial Optimization and Applications. International Series in Operations Research & Management Science, vol 358. Springer, Cham. https://doi.org/10.1007/978-3-031-57603-4_11
Download citation
DOI: https://doi.org/10.1007/978-3-031-57603-4_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-57602-7
Online ISBN: 978-3-031-57603-4
eBook Packages: Business and ManagementBusiness and Management (R0)