1
$\begingroup$

I'm implementing a Column Generation algorithm. The pricing problem, in general, find more than one column with negative reduced costs(the master is a min problem). If i add only the most negative reduced cost column per iteration, at the end i have a linear relaxation with $Z = 8240.3$. When i tried adding all the columns found in the pricing problem, in the end i have found a linear relaxation with $Z = 8166.668$.

That doesn't seem possible. Anyone have any clues on why this is happening?

Thanks in advance

|cite|improve this question
$\endgroup$
  • $\begingroup$ Numerical round-off/instability, maybe? Welcome to CS.SE! $\endgroup$ – D.W.♦ Apr 29 '17 at 15:57
  • $\begingroup$ Thank you @D.W. After reading your comment i searched my code and found out that it was indeed a round-off error. In an effort to save memory i was rounding off some dual variables to zero. When i stopped doing that, both pricing approaches lead to the same $Z$. Thank you $\endgroup$ – Victor Hugo Apr 29 '17 at 19:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.