1
$\begingroup$

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 ?

Thank you for your time

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
8
  • $\begingroup$ 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 $\endgroup$
    – Nguyen Quang Anh
    Apr 27 at 3:26
  • $\begingroup$ 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. $\endgroup$
    – prubin ♦
    Apr 27 at 16:28
  • $\begingroup$ 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 ? $\endgroup$
    – Nguyen Quang Anh
    Apr 28 at 14:16
  • $\begingroup$ Not necessarily if there are multiple optima. $\endgroup$
    – prubin ♦
    Apr 28 at 19:18
  • $\begingroup$ 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. $\endgroup$
    – Nguyen Quang Anh
    Apr 29 at 3:10

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.