12
$\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$
5
+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. Four 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.

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.
| improve this answer | |
$\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.

| improve this answer | |
$\endgroup$
  • $\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 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 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$ – Rolf van Lieshout Sep 8 at 8:06
  • 1
    $\begingroup$ I also added the paper you mentioned. $\endgroup$ – Rolf van Lieshout Sep 8 at 8:06

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.