Originally posted by: LoadPlanner

I am looking for some insight in why I am getting zero reduced costs for variables that are not alternate optimals for my general assignment problem. We have 3 drivers (A,B,C) and 2 loads (1,2), with XDL variables denoting Driver-load variables. We also have added slack variables for Drivers that are not assigned (NAD) and loads that are not assigned (NAL) with high costs (500), so it won't be cost efficient to not assign a driver/load if there are loads/drivers available. The LP is:

Minimize
obj: 500 NAL_1 + 1 XDL_A_1 + 7 XDL_B_1 + 151 XDL_C_1
+ 500 NAL_2 + 1 XDL_A_2 + 7 XDL_B_2 + 151 XDL_C_2
+ 500 NAD_A + 500 NAD_B + 500 NAD_C + id31
Subject To
id12: NAL_1 + XDL_A_1 + XDL_B_1 + XDL_C_1 = 1
id15: NAL_2 + XDL_A_2 + XDL_B_2 + XDL_C_2 = 1
id17: XDL_A_1 + XDL_A_2 + NAD_A = 1
id19: XDL_B_1 + XDL_B_2 + NAD_B = 1
id21: XDL_C_1 + XDL_C_2 + NAD_C = 1
Bounds
0 <= NAL_1 <= 1
0 <= XDL_A_1 <= 1
0 <= XDL_B_1 <= 1
0 <= XDL_C_1 <= 1
0 <= NAL_2 <= 1
0 <= XDL_A_2 <= 1
0 <= XDL_B_2 <= 1
0 <= XDL_C_2 <= 1
0 <= NAD_A <= 1
0 <= NAD_B <= 1
0 <= NAD_C <= 1
id31 = 0
End

Note that both loads are identical (same coefficient), so there will be two alternate optimal solutions, drivers A and B assigned to either load 1 and 2, and driver C not being assigned. However, when I get the Reduced costs all 6 XDL variables have Reduced cost of zero. I expect it to be zero for drivers A and B assigned to either loads 1 or 2 (due to the alternate optimal solutions), but surely assigning driver C to either of the loads will increase the Objective Value. What am I not getting here?

Thanks,
Lena
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

You hit the two-for-one special: your solution has both primal degeneracy and dual degeneracy (the latter translating to multiple optima). If you display the optimal basis CPLEX gets, you'll see several of the variables with zero values are basic. For instance, I get a basis of

XDL_A_1  XDL_C_1  XDL_A_2  XDL_B_2  NAD_B

for the 1->A, 2->B solution. Note that XDL_C_1 is in the basis. The marginal cost of pivoting XDL_C_2 in is zero; it just replaces XDL_C_1 at value 0. Hence the zero reduced cost for XDL_C_2.

To test this, try dropping the cost of either XDL_C_? variable to 150 and see what happens to the reduced cost of the other one.

/Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: LoadPlanner

Thank you Paul! I guess this means that the definition of Reduced cost for a specific variable is the increase in objective value to pivot that (non-basic) variable into the basis (thus the zero Reduced cost for basic variables with value zero makes sense)? I was under the impression (after reading various online sources) that the definition was the increase in objective value to increase that variable by one unit, and this is what we would need it to be.

Do you (or anyone else) know if there is something we can do with this model, to garantee a Reduced cost (that is >0 if not optimal) for all variables that are not 1? I assume it would need to be non-degenerate. Small changes in the coefficiants would be fine. Note that our problem is much larger than this, with a few hundred drivers and loads, so it's not something we could manually do.

Thanks again!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

The reduced costs only look at the basis cone, and not at the full model. Therefore, they are the change in the objective function if you increase the variable by one unit but discard all bounds of basic variables and all basic rows.
Since the basis cone is a relaxation of the full LP model, this means that the reduced costs provide a lower bound on the change in the objective function when increasing the variable by one unit.

To get rid of degeneracy, one would typically introduce small perturbations to the objective function and/or the right hand side.

Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> LoadPlanner wrote:
> I guess this means that the definition of Reduced cost for a specific variable is the increase in objective value to pivot that (non-basic) variable into the basis (thus the zero Reduced cost for basic variables with value zero makes sense)? I was under the impression (after reading various online sources) that the definition was the increase in objective value to increase that variable by one unit, and this is what we would need it to be.

Your original understanding is correct, give or take the "one unit" part. The reduced cost of a marginal variable is the net rate of change of the objective as the nonbasic variable increases, disregarding its bounds, as Tobias pointed out but assuming that the basic variables adjust (also disregarding their bounds) to maintain constraint feasibility. Your problem stems from having multiple optimal solutions.

You can associate every variable with a constraint. For slack variables, the association is obvious; for "natural" variables, the corresponding constraint is one of their bounds. The nonbasic variables correspond to the constraints that are binding at the current solution. Increasing one of them means moving off the hyperplane of that constraint while staying on the hyperplanes of the other binding constraints -- in other words, moving along an edge. The reduced cost is the rate of change of the objective along that edge. If the edge connects two optimal solutions, the rate of change of the objective is zero, so you get a zero reduced cost for a nonbasic variable.

> Do you (or anyone else) know if there is something we can do with this model, to garantee a Reduced cost (that is >0 if not optimal) for all variables that are not 1? I assume it would need to be non-degenerate.

Not exactly. The dual would need to be nondegenerate, which means the primal would need to have a unique optimum.

> Small changes in the coefficiants would be fine.

As Tobias suggested, small random perturbations to the objective function should give you a unique optimal solution.

/Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: LoadPlanner

Thank you both for your answers. We now have a better understanding of the Reduced costs we are seeing and some ideas on where to go from here. I did post a new question http://www.ibm.com/developerworks/forums/thread.jspa?threadID=355359&tstart=0 about a different issue we were seeing with the same model. I would really appreciate if you could take a look at that post as well.

Thank you much!
#CPLEXOptimizers
#DecisionOptimization