Benders decomposition has - as far as I know - not been extended to multiple objectives. (Well, there are obvious ways in which to do it, as long as the multiple objectives are treated through any of the standard scalarization techniques that are used, but are you referring to a more advanced one?) If you know of any good reference to such a description, then please share it. After reading them I can perhaps answer your question. :-)

Dear Michael ,

In this paper authors used BDA for their multi-objective NP-hard problem.Firstly ,they transformed their multi-objective model to single one ,and then they decomposed it based on BDA. 

Dear Iman,

As far as I know, Benders Decomposition (BD) is much better and more acceptable than meta-heuristic approaches especially for software development goals.

In power system studies, there are so many NP-hard problems which are only solved using BD and some similar methods because power industry policy makers cannot trust meta-heuristic solutions. We, as Iranian software developers, only implement the algorithms which are based on strong mathematical rules though meta-heuristic approaches are slightly used to improve the efficiency of the software.

In my opinion, forget the meta-heuristic approaches and follow math-based methods!

Regards,

Morteza Shabanzadeh

http://mortezash.blogfa.com/

I second Morteza's opinion - one needs to be sure that the solution is correct, and metaheuristics can never provide such guarantees. While each master problem in the Benders method is NP-hard, there is no need to solve these master problem optimally in order to establish convergence of the overall scheme - it is enough to make sure that enough improvement of the objective function is made in each major iteration. 

Dear Iman

I disagree with Morteza and Michael.

Basically, you need to choose the optimization problem to the problem at hand. Benders algorithm is good in some situations but meta-heuristics are good in other situations.

In my opinion you should always try good solid mathematical methods first, and only when they fail, switch to meta-heuristics. BUT there are many situations where this is exactly the case. A good example is multi-objective problems. The current methods for good, guaranteed optimal solutions to multi-objective problems, i.e. a Pareto Front, are WEAK. In most of these cases the choice is between getting no Pareto Front or using meta-heuristics.

Benders algorithm is a classic optimization algorithm, but it has only had limited success, primarily in Stochastic Programming problems. I have never seen a paper with both multi-objective problems and Benders algorithms, so I will read the referred article with interest.

I agree with most of the above comments.  These days, exact solvers are so good that it is advisable to consider using them first, and only use meta-heuristic methods if exact methods turn out not to be viable for some reason.  And even if you do decide to use a meta-heuristic, it may be helpful to also use mathematical programming to compute a bound, that you can use to assess the quality of your heuristic solution. 

I also want to add that Benders decomposition is designed for problems whose constraint matrix has "block-angular" structure.  That is to say, it works best if, when you remove some variables (columns), the remaining problem decomposes into a number of smaller problems.