7

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 ?

SecretAgentMan
  • 1,895
  • 2
  • 13
  • 39
Kuifje
  • 13,324
  • 1
  • 23
  • 56

1 Answers1

4

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.

Philipp Christophel
  • 3,188
  • 8
  • 24
  • 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 '20 at 16:25
  • 3
    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 '20 at 20:24