Since the benders algorithm is finite, there a maximum number of cuts that could theoretically be added. The worst case is that I add cuts for all extreme points and all extreme rays that are part of the full benders reformulation.

I was wondering, is there a method to calculate this number of maximum cuts?

The reason being: my implementation right now is painfully slow, and for a certain problem size I get a stack overflow after about 2500 iterations.

that means obviously, 2500 have been added already. since my problem size is still rather small, I was wondering if that would even be possible or if there is a mistake in my code. So i thought that if I knew the maximum number of cuts that could be in the worst case be added, I would know if adding 2500 cuts even makes sense.

  • $\begingroup$ Maybe section 2.4 of Generalized Benders decomposition (10.1007/BF00934810) may help you. $\endgroup$ Commented Nov 2, 2023 at 15:29
  • $\begingroup$ Thanks; I'll take a look! $\endgroup$ Commented Nov 3, 2023 at 8:30


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.