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: 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
_______________________________________________
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk
