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 yvars the first time, the algorithm works fine. However, when the yvars 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 yvars 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 yvars. 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 (bBy) part I'm focusing on. This is a reallife 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 foreach constraint foreach constraint with a yvar in it foreach variable var in the model 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 
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.) answered 11 Nov '10, 05:15 Paul Rubin ♦♦ 1
Hi Paul. Ah, I suppose I forgot to touch on how to fix the yvariables. 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 (bBy) 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 yvars 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
