7
$\begingroup$

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 !

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Can you verify whether the solution status is optimal? $\endgroup$
    – Kevin Dalmeijer
    Jan 30, 2020 at 14:00
  • 1
    $\begingroup$ good point. The solution status is OPTIMAL. $\endgroup$
    – Kuifje
    Jan 30, 2020 at 14:27

1 Answer 1

Reset to default
4
$\begingroup$

My guess would be that the variable is not basic, it is non-basic but at the upper bound of 1.0.

Modern solvers use the generalized simplex method which allows for lower and upper bounds on a variable. If a variable is upper bounded, its optimal reduced cost needs to be non-positive.

I can't say I fully understand the output you pasted, but it looks like this is the case here.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Kuifje
    Jan 30, 2020 at 16:25
  • 3
    $\begingroup$ 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). $\endgroup$
    – prubin ♦
    Jan 30, 2020 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.