I am using Benders' Decomposition to solve a stochastic MIP.
To improve cut selection, I implemented the Alternative Cut Generation Problem as proposed by Fischetti et al. (2010).
I will summarize the key changes here:
Assuming we have the following dual subproblem objective function for a scenario $s$:
$$ \hat{v}_s = Maximize \; \pi^T (h_s - T_s \bar{x}) $$
In the alternative cut generation, we modify the objective:
$$ \hat{v}_s = Maximize \; \pi^T (h_s - T_s \bar{x}) - \theta_s \pi_0 $$
with $\theta_s$ being the current recourse value projection for scenario $s$ of the master problem.
Also, in the paper it is stated that the right hand side of all constraints of the dual subproblem will be multiplied by $\pi_0$. With this, we basically scale all $\pi$-variables by $\pi_0$.
Additionally, a normalization constraint is added to the constraints that turns this problem into a problem that is always feasible:
$$ \left\lVert \pi \right\rVert_1 + \pi_0 = 1 $$
The following definitions hold:
If $\hat{v}_e > 0$ a cut exists. Otherwise, the master problem solution used as input is optimal.
In the case $\pi_0 > 0$, an extreme point exists, we get an optimality cut.
Otherwise, if $\pi_0 = 0$, an extreme ray of the original dual subproblem exists, we get a feasibility cut.
With these changes, the authors argue we have a more clever selection of cuts while still making the usual progress in the Benders' algorithm.
Now, to my issue:
I have implemented both versions, the standard dual subproblem and the modified one.
The problem is, the decision whether to add an optimality cut or a feasibility cut differs.
That means, in more detail, receiving the same master problem solution as an input, it can happen that the dual subproblem is unbounded, thus detecting a ray and adding a feasibility cut, meanwhile the alternative cut generation problem for the same master problem solution reports an objective value $> 0$ with also $\pi_0 > 0$, thus suggesting to add an optimality cut.
Can anyone explain why this discrepancy happens?
Is it likely an error on my side or can this odd behavior sometimes occur using this method?
