1
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ 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. It might help to edit your question to describe your full original problem and how are you decomposing into master and subproblem. $\endgroup$
    – RobPratt
    Jun 3, 2022 at 15:06
  • $\begingroup$ If the master objective value doesn't change, why the solution is guaranteed to differ from the previous one? $\endgroup$
    – htam_ujn
    Jun 3, 2022 at 15:10
  • $\begingroup$ 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$. $\endgroup$
    – RobPratt
    Jun 3, 2022 at 15:19
  • $\begingroup$ I like your explanation. Can you post an answer so I can accept? I think I know more about benders decomposition from your comment. $\endgroup$
    – htam_ujn
    Jun 3, 2022 at 15:28

2 Answers 2

3
$\begingroup$

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$.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks, I really like the explanation. Unboundedness is different from other situations. I would appreciate it if you append the content to your answer in the linked problem, which is more relevant. It may help more people like me. $\endgroup$
    – htam_ujn
    Jun 3, 2022 at 19:46
  • $\begingroup$ I updated my answer to point here (along with a synopsis of what I wrote here). $\endgroup$
    – prubin
    Jun 3, 2022 at 23:06

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.