I am trying to implement a Benders decomposition approach using the C++ Concert API. I do not want to rely on the getDual, getDuals, getRay or dualFarkas methods because I found that they are too dependent on the black box solver. I don't get the convergence ratio that I would like to see in my method. I am trying to improve that fact by calculating/ computing/ finding the actual extreme ray of the dual. So I was wondering if any one of you have come accross this problem again and have come up with any methods to find an extreme ray. The most obvious is solving a LP, but does anyone have any idea how the LP should look like in a generic case?
asked
dimrizo |

As far as I know (and this is supported by comments a friend of mine, an optimization software developer, made a while back), both dualFarkas and getRay should return extreme rays if the problem is solved using primal simplex or dual simplex. If you are using the interior point solver, then I'm not sure. There can of course be more than one extreme direction for the dual, and I think it's largely a matter of luck which one you end up with. Assuming you are using primal or dual simplex, you can tip the solver toward one extreme ray versus another by tweaking the dual objective function a little (but not too much, lest you get an objective function for which the dual is bounded). The issue is, how would you know in which direction to tip it? I've sometimes wondered whether the Magnanti-Wong method can be applied to infeasible subproblems in a Benders decomposition. It requires a feasible subproblem; one possibility would be to add artificial variables, switch the subproblem objective function to minimizing their sum, and generate a "solution" that way. This is pure speculation on my part; I've never tried to implement it.
answered
Paul Rubin ♦♦ |

Just to be clear, you're referring to an unbounded

dualproblem (infeasible primal LP)? Also, I don't understand what you mean by "the actual extreme ray". Are you saying that you think getRay and dualFarkas are returning rays that are not extreme?Thanks for commenting. Yes, I am reffering to the unbounded dual problem which I formulated as a problem in CPLEX. And I want to get out of it an extreme ray. Using getRay on this unbounded dual problem will give me cuts that won't "help" the method converge fast enough. I was wondering if there any other ways to get extreme rays, that maybe will lead to better cuts. P.S. If I use dualFarkas on the infeasible primal LP the method converges way faster that if I use getRay on the dual. So I guess that getRay is doing what I think it is doing.