# Dantzig Wolfe Dual Prices

 1 1 Hi everyone. Another DW question... First of all, you can see the structure of my problem here: http://www.kreutz.us/images/structure.png (Note: I know Benders decomp would probably be more suitable for this, but this is for a school project, so I'm starting with DW) I'm solving the subproblems composed of the x vars and y vars (5 pictured in the graph) and the master problem is composed of the y vars and the z vars. I've made a method that generates a feasible solution to the whole problem(x,y and z vars) and I've verified the solution it provides. Now when I start DW by solving the master problem for the duals, I get some prices that are sky high or 0. This in turn causes the subproblems to return solutions where the y vars are maxed out in either the lower or upper bound. These solutions end up not getting used by the master problem, since the constraints in the master problem end up looking something like this, where sol1 and sol2 are the solutions I've generated to just reach feasibility: z_1 - z_2 + 76 sol1 - 150 sol2 + 100000 sol6 - 100000 sol7 = 0 If I let it run for ~ 20 iterations with 4 subproblems, I start to see a move from the initial solution, but some of the subproblems keep generating the same column over and over again, never moving forward. The move I see is that the solver takes one of the solutions where all y vars have been generated to 0 and uses a lot of that. Then it uses a little bit of one of the "bad" solutions. Once in a while, a column with "sensible" numbers will also be generated. When that happens, the dual prices that are passed to it are also "sensible". I'm using sensible here as in numbers that are somewhat on the same scale as the coefficients in the constraints that they appear in. It's clear that something is wrong, but I'm at a loss as to what it can be. I've checked that I'm using the right obj function for the subproblems. I've checked that the dual prices are transferred correctly from master to subproblems etc. So, any ideas as to what's messing it up? My gut feeling is that is has something to do with the dual prices that are generated by the master problem. I'm not sure how much of this is relevant, and I'm hoping I just made some easily fixable newbie error along the way. Feel free to ask further questions about my program, and I'll see if I can answer them. asked 11 Aug '10, 12:24 kreutz 117●2●9 accept rate: 0% If you meant "the master problem is composed of the y vars and the z vars" literally, that's an issue. The master problem should have the z variables and new variables representing the weights being assigned to each subproblem solution. (11 Aug '10, 15:48) Paul Rubin ♦♦ Hi Paul Oops. It's actually the z vars and vars representing the added columns. (11 Aug '10, 18:06) kreutz

 1 You don't show the progress in the restricted master problem, which is also important. Do your optimizer take any iterations ? Do you check solution status from the optimizer i.e is it always optimal ? No infeasible or unbounded sub or restricted master problems ? Why not start with two subproblems and make that work first. answered 31 Aug '10, 14:42 Bo Jensen ♦ 5.0k●2●9●19 accept rate: 14% Okay, I think we're nearing the limits of my cplex/LP knowledge here. I did a run with 2 subproblems, all problems (master or sub) are solved to optimality each time, according to my logs. But the cplex log shows this: http://pastebin.com/sjirFr2d So after it finds the last column it includes, it just stays on "reinitializing dual norms..". I'm not sure what that means. (31 Aug '10, 22:00) kreutz Oh I forgot to say that I set a hard limit of 100 iterations for this run, so that's one "reinitializing dual norms" for each itr after the 17th (31 Aug '10, 22:01) kreutz The cplex messsage about dual norms is irrelevant here, it is related to dual priciing. But no iterations were performed in the last rounds, so something is fishy in your checks. I would take the solution you know is optimal and split it up in subproblems, calculate the objective for each sub and add the columns. This will give you a contradiction. (01 Sep '10, 03:42) Bo Jensen ♦ If you are working on simple example data, you could write the two subproblems, the restricted master and the original problem to an LP file and put it up somewhere. Then I will have a quick look. (01 Sep '10, 14:05) Bo Jensen ♦
 1 Woop, it's working!! The problem was, of course, with the dual prices. I just couldn't figure out why the last year would be working while the others weren't. It lied in a constraint formulated as: x_year = x_(year-1) + ... <=> x_year - x_(year-1) + ... = 0 I had forgotten that when I use the dual price in relation to the x_(i-1) variable it needs to be multiplied with -1. I had somehow assumed that all of the coefficients were 1 and implemented that. The reason it would be working for the last year is that it is never used as a "previous year", so to speak. Correcting it took 5 lines of code and 3 minutes of work, not to mention the 2-4 weeks looking for the damn bug! Now to see if I actually get a performance increase... Thanks for all of the help! I'll be back when I start implementing benders decomp :) answered 01 Sep '10, 15:17 kreutz 117●2●9 accept rate: 0% Glad you found it. This is implementation OR in a nutshell, I spend long time on small bugs everyday, with time you get this time reduced though. I am sad to say I don't think you will see speed up, general lp solvers are quite good. (01 Sep '10, 15:34) Bo Jensen ♦
 0 This in turn causes the subproblems to return solutions where the y vars are maxed out in either the lower or upper bound. These solutions end up not getting used by the master problem ... As Bo pointed out, degeneracy in the master problem can cause the objective value to hold constant after you insert a new master column arising from one of the subproblems; but a subproblem solution is chosen specifically because the reduced cost of its weight variable in the master problem is (strictly) favorable (e.g., negative in a minimization problem), and so the simplex method applied to the master problem must pivot it into the basis (unless you add multiple new columns in one gulp, in which case simplex must enter at least one but not necessarily all into the basis). If the master solution is degenerate, it's possible the new column gets pivoted in and then out again, leading to a different basis for the current master solution. It cannot cycle back to the same basis, since that would return the reduced cost of the new column to a favorable value. ... some of the subproblems keep generating the same column over and over again ... When this occurs, are you getting a subproblem objective value (master problem reduced cost) of zero, so that you are not tempted to add the rediscovered subproblem solution to the master problem again? It's entirely possible that a subproblem may not find a favorable new solution (in fact, D-W converges when none of the subproblems cough up a new solution). If you're rediscovering old subproblem solutions with what look like favorable master reduced costs, though, then something is borked. Numerical precision may be an issue. answered 12 Aug '10, 15:22 Paul Rubin ♦♦ 14.6k●4●12 accept rate: 19%
 0 Hello again I had to take a few weeks' hiatus from the problem, but now I'm back to banging my head against the wall :) I've found my algorithm to be working when I have just a single subproblem. It runs for some iterations and converges just fine, producing the same result as solving the whole problem at once. Problems only arise when I start using multiple subproblems. So I tried saving the values of the objective functions in the subproblems over the iterations. The dual prices have been subtracted in these obj functions, so they should be included in the solution if the value is < 0. In practice I have set it to < -0.01, since I sometimes got some numbers very close to zero. You can view the data here: http://pastebin.com/iRhTJPgU From iteration [16] and beyond, the same values just repeat across all 4 problems. Does this tell you anything? I'm hoping this exposes some glaring error I've made, but I'm still lost as to what it can be. answered 31 Aug '10, 14:01 kreutz 117●2●9 accept rate: 0% First off, please knock off the head banging. It's keeping me awake. Second, it's theoretically possible for the same subproblem objective value to recur (with a different solution each time), but it's a bit unlikely. Best guess, with nothing but the subproblem objective values to work from, is that you're not passing the master problem dual variables down to the subproblem correctly. But no guarantee that's the actual problem. Third, when I see objective values that large, I get a bit nervous about numerical stability. Check the kappa values for your master and subproblems. (31 Aug '10, 14:44) Paul Rubin ♦♦ I did a quick check for the master problem using 2 subproblems (same example I gave Bo data from in his answer above). Here they are: One number for each iteration Condition number: 6,75812769970185 Condition number: 6650,93775221134 Condition number: 5839,19578293879 Condition number: 6434,48995305621 Condition number: 8804,97785170453 Condition number: 12708,126467698 Condition number: 12292,3145426991 Condition number: 52428,236987769 Condition number: 142738,875744894 Condition number: 159766,017863404 and then the same number repeats for the rest of the iterations. (31 Aug '10, 22:23) kreutz These look good, which is fortunate (separate from the fact that it was not the source of your problem). Looks like numerical instability won't be a problem. (01 Sep '10, 22:44) Paul Rubin ♦♦
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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: