# Sign of the reduced cost in LP

I'm new to operation research. I'm confusing about the sign of reduced cost and I have a few questions that I'd like to ask. Suppose that I solve a maximization problem, considering a variable x with positive coefficient, then

1. What is the sign of the reduced cost of this variable if in the solution x > 0 ?
2. If x > 0 in the solution, then is x a basic variable ?
3. How do you interpret the sign of reduced cost in a maximization problem ?

The reduced cost of a nonbasic variable $$x$$ is the net rate of change to the objective if you increase the value of $$x$$ by a small amount and optimally adjust the other variables to preserve feasibility. Regardless of whether you are maximizing or minimizing, a positive reduced cost means increasing $$x$$ will increase the objective value and a negative reduced cost means increasing $$x$$ will decrease the objective value. The reduced cost of a basic variable is always 0.

Assuming that the problem has been solved to optimality, and assuming that the domain of $$x$$ is $$[0, \infty)$$ (typical for most LP formulations), then if $$x>0$$ in the optimal solution it will be a basic variable, and if $$x$$ is basic the reduced cost will be 0.

If $$x$$ has a nonzero lower bound $$\ell > 0$$ that is expressed as a bound on the variable rather than as a constraint (meaning that the constraint matrix does not include $$x\ge \ell$$), and if $$x=\ell$$ in the solution, then it may be nonbasic even though it is positive. The same is true if $$x$$ has a finite upper bound $$u$$ expressed as a bound rather than a constraint and $$x=u$$ in the optimal solution. This is because there are versions of the simplex algorithm that handle a lower bound $$\ell$$ by substituting $$\hat{x}=x - \ell$$ for $$x$$ in the model, and handle an upper bound $$u$$ by substituting $$\hat{x} = u - x$$ for $$x$$ when $$x$$ hits its upper bound.

• Thank you for your answer. Let say if the solution of the LP is optimal, then is it safe to say that the reduced cost of variable $x$ will be negative ? Since increasing $x$ cannot obtain a better solution, while decreasing $x$ will make the objective function smaller Apr 27 at 3:26
• No, that is incorrect on two counts. First, the reduced cost of a basic variable is always 0, so if $x$ is basic its reduced cost cannot be negative. Second, if LP has multiple optima, the reduced cost of a nonbasic variable that is positive in a different optimal solution will be 0.
– prubin
Apr 27 at 16:28
• Yes I agree with if $x$ is basic then its reduced cost is 0. I was talking about a case in which $x$ is non basic but its value is >0 in the optimal solution (because there's an lower bound and upper bound on $x$), then the sign of the reduced cost will always be negative ? Apr 28 at 14:16
• Not necessarily if there are multiple optima.
– prubin
Apr 28 at 19:18
• Could you explain more if it's not the case if there are multiple optima ? My thought is that if the $rcost(x) > 0$, its mean that increase $x$ will increase the objective value, but the objective value is already optimal, so it cant be increase anymore. Apr 29 at 3:10