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

kreutz
11729
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

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.

link

answered 31 Aug '10, 14:42

Bo%20Jensen's gravatar image

Bo Jensen ♦
5.0k2919
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 ♦

Maybe a dumb question, but did you remember to transform the initial feasible solution (x,y,z) into the space of the transformed master i.e [Ax,1] ?

Regarding the columns generated over and over again. You can check if the column should be added to the master problem by forming the corresponding column in the restricted master problem i.e [A_i*x_i,1] with cost c_i, then use the duals from the last solve of the restricted master problem say ym to calculate the reduced cost. If negative your fine and can add it, otherwise no improving column was found from that subproblem (which is perfectly valid). This check corresponds exactly to using the objective returned from the subproblem, but gives you a second check to test for errors.

But I think your problem lies in the z-vars, which has an empty subproblem. It is a funny formulation, but if we should pursue the DW idea, then each time you have a z-variable with a negative cost in the empty subproblem, then the subproblem is unbounded (since you can raise the z-var infinitively i.e no constraints in that subproblem, assuming no upper bounds), so you need to generate a column for that ray, note rays from subproblems are handled differently than bounded solutions.

link

answered 11 Aug '10, 13:09

Bo%20Jensen's gravatar image

Bo Jensen ♦
5.0k2919
accept rate: 14%

Hi Bo

I should start by saying that I don't have a subproblem for the z-vars. The z-vars are just left as-is in the master problem (see http://groups.google.com/group/sci.op-research/browse_thread/thread/dd1b3c23854c4a75# where I asked about this).

So when I transform the initial feasible solution I just grab the y-vars from it and use those as coefficients on the constraints as I would with a subproblem solution. The z-vars are ignored, since those are present in the problem already. The objective value cost of using the initial solution is just the cost of the x-vars and y-vars.

(11 Aug '10, 13:23) kreutz

Regarding the column generation. The columns that are generated over and over again all pass the check you speak of. I already had it check the obj function for the correct sign.

(11 Aug '10, 13:24) kreutz

It is perfectly OK to leave the z-vars as is, depending on the structure of A_z you can choose to do so or not. If the checks is satisfied, then you know at least one pivot is needed for the simplex algorithm in the restricted master, do you see any iterations ? But still there is no guarantee that the object will decrease since the pivot can be degenerated. I think you should do a small example by hand, I know it takes time, but is often worth it.

(11 Aug '10, 19:06) Bo Jensen ♦

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 :)

link

answered 01 Sep '10, 15:17

kreutz's gravatar image

kreutz
11729
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 ♦

If you in any ways have some information on the outcome you can share, I would be interested. What was your experience by using DW on a large LP, did you get any speed up ? How large is "large" ?

link

answered 12 Sep '10, 06:44

Bo%20Jensen's gravatar image

Bo Jensen ♦
5.0k2919
accept rate: 14%

1

Hi Bo

I'm currently waiting for my department to upgrade to C# 4.0 (aka visual studio 2010). Right now I'm the only one running it, because I wanted to take advantage of its easy parallel computing library. I can't throw 4.0 software on the main calculation pc (6 core cpu x 2, 48 gb ram) until we've upgraded the rest of our tools. On my own pc for a reasonably sized problem I'm not faster, but it looks like that might just be because I'm only running on a single dual core cpu.

I also have high hopes that a stabilization algorithm will cut some iterations off.

(13 Sep '10, 18:24) kreutz
1

Regarding size I'm not completely sure. I'll give you a ballpark figure soon. The reason is that we've implemented some reduction methods to cut down on the amount of timesteps so the model would fit into memory, but I'm not the one who wrote those methods, and I haven't had the chance to look at them carefully yet. A goal of ours is to get rid of these reduction methods eventually.

(13 Sep '10, 18:27) kreutz

OK if 48GB is not enough, then we can call it a large scale LP... Based on the limited information I have, I think I would have attacked it differently, DW has a bad reputation of tailing. I would cut down size by writing either columns or constraints to disc, then periodic look at them to see if they should be added. You would end up in some kind of partial pricing scheme for the simplex algorithm. If dual simplex was faster than primal, then I would do something similar to <link-below>. If you store them in a binary format, reading from disc is less painful.

(13 Sep '10, 19:24) Bo Jensen ♦

http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V8M-48MPTKX-DV&_user=10&_coverDate=05%2F31%2F1993&_rdoc=1&_fmt=high&_orig=search&_origin=search&_sort=d&_docanchor=&view=c&_searchStrId=1459691397&_rerunOrigin=google&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=0fd4805c1956a4d6ee83343fa461c787&searchtype=a

(13 Sep '10, 19:25) Bo Jensen ♦

Anyways +1 for providing information on the outcome :-)

(13 Sep '10, 19:27) Bo Jensen ♦

Can you say something about run times ?

(13 Sep '10, 19:29) Bo Jensen ♦
showing 5 of 6 show 1 more comments

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.

link

answered 12 Aug '10, 15:22

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

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.

link

answered 31 Aug '10, 14:01

kreutz's gravatar image

kreutz
11729
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 ♦♦
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
×127

Asked: 11 Aug '10, 12:24

Seen: 6,203 times

Last updated: 12 Sep '10, 06:44

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