Re: [Help-glpk] glp_intopt runs forever (related to Dusan Plavak's issue)

[Heinrich Schuchardt]

Hello Rafael,

even after scaling your model the ratio between minimum and maximum
coefficient in the matrix is very big. See below.

Please, check the code that generates your model:

Can't the following values be set to zero:
+ 4e-12 x_5

Maybe these values just arise due to rounding errors in the code you use
to generate the model?

Maybe also the difference between the x_5 coefficients in r_1 and r_2
are due to rounding errors?

You could simply round all values to the nearest multiple of
10E-8 or of 2^-27.

#include <math.h>
ar[counter] = floor(100000000. * left_parts[i][j] + .5) / 100000000.;

Best regards

Heinrich Schuchardt

Writing problem data to 'problem.lp'...
51 lines were written
GLPK Integer Optimizer, v4.62
13 rows, 9 columns, 73 non-zeros
5 integer variables, none of which are binary
Preprocessing...
9 rows, 9 columns, 53 non-zeros
5 integer variables, none of which are binary
Scaling...
 A: min|aij| =  4.000e-12  max|aij| =  1.875e+01  ratio =  4.688e+12
GM: min|aij| =  4.116e-04  max|aij| =  2.430e+03  ratio =  5.903e+06
EQ: min|aij| =  1.694e-07  max|aij| =  1.000e+00  ratio =  5.903e+06
2N: min|aij| =  1.242e-07  max|aij| =  1.435e+00  ratio =  1.156e+07
Constructing initial basis...
Size of triangular part is 9
Solving LP relaxation...
GLPK Simplex Optimizer, v4.62
9 rows, 9 columns, 53 non-zeros
      0: obj =   0.000000000e+00 inf =   3.793e+04 (4)
      6: obj =   6.353265000e+00 inf =   0.000e+00 (0)
*     9: obj =  -6.292433767e-16 inf =   1.722e-12 (0)
OPTIMAL LP SOLUTION FOUND
Integer optimization begins...
+     9: mip =     not found yet >=              -inf        (1; 0)
+    20: >>>>>   1.799565000e-01 >=  -5.670240878e-16 100.0% (8; 0)
Warning: numerical instability (dual simplex, phase II)
Warning: numerical instability (dual simplex, phase II)
Warning: numerical instability (dual simplex, phase II)



On 06/10/2017 12:29 PM, Rafael Korbaš wrote:
> Hello Heinrich,
> 
> 
> I'm Dusan's colleague and I'm also trying to understand, why our
> lp-solving function in certain conditions loops forever. Dusan forwarded
> me your email and I've read it. As you pointed out, if we try to solve
> the problem statement obtained through the glp_write_lp(), everything is
> fine.
> 
> Therefore I came up with a compilable C++ code (the "main.cpp"
> attachment) that replicates the issue. The problem statement is
> hardcoded, so the only thing you need to do is to compile it, e.g. with
> the following command:
> 
> g++ main.cpp -std=gnu++11 -lglpk
> 
> And run it.
> 
> It should output the line "51 lines were written", since it writes the
> problem statement to the problem.lp file and afterwards, it loops
> foreverer at the line 152 (the "glp_intopt" call). I have a feeling that
> the "problem.lp" file gets solved without problems, because of some
> rounding during the output of the "glp_write_lp" function, but I don't
> see that deep into the issue to draw any conclusions.
> 
> I use the latest available version of libglpk, i.e. version 4.61, the
> same as Dusan.
> 
> I hope that I provided you enough information to replicate the behavior
> by yourself and if you need anything else, don't hesitate to write us an
> email.
> 
> 
> Best regards,
> 
> Rafael
>

problem.lp
Description: Text document