13
$\begingroup$

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?

$\endgroup$

3 Answers 3

6
+50
$\begingroup$

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.
$\endgroup$
10
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ I took a look at the paper. When saying branching both on variables in MP ans SP, you do not mean that they integrate the branching decisions, do you? As far as I understand, they tackle both MP and SP via column generation approach meaning that MP is solved by CG and then the fixed solution is passed to SP to solve it via CG. In fact, they first solve the LP relaxation of both MP and SP with Benders fashion. Then, they bring back to integrality constraints only for the MP and repeat the Benders. As a final step, they bring back to integrality constraints for the SP, and finish the problem. $\endgroup$
    – whitepanda
    Sep 7, 2020 at 16:15
  • $\begingroup$ Also, for those who are interested in this three-phase approach proposed by Cordeau et al. (2001), one of the co-authors of the same paper seems to improve the algorithm (see pubsonline.informs.org/doi/10.1287/trsc.2019.0892). Maybe you can add this paper to your answer for others to see. $\endgroup$
    – whitepanda
    Sep 7, 2020 at 16:19
  • 1
    $\begingroup$ I meant that if you want to be sure that your method is exact, you need to branch on MP and SP variables in your branch-and-bound tree. For example, you could start by branching on the MP variables until the MP is integer. Then, if the SP is fractional you branch on the SP variables. However, after you have branched on a SP variable, it is possible that the MP in no longer integral, so you branch on a MP variable again. If you don't care about exactness, you can use some heuristic branching/fixing strategies to speed up the approach (as did Cordeau). $\endgroup$ Sep 8, 2020 at 8:06
  • 1
    $\begingroup$ I also added the paper you mentioned. $\endgroup$ Sep 8, 2020 at 8:06
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.