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 30 Aug '17, 14:24

dimrizo's gravatar image

accept rate: 0%

edited 30 Aug '17, 14:52

Just to be clear, you're referring to an unbounded dual problem (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?

(30 Aug '17, 17:07) Paul Rubin ♦♦

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.

(31 Aug '17, 04:33) 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.

Reference: Title = {Accelerating Benders Decomposition: Algorithmic Enhancement and Model Selection Criteria}, Author = {Thomas L. Magnanti and Richard T. Wong}, Journal = {Operations Research}, Year = {1981}, Month = {May-June}, Number = {3}, Pages = {464-484}, Volume = {29},


answered 01 Sep '17, 19:38

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
accept rate: 19%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported



Asked: 30 Aug '17, 14:24

Seen: 846 times

Last updated: 01 Sep '17, 19:38

OR-Exchange! Your site for questions, answers, and announcements about operations research.