Adding cuts doesn't change the solution of master problem in Benders decomposition

Question

From the problem Unbounded master problem in Benders decomposition, it can happen that after adding cuts the master problem is still unbounded. The answers in the post suggest adding bound for the objective or variables to solve the unboundedness.

I found that the reason why unboundedness makes benders fail is that sometimes the solver returns the same solution before and after adding cuts since the master problem with cuts is still unbounded. I think it can also happen when adding bounds to the objective or variables since there's no assurance that the lower bound will be better with more cuts, which means more cuts don't guarantee a different solution to the master problem.

I know there're some techniques like restarting to jump from incumbent to new solutions, but these techniques seem to have no guarantee.

Answer 1

You can certainly get the same master objective value after adding optimality cuts, but you should not get the same solution in consecutive master solver calls until the final iteration, when the lower bound and upper bound are the same. Suppose the master solver claims objective value $\eta_1$, but the subproblem says the true objective value is $\eta_2 > \eta_1$ and generates an optimality cut that conveys that information. If the cut is generated correctly and the master solver returns the same solution, the master objective value will now be $\eta_2$.

Answer 2

Suppose that the master problem entails maximizing a variable $z$, and let $x$ be the master problem variables. Somewhere along the line, the solver arrives at a solution $(\bar{x}, \bar{z})$ which is feasible (so far) and discovers that the master problem is unbounded. This means it has found a direction $u$ such that $x + \lambda u$ is feasible for all $\lambda > 0$ and $z\rightarrow \infty$ as $\lambda \rightarrow \infty.$

The master solution $(\bar{x}, \bar{z})$ is passed to the subproblem, which generates a Benders optimality cut $z \le a^\prime x + b$ violated by the current solution (meaning $\bar{z} > a^\prime \bar{x} + b$). Note that the recession direction $u$ was not passed to the subproblem. Let $\hat{z} = a^\prime \bar{x} + b.$ $(\bar{x}, \hat{z})$ is a feasible master solution (at least until some cut renders it infeasible), and $u$ is still a recession direction for $x$. So if $a^\prime u > 0,$ the master problem is still unbounded and the values of the $x$ variables are still unchanged ($\bar{x}$). While it is possible that $a^\prime u \le 0,$ we have no reason to expect that, particularly since the subproblem was unaware of $u.$

So unless we get lucky and the subproblem generates an optimality cut that is limits $z$ in the recession direction $u,$ the only workaround for the unbounded master is to explicitly bound either $z$, $x$ or all of the above.