# Negative reduced cost for basic variable

I am observing something unusual : after solving a linear program, some basic variables have negative reduced costs (instead of $$0$$) :

CPLEX> display which sensitivity analysis: objective *

Variable Name      Reduced Cost            Down         Current              Up

Path_P168                  zero       -infinity     305767.0000       +infinity
Path_P198                  zero    1764192.0000    1790688.0000       +infinity
Path_P203           -13636.0000       -infinity      58440.0000      72076.0000
Path_P204           -51212.0000       -infinity     207739.0000     258951.0000
Path_P205           -35112.0000       -infinity     247247.0000     282359.0000

CPLEX> display solution variables *

Variable Name           Solution Value
Path_P168                     1.000000
Path_P198                     0.094203
Path_P203                     1.000000
Path_P204                     1.000000
Path_P205                     1.000000


In the above sensitivity report generated by CPLEX, variable Path_P203 for example, has value $$1$$ and reduced cost $$-13636$$. The solution status is optimal.

I thought this was impossible (as basic variables should have reduced costs equal to $$0$$). Can someone provide an explanation ?

Thanks !

• Can you verify whether the solution status is optimal? – Kevin Dalmeijer Jan 30 at 14:00
• good point. The solution status is OPTIMAL. – Kuifje Jan 30 at 14:27

• Thanks for you help. I'm not sure I understand. The solution provided by CPLEX is $1.0$. I do not believe it is the upper bound. – Kuifje Jan 30 at 16:25
• If Path_P203 has domain $[0,1]$ (meaning that the upper bound of 1 was set on the variable, not added as a functional constraint), and if you are minimizing, then Path_P203 may be nonbasic with a negative reduced cost. In essence, when a basic variable $x$ with domain $[0, u]$ reaches its upper bound $u$ during a pivot, it can be replaced internally with $\tilde{x}=u-x$, which leaves the basis as a result of the pivot (with $\tilde{x} = 0$ and with reduced cost the opposite of the reduced cost of $x$, hence positive). – prubin Jan 30 at 20:24