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?


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.

  • $\begingroup$ The sub problem returns a vertex of the dual polyhedron. My question was: Is it possible that the sub problem returns the same vertex twice? If such thing happens then the algorithm stuck at that point because it will not introduce any new cut then. The relaxed master problem will have the same solution as its previous iteration. $\endgroup$ – Rajat Sep 15 '17 at 3:11
  • $\begingroup$ It is possible if you do not generate cuts systematically . For any given solution of the master problem, there is a Benders cut that cuts it off if and only if the subproblem has a solution whose corresponding objective value is worse than that of the master problem. You add a Benders' cut only under this condition, that is, when the Benders cut can cut off the current solution of the master problem. $\endgroup$ – Opt Sep 15 '17 at 6:42
  • $\begingroup$ You can see it in this document which gives a basic introduction to benders decomposition. For a systematic way of generating Benders’ cuts see Fischetti et al. (2010). $\endgroup$ – Opt Sep 15 '17 at 6:50

I could give you a hint about the convergence of the benders decomposition algorithm.

Master vs. Original

In the picture the orange one is the original obj of the LP, and the blue one is the master obj of the bender's decomposed original LP. It shows the changes on master obj through iterations.

It is a large scale linear energy-model, and it tries to minimize the costs. Each iteration, a linear cut is taken from the sub problem and add it to master as a new constraint.

One thing to mention, that after objective value of 2.00 it slows down converging, as you can see between iteration 35-95, master obj is very slowly converging to the original obj value. At iteration 95, master obj is equal to original obj, which stops the algorithm.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.