I'm struggling a bit with my understanding of reduced cost in linear programs. I know how they are calculated and understand why and know that they tell us how much the objective function improves when we increase the value of the corresponding variable. Other than that my understanding is pretty limited. I would also be grateful for any good literature recommendations on the topic. I have two related questions/problems:
Consider a linear program \begin{align} z^* = \min & \sum\limits_{j \in J} c_j x_j \\ \text{s.t.} & \sum\limits_{j \in J} a_j x_j &= b \\ & x_j &\geq 0&, \ j\in J. \end{align} Now let $x^\prime$ be a feasible solution with objective value $z = \sum_{j\in J} c_j x^\prime_j $ and $\bar{c}^*= \min\{\bar{c}_j \mid j \in J \} $ the minimal reduced cost. In their Column Generation Primer (Section 2.1) Desrosiers and Lübbecke state that, if we have a bound of the form $\sum_{j \in J} x_j \leq k$ we get a lower bound for the objective value of an optimal solution $$ z^* \geq z + k \bar{c}^* $$ since we can not decrease the objective value $z$ by more than $k$ times the minimal reduced cost. While this seems to be intuitive I do not know how to proof this. Are the (minimal) reduced cost monotonically increasing? I.e. if $x_{j_1}$ is the variable with the minimal reduced cost $\bar{c}^*$ and $x_{j_1}$ enters the basis and we increase its value to one and calculate the minimal reduced cost $\bar{c}^*_{new}$ for this new solution. Does $\bar{c}^*_{new} \geq \bar{c}^*$ hold? If not, how does one proof the above inequality? (Stated differently, can it happen that the reduced cost for a variable has low (near zero) reduced cost and only after another variable enters the basis the reduced cost of that variable assume a big negative value? Or do the reduced cost identify the potential of a variable to decrease the objective value regardless of the value of other variables?)
We have the same linear program plus an upper bound on the variables. \begin{align} z^* = \min & \sum\limits_{j \in J} c_j x_j \\ \text{s.t.} & \sum\limits_{j \in J} a_j x_j &= b \\ 0 \leq & x_j \leq 1&, \ j\in J. \end{align} As above let $x^\prime$ be a feasible solution with objective value $z = \sum_{j\in J} c_j x^\prime_j $. Again we have an upper bound $\sum_{j \in J} x_j \leq k$ where $k$ is an integer. If $x^\prime_1,\ldots, x^\prime_k$ are distinct variables and with reduced cost $\bar{c}_1, \bar{c}_2, \ldots , \bar{c}_k$ that are lower than all other reduced cost does a lower bound of the form $$ z^* \geq z + \sum\limits_{i=1}^k \bar{c}_i $$ hold?
Thank you very much in advance for all answers.
