Re: [Help-glpk] Simplex and Interior Point return different solutions (4.55 vs 4.56+)

[Andrew Makhorin]

On Mon, 2016-04-11 at 14:48 -0400, Marco Montes de Oca wrote:
> Hi.

> I've found several cases where the solution's objective function
> values returned by the simplex method (versions 4.56 onward) and the
> interior point method (versions 4.56 onward) are different. However,
> the same problems on version 4.55 return the same objective function
> value. 
> 
> I know that in the transition between 4.55 and 4.56 the implementation
> of the simplex method changed. I wonder, therefore, whether there is a
> problem in the latest implementation. 

> I'm attaching one of such cases as a .mps file.  I'm just solving the
> LP relaxation of this mixed-integer program as follows:

>       * Simplex:
>                 glpsol --mps test_problem.mps --min  --presol --nomip

>                 As output of 4.55 I see (last line of process):

>                 *  1000: obj =  -1.406015954e+00  infeas =  0.000e+00
>                 (0)

>                 As output of 4.56+ I see:

>                 *   859: obj =  -1.398866953e+00 inf =   0.000e+00 (0)

>       * Interior point:
> 
>                 glpsol --mps test_problem.mps --min  --presol --nomip
>                 --interior

>                 As output of 4.55+ I see:
>                 38: obj =  -1.406134845e+00; rpi =  2.1e-14; rdi =
>                 1.9e-16; gap =  1.8e-09

>                 As output of 4.56+ I see:
>                 38: obj =  -1.406134845e+00; rpi =  2.1e-14; rdi =
>                 1.9e-16; gap =  1.8e-09

> As you can see, the difference between interior point and simplex is
> smaller in 4.55 than it is in 4.56 onward. 

Both solutions are correct *within a tolerance*. You can check the KKT
optimality conditions reported at the end of the solution listing with
the "-o filename" option.

The difference in the optimal objective values occurs because the lp
relaxation of your mip instance is badly conditioned at the optimum,
i.e. the result is highly sensitive to small changes in the input data
caused by round-off errors, perhaps due to large constraint coefficients
used. 


> Thank you. 

> Marco A. Montes de Oca, Ph.D.
> clypd | Principal Data Scientist

> 484.888.8694
> address@hidden

> Connect with us: Twitter | LinkedIn | Facebook