Questions Tagged With reduced-costhttp://www.or-exchange.com/tags/reduced-cost/?type=rssquestions tagged <span class="tag">reduced-cost</span>enWed, 04 Oct 2017 15:06:00 -0400Pricing Out a New Variablehttp://www.or-exchange.com/questions/15047/pricing-out-a-new-variable<p>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.</p>
<p>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?</p>
<p>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.</p>
<p>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</p>gtg489pWed, 04 Oct 2017 15:06:00 -0400http://www.or-exchange.com/questions/15047/pricing-out-a-new-variableshadow-pricelinear-programmingoptimizationcolumn-generationreduced-costIs there a general theory of reduced costs?http://www.or-exchange.com/questions/14217/is-there-a-general-theory-of-reduced-costs<p>The concept of <em>reduced cost</em> appears virtually in any work about linear programming. I have a feeling, however, that the concept itself goes well beyond the boundaries of linear optimisation. For instance, there is an obvious similarity between the concept of reduced cost in linear programming and the cost of a <em>move</em> in local search (the simplex algorithm itself is a form or local search, after all). I was wondering where there exists a general theory of reduced costs, that transcends the boundaries of a specific optimisation technique. Maybe this is a trivial subject, but I haven't encountered any work that studies reduced costs under a unifying theory. Can anyone provide pointers to the literature, if available?</p>Tommaso UrliThu, 22 Sep 2016 20:23:58 -0400http://www.or-exchange.com/questions/14217/is-there-a-general-theory-of-reduced-costsreduced-costlinear-programminglocal-searchtheory