# Column generation: decreasing value of restricted master problem

I am using column generation to solve a minimization problem.

At a given iteration, my subproblem finds a column with reduced cost $$-1$$, and in the following restricted master problem, this new column takes value $$13$$, so I would expect the objective function to decrease by $$13$$ units. But is only decreasing by $$12$$. Is there an explanation for this?

• @prubin Thanks for the explanation. When performing the simplex algorithm, I identify the entering variable based on its reduced cost $\hat{c}$, as well as its upper bound $UB$ (potentially $0$). Is it not always the case that the objective function $Z$ becomes $Z+\hat{c} UB$? Is this different when performing column generation? Sep 19, 2022 at 10:40
• You are correct about how a simplex pivot works, and the rule is unchanged when you are using column generation. If you look at the example cited in your question, where the new column took the value 13, I think you will find that this was the result of multiple pivots. The first pivot presumably changed the new variable from 0 to some value $v$ and changed the objective value by $-1\times v,$ where $v < 13.$