Benders decomposition

Question

I was studying Benders decomposition for MILP. I have the following doubts:

1. Is there any chance that the optimal solution of the subproblem for $k$ and $l$ iterations, that is $u^k$ and $u^l$, are the same? $(k \neq l)$

2. If it is true, then what can we tell about the convergence?

Answer 1

There are different versions of the benders decomposition algorithm. Consider the basic version of the benders decomposition where subproblems are linear programs.

What benders decomposition does is to transmit a solution vector (obtained from the master problem) to the subproblem. In other words, the subproblem is the original problem except that the value of a subset of variables are fixed to some values (which may not be part of an optimal solution). Therefore, the subproblem gives a solution with an objective value which is NOT better than the optimal value of the original problem. This implies that for a minimization problem the subproblems give upper bounds on the optimal value of the original problem. There is no reason for these upper bounds to change strictly because at each iteration we end up with a different subproblem obtained from fixing those variables (they change neither increasingly nor decreasingly). However, if we find the best upper bound found so far and update it at each iteration then these new bounds change decreasingly (for a minimization problem). For the same reason, these new bounds may or may not change strictly. Therefor,

1) Yes, it is possible. Different subproblems may give the same solution or different solutions with the same objective value.

2) Nothing! As I said already, we keep only the best bound and that determines the convergence of the algorithm not the particular objective values of the subproblem.