I am wondering if optimality cuts in Benders algorithm exclude the possibility to have the same solutions and as a result, have the same optimality cut? I don't know why it is not possible to have the same cuts in different iterations of Benders decomposition algorithm.
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
It depends on whether you consider the master variable $\eta$ to be part of the solution. You can get the same master $x$ with a different $\eta$ after adding an optimality cut, but then the Benders decomposition algorithm would terminate because the solution is optimal to the original problem.
-
$\begingroup$ So, you mean that we may have the same variables (complicated variables) and optimality cut if we have reached the optimal solution? So, why the optimality cut excludes the current complicated cut if the optimal solution is not reached? $\endgroup$– AminApr 15, 2020 at 22:55
-
$\begingroup$ Yes, the following can happen in a minimization problem. Solve master problem, yielding solution $(\eta^1, x^1)$. Solve subproblem with fixed $x=x^1$, revealing that the master has underestimated the true objective value, which is $\eta^2 > \eta^1$ for that $x^1$. Add optimality cut to master, and solve again, yielding $(\eta^2, x^1)$. Solving the subproblem would not yield an optimality cut, and you are done. $\endgroup$– RobPrattApr 15, 2020 at 23:02
$\begingroup$
$\endgroup$
3
If I understand the question correctly, it is not possible to have the same optimality cut generated twice because (a) cuts are cumulative and (b) an optimality cut is only generated when an allegedly integer-feasible solution would violate the generated cut. So if you get solution 1, use it to generate cut 1 (which is added to the master), then get solution 2 which is feasible in the current master, solution 2 must satisfy cut 1. It may still incorrectly estimate the objective contribution of the subproblem, leading to another optimality cut (call it cut 2), but that cut will be different from cut 1 because solution 2 will satisfy cut 1 but violate cut 2.
If you are adding cuts on the fly via callback (rather than solving the master all the way, adding a cut, then solving the master again), and if you are using multiple threads, it might be possible for two different threads to trigger generation of the same cut before the cut makes it into the master (and is propagated to the various child processes). That would be fairly rare. Also, and again referring to the "one tree" approach, some solvers will let you allow cuts to expire. (CPLEX, for instance, refers to such cuts as "purgeable".) If you add optimality cuts that can and in some cases do expire, you run the risk to see them generated anew. Again, this would be pretty rare.
-
-
$\begingroup$ Dear @prubin. Could you please let me know why the current combination of master and dual variables violate the new generate optimality cut? Is it possible that the new cut be redundant and former cuts are stronger? Intuitively, I think it is acceptable to me but theoretically, I am confused to prove it. Thanks $\endgroup$– AminApr 26, 2020 at 21:21
-
$\begingroup$ The current master variables violate the new optimality cut because there would be no optimality cut if they did not. Let $(\hat{x}, \hat{z})$ be the current master solution, where $z$ is the surrogate for the subproblem objective value, and assume you are minimizing. You solve the subproblem with $x=\hat{x}$ and get optimal subproblem value $z*$. If $\hat{z}\ge z*$, there is no new optimality cut. If $\hat{z} < z*$, the new optimality cut $z\ge f(x)$ is generated so that $f(\hat{x})=z^*$, which means $(\hat{x}, \hat{z})$ violates it. $\endgroup$– prubin ♦Apr 27, 2020 at 22:19