I am doing column gen on a min problem. I solve a relaxation of my problem using a subset of vars and calculate shadow prices for the constraints. Then I compute the reduced cost of new candidate variables using: objective coefficient of the new var minus the sumproduct of the shadow prices and the constraint coefficients.

I solved one time and used the results to price 3 new variables. 1st variable priced out at -1.69. 2nd var priced out at -0.12. 3rd var priced out at 100.38. This is a min problem, so I know negative is good, positive is bad here, so the 3rd var is clearly not a good add to the problem. But how do I interpret the two negative ones? Since both are negative, do I know with certainty that adding both will result in both being used in the basis? Or is it only the variable with the most negative value that is certain to enter the basis?

For testing: I added the 2nd var(-0.12) and NOT the 1st var (-1.69) and solved again and the 2nd var I just added was not even used in the solution. If I add the 1st var(-1.69), it gets used in the solution and the reduced cost of 2nd var changed to positive number.

My main question is: is my calculation for pricing new vars wrong? (I don't think it's wrong because when I price vars in the basis, they price out at 0 - so atleast that checks out) Should all candidate vars with negative reduced cost enter the basis? Or is it only the most negative one with certainty? And the others with some likelyhood, perhaps after future iterations of solves with the new vars? Thanks, Nathan

This question is marked "community wiki".

asked 04 Oct '17, 15:06

gtg489p's gravatar image

gtg489p
3314
accept rate: 0%


In no particular order ...

Is your calculation of reduced cost wrong? Maybe, maybe not. On the surface, it is correct. The one qualification is that if you enter upper bounds on variables as bounds, rather than explicit constraints, then you need to be sure to include the shadow prices of the bounds (which are zero for variables not at their bounds, and either the reduced costs or the negatives of the reduced costs for variables at their bounds (depending on which bound they're at, whether you're in the northern or southern hemisphere, etc.). EDIT: Sorry for the confusion. This applies to existing variables, not to new ones being generated in the subproblem(s).

Does a new variable's failure to enter the basis mean something was wrong with the reduced cost calculation? Not necessarily. If the current restricted master solution is degenerate, the dual has multiple solutions, and you may have just gotten unlucky which one you got. Put another way, it may be that the new variable looks good to the current basis, but the first pivot changes the dual solution (hence the reduced cost of the new variable) without actually moving to a different corner, and immediately the new variable looks unattractive.

Would adding both variables guarantee both would be helpful? No. Assuming either one entered the basis (see previous point), it could alter the dual solution to make the reduced cost of the other variable change sign.

Is the one with the more negative reduced cost guaranteed to be the best choice? No ... but it's probably the best bet, given what you know.

link

answered 04 Oct '17, 16:48

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

edited 04 Oct '17, 17:22

Thanks Paul, on your first point: I entered the bounds as explicit constraints - but for this kind of constraint, each variable gets its own row, and you don't get that row to calculate shadow price until you put the variable in the problem. The lower bound constraint for a variable that isn't in the problem would just be a row of 0's >= 0. So, how would you calculate the shadow price for those? Thanks, Nathan

(04 Oct '17, 17:08) gtg489p

Assuming that 0 is in the domain of the new variable (which is typically the case), you usually don't have to worry about the shadow prices for the bounds. They'll be zero for the current master basis, hence won't affect the reduced cost computation. In theory, something goofy could happen if your subproblem generated a variable with an upper bound of zero and a negative reduced cost, but I've never heard of a model where that could happen (just by the nature of a "normal" subproblem). I edited my previous answer to clarify (?) this.

(04 Oct '17, 17:28) Paul Rubin ♦♦

THanks Paul - very helpful. I think what I am going to do now, since nothing looks glaringly wrong, is to run this with real example data for which I already know the optimal solution and see if the column generation method arrives at it. If anyone else can think of a way to check the correctness of my new-variable pricing method, I would greatly appreciate any tips. Thanks, Nathan

(04 Oct '17, 17:41) gtg489p
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
×190
×18
×2
×2

Asked: 04 Oct '17, 15:06

Seen: 319 times

Last updated: 06 Oct '17, 14:43

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