3
1

Hi everyone

I have a minimization LP that I'm trying to solve using Bender's decomposition. The structure is like this http://www.kreutz.us/images/structure.png where the master solves y and z vars and then passes the y vars to the subproblems.

Here's the situation: When a problem is solved in the first iteration, i.e. the master problem generates the optimal y-vars the first time, the algorithm works fine.

However, when the y-vars need to go through more than one iteration, they stay the same. The reason being that the cut generated by the subproblems is of the form: master_obj >= constant. No y-vars in the cut, like you would expect. This constant even turns out to be the correct constant such that the lower bound and upper bound become equal the second time the master problem is solved. So the algorithm terminates, but with a much too high objective function because of the wrong values of the y-vars.

The cut I'm trying to generate can be seen on slide 10 here: http://www2.imm.dtu.dk/courses/02717/benders/benders.pdf where this is the u_i (b-By) part I'm focusing on. This is a real-life problem, so I don't have the data as matrices, but as a model set up in cplex. Therefore I need to do this iteratively. My approach is as follows (I hope this isn't getting too verbose, but it's the only way I can convey what's happening):

`define VarAddition as a hashmap Variable => Coefficient in cut
define ConstAddition as the constant part of the cut

foreach constraint
ConstAddition += RightHandSide of constraint * dual of constraint
end foreach

foreach constraint with a y-var in it
foreach y-var y in the constraint
VarAddition[y] += - (y's coef in the constraint * dual of constraint)
end foreach
end foreach

foreach variable var in the model
redCost = reducedCost of the variable
if (redCost > 0) then ConstAddition += redCost * var.LB
if (redCost < 0) then ConstAddition += redCost * var.UB
if (var is a y-var) then VarAddition[var] += -redCost
end foreach `

So what happens here is that I get some numbers inside VarAddition in the first two blocks of code, but then the reduced cost * bound turns out to be exactly the same and the coefficient becomes 0, thus not including any vars in the cut. I'm guessing it's some LP theoretic thing that I've missed, since they are equal (and given the opportunity I will blame it all on it being past midnight here :). Anyone got any bright/obvious ideas? Thanks in advance. I'll answer any followup questions asap.

asked 10 Nov '10, 23:44

kreutz's gravatar image

kreutz
11729
accept rate: 0%


When you say "dual of constraint" are you referring to the dual of a subproblem constraint? When you say "y's coef in the constraint", do you mean the coefficient of y in one of the subproblem constraints (and, if so, is this before or after moving y to the right hand side and changing the sign of it's constraint)?

Last and perhaps most important, why are you subtracting the reduced cost of a y variable in the penultimate line? (I assume this is the reduced cost from the master problem, since y is not a variable in the subproblem.)

link

answered 11 Nov '10, 05:15

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

1

Hi Paul. Ah, I suppose I forgot to touch on how to fix the y-variables. My colleague and I agreed that it should be enough to just fix them in the subproblem model, i.e. fix them by setting the lower and upper bound to be equal. Is this the wrong approach?

Regardless, yes, "dual of constraint" refers to a subproblem constraint. Yes, y's coef is in the subproblem and this is just the plain constraint, but since we need u_i (b-By) that's why I add -1(coefdual).

(11 Nov '10, 09:04) kreutz

I should also have been more clear about the code block. The code refers only to the subproblem. The y-vars are included in the subproblem, although fixed via their bounds.

The reason for the whole last code block is because we have bounds on our variables. Most literature just assumes that we have a lower bound of 0 and no upper bound, so it isn't included. My reasoning was that these bounds could just be viewed as some additional constraints where all variables have coefficient 1. So it's not the redcued cost from the master, but from the subproblem var which is fixed.

(11 Nov '10, 09:04) kreutz

what is the density of the classical benders cut that you produce?

link

answered 30 Nov '11, 14:48

Georgios's gravatar image

Georgios
111
accept rate: 0%

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:

×231

Asked: 10 Nov '10, 23:44

Seen: 1,887 times

Last updated: 30 Nov '11, 14:48

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