2
$\begingroup$

I am solving an LP (i.e 118-bus system economic dispatch for 130% loading) using Benders decomposition. The problem takes 26 iterations to converge. This means that the process adds 25 cuts to the master problem till convergence. Then I saved those 25 cuts.

In the next step, I want to rerun the benders process. For the purpose of an experiment, I added the first 15 cuts (out of those 25 saved cuts) to the master problem before the first iteration. Intuitively, the problem should now converge within 11 iterations (or after generating and adding 10 cuts).

However, this time the benders process does not converge within 11 iterations rather it takes 21 iterations. Why is it taking 10 (=21-11) extra iterations to solve the problem?

I am using Yalmip(matlab) with cplex solver(1210).

Improve this question
$\endgroup$
5
  • $\begingroup$ Did you preserve the order of the first 15 cuts from the first run? More generally, did you preserve the order of all variables and constraints? $\endgroup$
    – RobPratt
    Jul 20, 2021 at 20:34
  • $\begingroup$ Yes, I preserved the order of cuts when adding them in the 2nd run. Also, one more observation is that when adding the first 9 cuts to the master problem for the 2nd run, it should take (26-9) =17 iterations. But it actually takes 20 iterations to converge. This means the number of extra iterations is (20-17) =3. This shows that the number of extra iterations depends on how many cuts I am adding. $\endgroup$
    – Fouad Hasan
    Jul 20, 2021 at 21:03
  • 1
    $\begingroup$ Why is "he problem should now converge within 11 iterations(or after generating and adding 10 cuts" intuitive? My intuition is I don't know what's going to happen. $\endgroup$
    – Mark L. Stone
    Jul 20, 2021 at 21:54
  • $\begingroup$ Hi, to my understanding, it should converge within 11 iterations because we already added the exact same first 15 cuts to the master problem. Now after the first iteration of the second run, the new generated cut should be the same as the 16th cut of the first run and so on. In this way, it should generate the unused cuts and converge within 11 iterations. Isn't it? $\endgroup$
    – Fouad Hasan
    Jul 21, 2021 at 14:52
  • $\begingroup$ After a close inspection, I found that the 15 constraints (which were added in the first iteration) were being deleted during the second iteration. That's why the benders process was recreating those cuts. This makes the total number of iterations higher than the iteration number of the original problem. $\endgroup$
    – Fouad Hasan
    Jul 22, 2021 at 21:20

1 Answer 1

Reset to default
2
$\begingroup$

When you add any number of the original cuts (presumably as constraints, rather than lazy constraints or user cuts) and then restart the solver, CPLEX will go through a presolve step, the results of which may be different from the original presolve due to the presence of the extra constraints. It will then solve the root LP, the solution to which will likely be different from the solution to the original root LP, and so on.

So the branch-and-bound tree in the second run may well be significantly different from the tree in the first run. That can lead to CPLEX encountering different "feasible" solutions along the way, leading to different Benders cuts. Whether the second run reaches optimality with more, fewer or the same number of cuts as the number of unused cuts from the first run is largely a matter of luck.

Update: Oops! I thought the master problem was a MIP, when it was clearly stated to be an LP.

The master problem in the second approach will be different from that of the first even if presolve makes no changes in either of them. If CPLEX starts the second master at a different vertex from the vertex at which the 15th cut was found, it may lead to a different master solution, triggering a different cut, and so on. It might be interesting to record the master problem basis after the 15th cut is added and the master is solved again in the first approach, add the first 15 cuts, then start again using the recorded basis as the starting solution to the LP. I'm still not sure that would generate the same sequence of cuts (partly due to presolving, partly due to random tie-breaking whenever there is a tie for the best column to enter into the basis), but perhaps it would.

Improve this answer
$\endgroup$
5
  • $\begingroup$ The idea of presolve makes sense. But the argument regarding the branch and bound is not clear. As Cplex would apply branch and bound for MIP problems whereas my problem is simple LP (simplex or interior point will be used by cplex). $\endgroup$
    – Fouad Hasan
    Jul 21, 2021 at 6:33
  • $\begingroup$ Good point. I saw LP in the original question, but pretty much every Benders application I've seen in recent years has been a MILP (since LP solvers can now handle really large LPs without decomposition), so I thought that was a typo. My mistake. I'll edit the response. $\endgroup$
    – prubin ♦
    Jul 21, 2021 at 20:53
  • $\begingroup$ Thank you for sharing your insight. You are absolutely correct. Most of the papers, these days, apply benders for MILP. Solving LP is already very fast. However, I was trying to verify some ideas with LP as it takes less time to solve. Solution: After a close inspection, I found that the 15 constraints (which were added in the first iteration) were being deleted during the second iteration. That's why the benders process was recreating those cuts. This makes the total number of iterations higher than the iteration number of the original problem. $\endgroup$
    – Fouad Hasan
    Jul 22, 2021 at 21:19
  • $\begingroup$ I take it the 15 deleted constraints were the 15 Benders cuts you added before starting the second solution? If so, were they removed during presolve? I can see how that might happen (because the presolver doesn't "see" the Benders subproblems, just the master). If that is what happened, turning off presolving of the second master should stop it (but with unknown effect on solution time). $\endgroup$
    – prubin ♦
    Jul 23, 2021 at 23:17
  • $\begingroup$ Thank you very much for mentioning that presolve issue. However, in this case, the issue occurred because of the way I used the 'for' loop to add those 15 cuts inside the master problem. That for loop was not working during the second interation (I was clearing all cuts at the start of each benders iteration and added them back during start). Fortunately, after modifying the 'for' loop It is solved. $\endgroup$
    – Fouad Hasan
    Jul 25, 2021 at 15:21

Your Answer

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

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