Re: [Bug-glpk] Bug in Dual/Reduced Cost computation for a simple lp

[Andrew Makhorin]

Hi Anurag,

> I am trying to use GLPK (version 4.13) to model a simple supply chain
> network model to be solved as a linear program. The duals I am getting
> for this linear program are not correct for a corner case (when demand
> is equal to supply). I cross checked with cplex solver to see the
> right dual/reduced costs for those variables and indeed cplex is
> giving me the expected answer.
> 
> Please find attached the lp file (cplexlp.lp in cplex format) that you
> can use with interactive cplex and glpsol both. The variables in
> question are: Res1T1, Res1T2, Res1T3, Res1T4. The reduced costs of
> these variables is not correct. Similarly the duals on rows Res1R1,
> Res1R2, Res1R3, Res1R4 is also not correct. Please find attached the
> solution files out of cplex (cplexsol.txt) and glpk 4.13 (glpsol.txt)
> with this mail.
> 
> Use of correct duals and reduced costs is important for my project.
>
> Please help!

There is no error. You obtained different duals, because your model
has multiple optimal solutions. Cplex found one of them, and glpk found
another. For example, in the solution found by cplex Res1T1 is
non-basic on its upper bound, while in the solution found by glpk
Res1T1 is basic. However, both solutions are equivalent in the sense
that they both satisfy to the same optimality conditions.

> Lastly I do appreciate your work and effort for the
> freeware implementation of a lp solver. This really is great work for
> the open source community!

Thank you for your interest in glpk.


Andrew Makhorin