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's gravatar image

Opt1989
1056
accept rate: 0%

edited 31 Jan, 07:10


I'm fairly confident that Benders optimality cuts derived from non-extreme optimal solutions to the dual problem are valid, as are Benders feasibility cuts derived from non-extreme 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 M-W 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.

link

answered 31 Jan, 15:57

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.5k412
accept rate: 19%

Thanks Paul. Just to make sure I understand your answer to the third question. Do you mean M-W 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 M-W will produce a correct solution even if the dual has only one optimal solution. Is it useful there? No. Remember that M-W 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 ♦♦
Your answer
toggle preview

Follow this question

By Email:

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

By RSS:

Answers

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

Tags:

×34
×6

Asked: 31 Jan, 06:30

Seen: 223 times

Last updated: 06 Feb, 17:58

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