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.


1 Answer 1


Assume you want to solve $$ \begin{array}{ll} min & c^T x \\ st & A x = b \\ & x \geq 0 \end{array} $$

For any dual feasible solution $(\hat y,\hat s)$ it holds $$ \hat s = c - A^T \hat y \geq 0. $$ Next assume $c^Tx \leq \hat z$ for all feasible x, then clearly $$ c^T x - \hat y^T \hat A x = c^T x - b^T \hat y \leq \hat z - b^T\hat y $$ holds for all feasible $x$. This implies $$ c^T x - \hat y^T \hat A x = (c - A^T \hat y)^T x = \hat s^T x \leq \hat z - b^T \hat y. $$ Given $x \geq 0$ we conclude $$ \hat s_j^T x_j \leq \hat z - b^T \hat y. $$

This is how I explain how to obtain bounds on primal variables from a dual feasible solution and an upper bound on the objective value.


Your Answer

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

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