8

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?

RobPratt
  • 32,006
  • 1
  • 44
  • 84
user123456
  • 81
  • 4

1 Answers1

8

The reduced cost is the instantaneous rate of change as you increase the value of the new variable from 0. The actual impact of the new variable on the objective function is piecewise linear and concave. So as you increase the new variable from 0, initially our objective improves one unit per unit of the new variable, then beyond some amount less than rate 1, then beyond some further amount at an even lower rate, and eventually the objective begins to get worse if you keep increasing the new variable (unless you first hit a value beyond which the problem becomes infeasible). As you increase the new variable, periodically you will need to pivot (because some other variable hits an upper or lower bound), and with each pivot the rate of change of the objective function changes.

prubin
  • 39,078
  • 3
  • 37
  • 104
  • 3
    It is worth noting that the "some other variable hits an upper or lower bound" situation can happen right away, yielding no decrease at all in the objective value. – RobPratt Sep 18 '22 at 23:32
  • @RobPratt Good point. – prubin Sep 19 '22 at 02:59
  • @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? – user123456 Sep 19 '22 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.$ – prubin Sep 19 '22 at 15:53