Reduced Costs and the Optimality Test

A variable's cost coefficient tells you what it costs directly. It says nothing about what the basic variables must give up to accommodate it, which is the number that actually decides whether bringing it in helps.

This is the test the simplex method runs at every iteration. The previous unit established that the search can be confined to corners; this one supplies the stopping rule. Without it an algorithm could move between corners forever with no way to recognize that it has arrived.

The reduced cost also answers a question worth asking on its own: what would it actually cost to start using a variable currently held at zero.

This unit assumes you can identify a basis and its basic feasible solution, and that you can invert a small matrix or solve a small linear system.

A nonbasic variable sits at zero. Ask what happens if you raise it to one.

Two things change, not one.

The direct effect is the obvious one: the objective picks up $c_j$, the variable's own cost coefficient.

The indirect effect is the one that is easy to forget. The constraints $Ax=b$ still have to hold. Raising $x_j$ consumes resources, so the basic variables must shift to compensate, and those shifts have costs of their own.

The reduced cost is the sum of both effects. It is the net change in the objective per unit of $x_j$, after the compensating adjustment has been paid for.

That is why a variable with an attractive-looking coefficient can still be a bad move: the adjustment it forces may cost more than the variable saves. And it is why the optimality test looks at reduced costs rather than at the cost vector directly.

Let the program be

and let $B$ be a basis with basic columns $A_B$ and basic costs $c_B$.

Reduced cost. For each variable $j$,

Writing $y^{\mathsf{T}}=c_B^{\mathsf{T}}{A}_B^{-1}$, this is ${\overline{c}}_j=c_j-y^{\mathsf{T}}{A}_j$. The vector $y$ is the dual vector associated with the basis, and $y^{\mathsf{T}}{A}_j$ is exactly the indirect cost described above.

Basic variables carry no information. For $j\in B$ the column $A_j$ is a column of $A_B$, so $A_B^{-1}{A}_j$ is a unit vector and

Every basic variable has reduced cost zero by construction. Only the nonbasic ones are informative.

Optimality condition. If ${\overline{c}}_j\ge 0$ for every $j$, the current basic feasible solution is optimal for the minimization program.

The reasoning is direct: any feasible move raises some nonbasic variable, each unit of which changes the objective by that variable's reduced cost. If no reduced cost is negative, no available move lowers the objective.

Given a standard-form minimization program and a basis $B$:

Assemble the basis data. Collect the basic columns into $A_B$ and the corresponding cost entries into $c_B$, in the same order.

Form the dual vector. Solve

which in practice means solving $A_B^{\mathsf{T}}y=c_B$ rather than inverting $A_B$ explicitly.

Compute one reduced cost per nonbasic variable. For each $j\notin B$,

Basic variables can be skipped: their reduced costs are zero by construction.

Apply the test. If every ${\overline{c}}_j\ge 0$, the current basic feasible solution is optimal; stop. If some , that variable is a candidate to enter the basis, because each unit of it lowers the objective by $|{\overline{c}}_j|$.

Check the objective sense before concluding. This test is stated for minimization. For a maximization program, either convert to minimization first or reverse the condition; applying the minimization rule unchanged inverts the answer.

Problem. For the program

subject to

decide whether the basis $B=\{3,4\}$ is optimal.

Goal. Compute the reduced costs of the nonbasic variables $x_1$ and $x_2$ and apply the test.

Relevant principle. A basis is optimal for a minimization program when no nonbasic variable has a negative reduced cost.

Step 1: assemble the basis data.
$A_3=(1,0{)}^{\mathsf{T}}$ and $A_4=(0,1{)}^{\mathsf{T}}$, so $A_B=I$. The basic costs are $c_3=0$ and $c_4=0$, so $c_B=(0,0{)}^{\mathsf{T}}$.
Reason: the slack columns happen to form an identity basis, which makes this the natural starting basis.

Step 2: form the dual vector.
$y^{\mathsf{T}}=c_B^{\mathsf{T}}{A}_B^{-1}=(0,0)I=(0,0)$.
Reason: with zero basic costs there is no indirect cost to account for at this basis.

Step 3: reduced costs of the nonbasic variables.

Step 4: apply the test.
Both reduced costs are positive, and the basic variables have reduced cost zero. No nonbasic variable is negative, so the basis is optimal.

Check. The basic solution here is $x_3=4$, $x_4=2$, with $x_1=x_2=0$, giving objective value $0$. Since all costs are nonnegative and all variables are constrained to be nonnegative, the objective cannot fall below $0$. The test agrees with what direct reasoning gives.

Interpretation. Both $x_1$ and $x_2$ cost something to use and neither improves the objective, so leaving them at zero is optimal. Had $c_1$ been negative, ${\overline{c}}_1$ would have been negative too and $x_1$ would have been worth bringing in.

Reading $c_j$ in place of ${\overline{c}}_j$ is the most common way this test goes wrong, and it produces confident wrong answers in both directions.

Take

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

Then

The dual vector is

Now the nonbasic variable $x_3$ has $c_3=0$ and $A_3=(1,0{)}^{\mathsf{T}}$:

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.