Consider the binary program
$$ \min_{ x \in \{0,1\}^N } \left\{ c^T x \mid Ax \leq b \right\}$$
where $A$ and $b$ are real matrices with appropriate dimensions. I am interested in solving large binary MIP problems of this type. In many cases, a large number of my variables $x$ are zero. According to this answer by Rolf van Lieshout, one could do this using reduced cost fixing. However, I've tried looking further into the topic but resources are quite limited, as others also have noted.
From what I understand, reduced cost fixing works by considering the reduced cost vector $d=c-A^T y^\star$, where $y^\star$ is the optimal dual solution. Then, given some lower bound $z_{LB}$ and upper bound $z_{UB}$, we can fix the nonbasic variable $x_j$ to $0$ if $d_j \geq z_{UB} - z_{LB}$, or fix $x_j$ to one when $- d_j \geq z_{UB}-z_{LB}$.
Alternatively, one can also write $d_j = c_j - c_{\mathcal{B}}^T B^{-1} a_j$, where $c_{\mathcal{B}}$ is the cost coefficient vector of the basic variables, $B^{-1}$ is the basis inverse and $a_j$ is the j'th column of $A$.
I have a question regarding this topic:
Is there a mathematical derivation which proofs that the entries of the reduced cost vector indeed show that the objective would have to increase by the given amount before they could enter the basis in the simplex algorithm? All sources I could find unfortunately simply claim this fact, but neglect to show it. I would really like to understand and proof why we can claim that the objective has to change by the given value before the variable can enter the basis again. I've tried proving it, but could not manage.
