How to handle an IP sub-problem with an objective function in Benders Decomposition

Question

I have a question on Benders Decomposition (BD). Suppose I have an MILP model which can be decomposed into a master problem (MP) including integer and continuous variables and a subproblem (SP) including only integer variables. In addition, suppose that the SP generated does not hold any nice property like total unimodularity meaning that the relaxation does not do any good for me. In this case, I cannot utilize the duality theorem to generate a Benders cut.

I am familiar with Logic-Based BD (LBBD). Yet, in all the studies that I have seen using LBBD, SP becomes a feasibility problem without an objective function, which is solved by constraint programming (CP).

Now, let's further assume that the SP has a solid objective function. I was wondering if there are recent studies containing LBBD where SP is an IP with an objective function and is not solved with CP. If not, what are some viable approaches to tackle such problem settings?

Answer 1

I was researching the topic with mixed-integer subproblems in the context of two-stage stochastic programs, but got stuck and haven't revisited. In the mixed-integer case, there has been some progress recently, maybe you can apply some of the findings to your problem. Some promising recent studies and some additional pointers:

• Rahmaniani, R., Ahmed, S., Crainic, T. G., Gendreau, M., & Rei, W. (2020). The benders dual decomposition method. Operations Research.
• Zou, J., Ahmed, S., & Sun, X. A. (2019). Stochastic dual dynamic integer programming. Mathematical Programming, 175(1-2), 461-502.
• Li, C., & Grossmann, I. E. (2019). A generalized Benders decomposition-based branch and cut algorithm for two-stage stochastic programs with nonconvex constraints and mixed-binary first and second stage variables. Journal of Global Optimization, 75(2), 247-272.
• Kim, K., & Zavala, V. M. (2018). Algorithmic innovations and software for the dual decomposition method applied to stochastic mixed-integer programs. Mathematical Programming Computation, 10(2), 225-266.
• The last paragraph of Section 3.2 offers references for pure integer subproblems (mostly LBBD) and mixed-integer subproblems, and conditions for the validity of cuts. Ahmed, S. (2010). Two‐Stage Stochastic Integer Programming: A Brief Introduction. Wiley Encyclopedia of Operations Research and Management Science.
• Zheng, Q. P., Wang, J., Pardalos, P. M., & Guan, Y. (2013). A decomposition approach to the two-stage stochastic unit commitment problem. Annals of Operations Research, 210(1), 387-410.
• van der Laan, N., & Romeijnders, W. (2020). A Converging Benders’ Decomposition Algorithm for Two-stage Mixed-integer Recourse Models.
• van der Laan, N., & Romeijnders, W. (2021). A loose Benders decomposition algorithm for approximating two-stage mixed-integer recourse models. Mathematical Programming, 190(1), 761-794. (approximate method)
• Chen, R., & Luedtke, J. (2022). On generating Lagrangian cuts for two-stage stochastic integer programs. INFORMS Journal on Computing.
• Dumouchelle, J., Patel, R., Khalil, E. B., & Bodur, M. (2022). Neur2SP: Neural Two-Stage Stochastic Programming. arXiv preprint arXiv:2205.12006. (heuristic)

Consider that decomposition methods might not be faster than commercial solvers, depending on the sophistication of the decomposition approach. See

• Bonami, P., Salvagnin, D., & Tramontani, A. (2020). Implementing Automatic Benders Decomposition in a Modern MIP Solver. In International Conference on Integer Programming and Combinatorial Optimization (pp. 78-90). Springer, Cham.

Answer 2

It is possible to have an integer subproblem with an objective, but to solve such a problem you need to branch on variables both in the master problem and in the sub-problem. This is not supported by off-the-shelf solvers, so it requires quite some coding to make this work (fast).

A recent example of a paper using this method is Zeighami and Soumis (2019), who base their work on Cordeau et al. (2001). The authors use Benders to tackle simultaneous crew pairing and crew assignment. In their approach, they put the crew scheduling part, which is an integer programming problem, in the subproblem. They solve the problem using branch-and-price-and-cut, branching both on variables in the master and in the subproblem.

Answer 3

Following are some examples that include objective functions in their logic-based Benders sub problems.

• Baloch, G., Gzara, F., 2020. Strategic Network Design for Parcel Delivery with Drones Under Competition. Transportation Science 54, 204–228. https://doi.org/10.1287/trsc.2019.0928

• Barzanji, R., Naderi, B., Begen, M.A., 2020. Decomposition algorithms for the integrated process planning and scheduling problem. Omega 93, 102025. https://doi.org/10.1016/j.omega.2019.01.003

• Guo, C., Bodur, M., Aleman, D.M., Urbach, D.R., 2021. Logic-Based Benders Decomposition and Binary Decision Diagram Based Approaches for Stochastic Distributed Operating Room Scheduling. INFORMS Journal on Computing ijoc.2020.1036. https://doi.org/10.1287/ijoc.2020.1036

• Naderi, B., Roshanaei, V., 2020. Branch-Relax-and-Check: A tractable decomposition method for order acceptance and identical parallel machine scheduling. European Journal of Operational Research 286, 811–827. https://doi.org/10.1016/j.ejor.2019.10.014

• Roshanaei, V., Luong, C., Aleman, D.M., Urbach, D., 2017. Propagating logic-based Benders’ decomposition approaches for distributed operating room scheduling. European Journal of Operational Research 257, 439–455. https://doi.org/10.1016/j.ejor.2016.08.024

• Roshanaei, V., Naderi, B., 2021. Solving integrated operating room planning and scheduling: Logic-based Benders decomposition versus Branch-Price-and-Cut. European Journal of Operational Research 293, 65–78. https://doi.org/10.1016/j.ejor.2020.12.004

• Tran, T.T., Araujo, A., Beck, J.C., 2016. Decomposition Methods for the Parallel Machine Scheduling Problem with Setups. INFORMS Journal on Computing 28, 83–95. https://doi.org/10.1287/ijoc.2015.0666

• Zhang, Y., Lin, W.-H., Huang, M., Hu, X., 2019. Multi-warehouse package consolidation for split orders in online retailing. European Journal of Operational Research. https://doi.org/10.1016/j.ejor.2019.07.004

When sub problem is solved by constraint programming (CP), the Benders cut is "feasibility cut". When sub problem have an objective function, it have to be solved with an MIP solver (when subproblem contains integer variable), and the Benders cut is "optimality cut".

Based on my experience on implementing logic-based Benders decomposition (LBBD), the reason that most of previous works modeling subproblem as feasibility-checking problem is, to solve subproblem to optimum (find optimal solution / prove optimality) is far more time consuming than CP. Include objective function in subproblem make LBBD inefficient consider that subproblems have to be solved many times.