Unbounded master problem in Benders decomposition

Question

After a few iterations, my master problem with optimality cuts is still unbounded. I wonder if it's possible in theory?

If it's possible, how to deal with the unbounded master problem?

Answer 1

Assuming your master problem is to minimize $\eta$, a simple way to avoid unboundedness, even before adding any cuts, is to impose a redundant lower bound $\eta \ge L$ for some constant $L$. Often, taking $L=0$ is valid.

Answer 2

Yes, it is possible in theory.

An alternative to bounding the objective function is bounding the variables. If this is a "real-world" model (where the variables represent actual decisions), they will all be bounded in practice. Adding appropriate (not overly tight, but not ridiculously loose) bounds will sometimes speed up the solution process in addition to keeping the model bounded.

Update: I added an answer to the linked question that is relevant here (and too lengthy to repeat). Basically, if the solver for the master problem is at a corner where it discovers a recession direction that makes the master unbounded, and if the subproblem generates an optimality cut (to correct the master problem under-/over-estimating the objective value at that corner), there is no guarantee that the cut causes the objective to become bounded in the recession direction. If it does not, the solver will return the same corner solution (with an amended objective value), the master will remain unbounded, and the solution process will remain stuck.

Answer 3

RobPratt's and prubin's answer indeed solves the problem in the post.

If someone wonders whether there exist other solutions, I found a class of stabilization methods in Frangioni, A. (2020) for nonlinear nonsmooth problems to avoid oscillation called proximal and level stabilization also solving this problem to some level.

proximal stabilization: adding a proximal term to the objective of the master problem, then the MP changes from $$ \min_{x \in X} f(x) $$ to $$ \min_{x \in X} f(x) + \frac{\mu}{2}|| x - x_k ||_2^2 $$ where $\mu$ is a hyperparameter.

level stabilization: adding a level set constraint, then the MP becomes $$ \min_{x \in X} || x - x_k ||_2^2 \\ \text{s.t. } f(x) \le l $$ where $l$ is a hyperparameter. You can choose $l$ as the best primal bound you have achieved.

Of course, you can combine the above 2 methods $$ \min_{x \in X} f(x) + \frac{\mu}{2}|| x - x_k ||_2^2\\ \text{s.t. } f(x) \le l $$

Reference

1. Frangioni, A. (2020). Standard bundle methods: untrusted models and duality. In Numerical Nonsmooth Optimization (pp. 61-116). Springer, Cham.