Reduced Costs and the Optimality Test

The reduced cost of a nonbasic variable is the net change in the objective per unit increase of that variable, once the basic variables adjust to keep the constraints satisfied. For a minimization program in standard form, a basic feasible solution is optimal when every reduced cost is nonnegative, because no available direction improves the objective.

Definition

For a basis $B$ with basic cost vector $c_{B}$ , the reduced cost of variable $j$ is the scalar ${\bar{c}}_{j} = c_{j} - c_{B}^{T} A_{B}^{- 1} A_{j}$ . Equivalently, with the dual vector $y$ defined by $y^{T} = c_{B}^{T} A_{B}^{- 1}$ , the reduced cost is ${\bar{c}}_{j} = c_{j} - y^{T} A_{j}$ .

Formal statement

${\bar{c}}^{T} = c^{T} - c_{B}^{T} A_{B}^{- 1} A$ . For a minimization program in standard form, if ${\bar{c}}_{j} \geq 0$ for every $j$ , the current basic feasible solution is optimal.

Assumptions and scope

The test as stated applies to minimization. For a maximization objective either convert to minimization first, or reverse the sign condition, but do not apply the minimization rule unchanged.
Reduced costs are defined relative to a specific basis. The same variable has different reduced costs under different bases, so a reduced cost is never a property of the variable alone.
Every basic variable has reduced cost zero by construction, since ${\bar{c}}_{B}^{T} = c_{B}^{T} - c_{B}^{T} A_{B}^{- 1} A_{B} = 0$ . Only nonbasic variables carry information for the test.
Nonnegative reduced costs are sufficient for optimality. The converse can fail at a degenerate basic feasible solution, where an optimal point may admit a basis showing a negative reduced cost that nonetheless permits no improving step.

Worked material

Contrast

The cost coefficient is not the reduced cost

Reading $c_{j}$ in place of ${\bar{c}}_{j}$ is the most common way this test goes wrong, and it produces confident wrong answers in both directions.

Take

min 1 x_{1} + 4 x_{2} subject to x_{1} + x_{2} + x_{3} = 3, x_{1} + x_{4} = 1, x \geq 0,

with $c = (1, 4, 0, 0)^{T}$ , and consider the basis $B = {2, 1}$ in that order.

Then

A_{B} = (\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix}), c_{B} = (\begin{matrix} 4 \\ 1 \end{matrix}), A_{B}^{- 1} = (\begin{matrix} 1 & - 1 \\ 0 & 1 \end{matrix}) .

The dual vector is

y^{T} = c_{B}^{T} A_{B}^{- 1} = (4, 1) (\begin{matrix} 1 & - 1 \\ 0 & 1 \end{matrix}) = (4, - 3) .

Now the nonbasic variable $x_{3}$ has $c_{3} = 0$ and $A_{3} = (1, 0)^{T}$ :

{\bar{c}}_{3} = 0 - (4, - 3) (\begin{matrix} 1 \\ 0 \end{matrix}) = - 4 .

The coefficient says zero; the reduced cost says $- 4$ . A variable that appears free in the objective is in fact the most improving move available, because bringing it in relieves the basis of expensive adjustments.

The error runs the other way too: a variable with a small positive $c_{j}$ can have a positive reduced cost large enough to rule it out, or a variable with a negative $c_{j}$ can have a positive reduced cost once the compensating adjustment is priced in.

The reliable rule is that $c_{j}$ alone is never sufficient. The reduced cost depends on the basis, so it must be recomputed whenever the basis changes. The same variable will have different reduced costs at different corners.

Common errors

Common misconception

The reduced cost of a variable is just its objective coefficient, so a variable with a negative coefficient always improves the objective when brought into the basis.

Reduced Costs and the Optimality Test

Assumptions and scope

Worked material

The cost coefficient is not the reduced cost

Common errors

Related units

Requires

Connected

Learn this topic

Used in

Sources

Settings

Focus timer

Today

Last seven days

Where the time went

Recent sessions

Settings

Notifications

Your history