CODEWITHSUNDEEP
optimizationlinear-programmingcplex
E. Su
E. Su

Reputation: 1

Why the reduced cost for the nonbasic variable can be negative?

I am working the column generation with the IP solver CPLEX.

When the master problem was solved to optimal, I output the basis information, and I found that there is a nonbasic varible takes value 1.0, and its reduced cost is negative, although the status of the cplex model is optimal.

I can't really understand what happen to this phenomenon. Maybe it is because that the solver can attach both the lower and upper bounds on a variable (eg. [0,1] in my experiment), so the reduced cost of a nonbasic variable can be negative, and its value reaches the upper bound. But I don't know how to prove it.

Any help would be greatly appreciated. Thank you very much!

Upvotes: 0

Views: 558

Answers (2)

user29057184
user29057184

Reputation: 1

I found the same problem. I'm minimizing using CPLEX. I found that some non basic variables take value = 1 (for the [0,1] bounded case) and the reduced cost is strictly negative.

Upvotes: 0

Erwin Kalvelagen
Erwin Kalvelagen

Reputation: 16714

Depends on maximization or minimization and on whether the variable is at lower bound or at upper bound.

enter image description here

Upvotes: 0

Related Questions