8
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 3
    $\begingroup$ 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. $\endgroup$
    – RobPratt
    Sep 18, 2022 at 23:32
  • $\begingroup$ @RobPratt Good point. $\endgroup$
    – prubin ♦
    Sep 19, 2022 at 2:59
  • $\begingroup$ @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? $\endgroup$
    – user123456
    Sep 19, 2022 at 10:40
  • $\begingroup$ 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.$ $\endgroup$
    – prubin ♦
    Sep 19, 2022 at 15:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.