Re: glp_intopt runs forever (related to Dusan Plavak's issue)

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
>

_______________________________________________
Help-glpk mailing list
[email protected]
https://lists.gnu.org/mailman/listinfo/help-glpk

\* Problem: amounts *\

Minimize
 obj: + 0.03 x_6 + 0.0375 x_7 + 0.075 x_8 + 0.0375 x_9

Subject To
 r_1: + 9.3 x_5 + 2.548 x_4 + 0.17905 x_3 + 5.0773125 x_2 + 1.0491 x_1
 - ~r_1 = -80000
 r_2: + 9.3 x_5 + 0.744 x_4 + 0.02325 x_3 + 0.6800625 x_2 + 0.0651 x_1
 - ~r_2 = -32000
 r_3: + 0.369 x_4 + 0.10291 x_3 + 3.5285625 x_2 + 0.0082 x_1 - ~r_3
 = -16000
 r_4: + 1.435 x_4 + 0.05289 x_3 + 0.8686875 x_2 + 0.9758 x_1 - ~r_4
 = -32000
 r_5: + x_5 + 10 x_4 + x_3 + 18.75 x_2 + x_1 <= 800
 r_6: + x_6 + 9.3 x_5 + 2.548 x_4 + 0.17905 x_3 + 5.0773125 x_2
 + 1.0491 x_1 >= 400
 r_7: - x_6 + 9.3 x_5 + 2.548 x_4 + 0.17905 x_3 + 5.0773125 x_2
 + 1.0491 x_1 <= 400
 r_8: + x_7 + 9.3 x_5 + 0.744 x_4 + 0.02325 x_3 + 0.6800625 x_2
 + 0.0651 x_1 >= 160
 r_9: - x_7 + 9.3 x_5 + 0.744 x_4 + 0.02325 x_3 + 0.6800625 x_2
 + 0.0651 x_1 <= 160
 r_10: + x_8 + 0.369 x_4 + 0.10291 x_3 + 3.5285625 x_2 + 0.0082 x_1
 >= 80
 r_11: - x_8 + 0.369 x_4 + 0.10291 x_3 + 3.5285625 x_2 + 0.0082 x_1
 <= 80
 r_12: + x_9 + 1.435 x_4 + 0.05289 x_3 + 0.8686875 x_2 + 0.9758 x_1
 >= 160
 r_13: - x_9 + 1.435 x_4 + 0.05289 x_3 + 0.8686875 x_2 + 0.9758 x_1
 <= 160

Bounds
 0 <= ~r_1 <= 160000
 0 <= ~r_2 <= 64000
 0 <= ~r_3 <= 32000
 0 <= ~r_4 <= 64000
 100 <= x_1 <= 400
 8 <= x_2 <= 16
 2 <= x_3 <= 400
 4 <= x_4 <= 20
 4 <= x_5 <= 30

Generals
 x_1
 x_2
 x_3
 x_4
 x_5

End