Re: [Bug-glpk] bug in simplex for small dimensions ?

[Andrew Makhorin]

>    on the following problem :
> 
> 
> Minimize
>       func: - x1 - x2
> Subject To
>     cst1:  0.9510565162951536 x1 + 6.909830056250525e-01 x2 <= 
> 2.5930960382153598
>     cst2: -0.3632712640026803 x1 + 1.118033988749895e+00 x2 <= 
> 1.7058192410423680
>     cst3: -1.1755705045849463 x1 + 2.220446049250313e-16 x2 <= 
> -0.2245139882897925
>     cst4: -0.3632712640026806 x1 - 1.118033988749895e+00 x2 <= 
> -0.5302487364574219
>     cst5:  0.9510565162951534 x1 - 6.909830056250528e-01 x2 <= 
> 1.2111300269652543
> End
> 
>    the simplex and interior methods give 2 very different solutions.
> 
>    glpsol --lp test_glpk.LP --interior -o sol_interieur.txt
>    glpsol --lp test_glpk.LP --simplex -o sol_simplex.txt
> 
>    I have tested this with v4.47 and v4.44. The interior solution
>    is the good one, the simplex one doesn't verify constraints.
>    I use the v4.44 version provided by the rpm package of my
>    linux distribution (mageia 1) and I have compiled the v4.47
>    (so as to test with glpsol which is apparently not provided
>    with the v4.44 rpm mageia package). My machine is a dell
>    6420 laptop running the 64 bits linux (mageia 1).

The error occurs because of tiny (i.e. close to zero) constraint
coefficients (2.22e-16).

By default, before calling the simplex solver, glpsol scales the lp
instance with the geometric mean scaling method, in which case tiny
constraint coefficients lead to badly conditioned constraint matrix,
that, in turn, leads to excessive round-off errors and therefore wrong
results. To make the computations more stable you need to either disable
automatic scaling and using the lp presolver (--nopresol --noscale), or,
that is much better, remove tiny constraint coefficients from your lp
instance replacing them with exact zeros.