3
$\begingroup$

I'm working on a location problem and I have an issue with the Benders decomposition. I'm using Cplex with Python. I coded a single cut and a multi-cut to compare.

The single-cut implementation takes a very long time to run. It requires huge amounts of time to add several cuts (~5000 sec for 7 cuts on a 50 node network). Meanwhile, the multi-cut takes less time (40 sec) to add 500-7000x the number of cuts.

1- Where do you think the problem is coming from?

2- Is there a way to know how many subproblems the code is creating and solving? and if there are any Cplex built-in functions to do this?

Improve this question
$\endgroup$
3
  • $\begingroup$ There is no guarantee that Benders will work faster than cplex out of the box. In fact it often won’t, as you discovered. Cplex uses lots of MIP optimization techniques and has gotten good at determining which one to use for a given problem. You are choosing one MIP technique. Cplex may well beat Benders or any other given method. $\endgroup$
    – LarrySnyder610
    Commented Aug 10, 2020 at 12:13
  • $\begingroup$ I agree with you, but what's odd in this Benders code is that it takes a very long time to apply a small number of cuts (5000 sec for 6 cuts) and this doesn't make sense. $\endgroup$
    – Almufa
    Commented Aug 10, 2020 at 12:18
  • $\begingroup$ In that case you might want to revise your question to focus on that concern. $\endgroup$
    – LarrySnyder610
    Commented Aug 10, 2020 at 12:26

1 Answer 1

Reset to default
1
$\begingroup$

If all the cuts you generate have an impact (i.e., you don't generate cuts that are rendered redundant by other cuts), then at least some of the reason that adding a bunch of cuts at once is faster than adding one at a time is that you update the node LP after each cut is added in the first case, and only after all the cuts are added in the second case. So you might look at the iteration count in the CPLEX log, and see if the first method is racking up a lot more iterations adding 7 cuts than the second method does adding a comparable number of cuts (which might be just one call to the callback).

That said, 5000 seconds for 7 cuts on a small network sound pretty high, so I would not rule out a problem with your code.

As far as the number of subproblems, you can just put a little code in the callback to increment a counter each time the callback is called.

Improve this answer
$\endgroup$

Your Answer

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

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