CPLEX - Reduced Costs

Question

I am currently working with cplex and am trying to determine the reduced cost of a LP. I am a little puzzled by the results. My current understanding of reduced cost is that it describes the amount by which a objective function coefficient must improve before a variable can be part of the solution (value = 1).

Thus all basic variables ( non-zero in the solution) have reduced costs of zero. I read that variables that are not part of the current solution can also have a reduced cost of zero if they are at one of their limits. Is that true?

The reduced cost of the following LP confuses me:

minimize 100*x1 + 3*x5
0 <= x0, x1, x2, x3, x4, x5, x6, x7, x8
x0 = 1
x0 - x1 - x2 = 0
x3 = 1
x3 - x4 = 0
x1 - x6 = 0
x2 - x7 = 0
-x4 + x5 - x8 = 0
-x5 + x6 + x7 + x8 = 0

If I use cplex to compute the reduced cost, I get the following result.

Objective Value = 3
Solution = [1, 0, 1, 1, 1, 1, 0, 1, 0]
Reduced Cost = [0 0 0 0 0 0 100 0 3]

I don't understand why the variable x1 has reduced cost of zero, it is neither part of the solution nor is it at the upper limit. Should the reduced value of x1 not be 100 as for variable x7. If I increase the value of x1 by one, I get a solution that is 100 (cost) worse, right?

Here, my C++ code:

#include <ilcplex/ilocplex.h>

int main () {
  IloEnv             env;
  IloModel     model(env);
  IloNumVarArray   x(env);
  x.add(IloNumVar(env)); //default: between $0$ and $+\infty$ 
  x.add(IloNumVar(env));
  x.add(IloNumVar(env)); 
  x.add(IloNumVar(env));
  x.add(IloNumVar(env)); 
  x.add(IloNumVar(env));
  x.add(IloNumVar(env));
  x.add(IloNumVar(env));
  x.add(IloNumVar(env));
  model.add(x[0] == 1);
  model.add(x[0]-x[1]-x[2] == 0);
  model.add(x[3] == 1);
  model.add(x[3]-x[4] == 0);
  model.add(x[1]-x[6] == 0);
  model.add(x[2]-x[7] == 0);
  model.add(-x[4]+x[5]-x[8] == 0);
  model.add(-x[5]+x[6]+x[7]+x[8] == 0);
  model.add(IloMinimize(env, 100*x[1] + 3*x[5]));
  IloCplex cplex(model);
  cplex.solve();
  std::cout << "Min=" << cplex.getObjValue() << std::endl;
  IloNumArray v(env);
  cplex.getReducedCosts(v, x);
  std::cout << v << std::endl;
  env.end();
}

Answer 1

I read that variables that are not part of the current solution can also have a reduced cost of zero if they are at one of their limits. Is that true?

Yes. If the variables are not on their limits, then they have a reduced cost of zero. If they are at one of their limits they can still have a reduced cost of zero, in case multiple primal optimal solutions exist.

Then, your problem can be seen as a flow problem on the following network:

Each arc represents the variable value of the node it enters (e.g., 1 = x0). The optimal solution corresponds to the path 0-2-7-5-4-3, which has a total cost of 3. In case you force x1 (or x6) equal to 1, then the solution will change to x0=x1=x6=x5=x4=x3=1.

Now, dual values and shadow prices are meaningful only when the optimal basis remains the same. Forcing x1=1 changes the optimal basis (because a different path is optimal) and therefore the corresponding dual values may not be meaningful.

An alternative interpretation of the reduced cost is to think of it as the dual price of the non-negativity constraints (i.e., showing how much the objective function will increase in case one unit of a non-basic or zero-level basic variable is forced into the basis at level 1 - assuming non-negativity constraints). Again, its value may not be correct if this alteration changes the optimal basis.

Since the reduced costs are the dual values of the corresponding non-negativity constraints, another experiment you can try is to add explicitly the non-negativity constraints as constraints and then check their dual values. For x6>=0 I get a dual value of 100 and an allowable increase of the right-hand-side = 1, while for x1>=0 I get a dual value of 0 and an allowable increase of the right-hand-side of 0. This, practically means that the dual value (which is the reduced cost in the case) is not meaningful.

I hope this helps.