I am using accelerated bender decomposition algorithm which lower and upper bound reach convergence before second iteration ,is it normal such as case?
,as I have attached file,it is shown after iteration 1 lower and upper bound convergence,what happened ?,in fact when I use classic bender decomposition in iter num 2 lb and ub are convergence even with large size,I try to increase size of my problem however classic BDA is convergence in second iter so in this case is it worth to use accelerated BDA?
Hi Iman, I am not an expert in that topic but if Bender decomposition method converges so quickly this means that your problem is perhaps separable. Could you please formulate your problem ?
so,what can we interpret in this case if problem seperable?because as far as I know bender dcomposition is suitable for mixed integer programming to seperate original problem into master problem including integer variable and subproblem including linear problem.
so in this case is it sense of good or bad?
Hi, for me separable means that in your original problem independent groups of variables exist and that the problem is equivalent to n independent problems of lower size.
Dear Iman,
Benders decomposition may indeed converge in just two iterations,
but this would have been a lot of good luck.
BD constructs a polyhedral (piecewise linear) approximation
of the objective function. However, if this objective function
itself is piecewise linear and if it happens to be defined
by exactly two linear hyperplanes, then BD would converge
in just two iterations.
Even if the piecewise linear representation has more than two
hyperplanes, it might be the case that you were just lucky and
generated the two important hyperplanes from the very start.
Several problems solved by various decomposition techniques
including Benders decomposition are discussed in the papers:
http://www.maths.ed.ac.uk/~gondzio/reports/pdcgm2011.html
http://www.maths.ed.ac.uk/~gondzio/reports/ipdcgm.html
http://www.maths.ed.ac.uk/~gondzio/reports/pdcgmDemo.html
which describe the Primal Dual Column Generation Method (PDCGM):
http://www.maths.ed.ac.uk/~gondzio/software/pdcgm.html
With best regards,
Jacek Gondzio
I think something is wrong when upper bound becomes smaller than lower bound - as it can be seen in the attached figure.
Dear Marek,
this is accelerated benders decomposition,actually in classic form in iteration two ,both LB and UB convergence together in second iteration,but when I use Pareto cut to strength ,this would happen.
- Badges
- Science topic
- Similar topics
- Mathematics
- Applied Mathematics