Originally posted by: lxysjtu

Dear all,

I used CPLEX to solve the attached minimization lp.

The returned optimal solution has some variables with negative reduced cost. Logically it should not happen.

But I do not know how to figure out this issue.

Thanks.

Shaon

Originally posted by: Laci Ladanyi

If in a minimization problem you have an out of basis variable at its upper bound in an optimal solution then that will have negative reduced cost.

--Laci

Originally posted by: lxysjtu

Thanks, would you please give me detailed explanation?

For a minimization problem, in the optimal solution, a non-basic variable should have non-negative reduced cost and basic variable should have reduced cost of zero.

In my attached model, the optimal solution has non basic variable z_7_6 =1 with reduced cost  -0.008333. It is strange!!

What you said is true for a variable x with lower bound zero and upper bound infinity, as you commonly encounter in textbook treatments of the simplex method. If a variable x declared over [0, U] reaches its upper bound U, it is replaced in the basis with x' = U - x, with x' nomadic at its lower bound (0). The reduced cost of x' will be negative, as you expect, but that is the negative of the reduced cost of x, as Laci said.