In the Benders decomposition algorithm we normally use extreme points/rays to generate Benders optimality/feasibility cuts. However, I am not sure what happens if we use any optimal solution to the dual subproblem (not necessarily an extreme point). I guess maybe it has something to do with convergence of the algorithm. For example, if the feasible region is bounded then it may be OK to use any optimal solution. Is that right? What about optimality? Do we need to solve subproblems to optimality? For a minimization problem we still have an upper bound if the subproblems are not solved to optimality [right?], but I'm not sure about validity of the cuts. Maybe it also has something to do with the convergence, maybe not [?]. My other question is about pareto optimal method by Magnanti and Wong. Is the method useful or relevant to a dual problem with multiple solutions or degenerate solutions? I suspect that degeneracy is limited to extreme points but having multiple solutions is a more general definition. asked 31 Jan, 06:30 Opt1989 
I'm fairly confident that Benders optimality cuts derived from nonextreme optimal solutions to the dual problem are valid, as are Benders feasibility cuts derived from nonextreme recession directions of the dual. ( Note that the direction does have to be a recession direction/ray; it just does not need to be an extreme ray.) It's possible that convergence of the master problem is faster in general when using extreme points/rays, but I don't recall ever seeing a formal argument to that effect. The main reason for using extreme points/extreme rays is simply that's what you get when solving an LP subproblem (or its dual) using the primal or dual simplex algorithm. So, it it OK to use any optimal solution or any recession direction (along which the dual objective improves, of course)? Yes. As to the MW question, I don't see why degeneracy of the dual would matter one way or the other. I also don't think it matters whether the dual has multiple optima, but it's been a while since I looked at their paper, so I'm only about 90% confident there. answered 31 Jan, 15:57 Paul Rubin ♦♦ Thanks Paul. Just to make sure I understand your answer to the third question. Do you mean MW method can be useful even when there is exactly one optimal solution for the dual subproblem?
(01 Feb, 03:05)
Opt1989
What I mean is that MW will produce a correct solution even if the dual has only one optimal solution. Is it useful there? No. Remember that MW requires you to identify the optimal solutions to the dual and uses the core point as a tie breaker. If there is only one optimal solution, it will win the tie breaker (trivially), wasting a small amount of time in the process.
(06 Feb, 17:58)
Paul Rubin ♦♦
