Hi Xypron,
Sorry I should have been clearer.
I use the glpk-java bindings present on http://glpk-java.sourceforge.net/only.
I use (and referred to) GLPK._glp_lpx_simplex(lp) and
GLPK._glp_lpx_integer(lp) in my Java Code.
Additionally, I was referring to the analogous GLPK._glp_lpx_* functions in
my previous mail.
The problem is reproducible for me, although I don't know how you could
reproduce it since any individual lp instance can independently be solved
correctly by GLPK.
Additionally, I do set
GLPK._glp_lpx_set_real_parm(this.lp, GLPK.LPX_K_TOLOBJ, 0.001);
before I call the solve function. I thought this would have helped
The tail end part of the output log is below (where GLPK gets stuck in
infinite loops --- performing many iterations w/o any progress).
Thanks,
Manish Jain
University of Southern California
Tail End of output log:
Iteration 41
GLPK Simplex Optimizer, v4.44
39 rows, 390 columns, 1119 non-zeros
Preprocessing...
39 rows, 388 columns, 1079 non-zeros
Scaling...
A: min|aij| = 1.000e+000 max|aij| = 1.000e+000 ratio = 1.000e+000
Problem data seem to be well scaled
Constructing initial basis...
Size of triangular part = 39
1428: obj = 0.000000000e+000 infeas = 2.000e+000 (0)
* 1429: obj = 0.000000000e+000 infeas = 0.000e+000 (0)
* 1440: obj = 1.000000000e+002 infeas = 0.000e+000 (0)
OPTIMAL SOLUTION FOUND
GLPK Integer Optimizer, v4.44
39 rows, 390 columns, 1119 non-zeros
352 integer variables, 350 of which are binary
Integer optimization begins...
+ 1440: mip = not found yet <= +inf (1; 0)
+ 1442: >>>>> 1.000000000e+002 <= 1.000000000e+002 0.0% (1; 0)
+ 1442: mip = 1.000000000e+002 <= tree is empty 0.0% (0; 1)
INTEGER OPTIMAL SOLUTION FOUND
GLPK Simplex Optimizer, v4.44
14210 rows, 392 columns, 878 non-zeros
Preprocessing...
208 rows, 376 columns, 852 non-zeros
Scaling...
A: min|aij| = 1.000e+000 max|aij| = 1.000e+000 ratio = 1.000e+000
Problem data seem to be well scaled
Constructing initial basis...
Size of triangular part = 186
2698: obj = 0.000000000e+000 infeas = 3.000e+000 (22)
* 2770: obj = -6.000000000e-001 infeas = 0.000e+000 (8)
* 2800: obj = -5.000000000e-001 infeas = 0.000e+000 (3)
* 2840: obj = 3.125648139e-017 infeas = 3.173e-015 (1)
OPTIMAL SOLUTION FOUND
GLPK Integer Optimizer, v4.44
14210 rows, 392 columns, 878 non-zeros
352 integer variables, all of which are binary
Integer optimization begins...
+ 2840: mip = not found yet <= +inf (1; 0)
+ 2906: >>>>> 4.790982676e-017 <= 4.790982676e-017 0.0% (17; 0)
+ 2906: mip = 4.790982676e-017 <= tree is empty 0.0% (0; 33)
INTEGER OPTIMAL SOLUTION FOUND
GLPK Simplex Optimizer, v4.44
14210 rows, 392 columns, 879 non-zeros
Preprocessing...
208 rows, 378 columns, 855 non-zeros
Scaling...
A: min|aij| = 1.000e+000 max|aij| = 1.000e+000 ratio = 1.000e+000
Problem data seem to be well scaled
Constructing initial basis...
Size of triangular part = 187
1269: obj = 0.000000000e+000 infeas = 2.000e+000 (21)
* 1327: obj = -2.500000000e-001 infeas = 0.000e+000 (3)
* 1350: obj = 4.790982676e-017 infeas = 0.000e+000 (3)
OPTIMAL SOLUTION FOUND
GLPK Integer Optimizer, v4.44
14210 rows, 392 columns, 879 non-zeros
352 integer variables, all of which are binary
Integer optimization begins...
+ 1350: mip = not found yet <= +inf (1; 0)
+ 1352: >>>>> 4.790982676e-017 <= 4.790982676e-017 0.0% (1; 0)
+ 1352: mip = 4.790982676e-017 <= tree is empty 0.0% (0; 1)
INTEGER OPTIMAL SOLUTION FOUND
GLPK Simplex Optimizer, v4.44
40 rows, 42 columns, 1105 non-zeros
Preprocessing...
40 rows, 42 columns, 1105 non-zeros
Scaling...
A: min|aij| = 1.000e+000 max|aij| = 1.000e+002 ratio = 1.000e+002
GM: min|aij| = 9.955e-001 max|aij| = 1.005e+000 ratio = 1.009e+000
EQ: min|aij| = 1.000e+000 max|aij| = 1.000e+000 ratio = 1.000e+000
Constructing initial basis...
Size of triangular part = 40
309: obj = 0.000000000e+000 infeas = 4.635e+001 (0)
* 310: obj = -1.000000000e+002 infeas = 0.000e+000 (0)
* 331: obj = -5.000000000e+001 infeas = 3.294e-015 (0)
OPTIMAL SOLUTION FOUND
Iteration 42:
GLPK Simplex Optimizer, v4.44
40 rows, 391 columns, 1177 non-zeros
Preprocessing...
40 rows, 389 columns, 1136 non-zeros
Scaling...
A: min|aij| = 1.000e+000 max|aij| = 1.000e+000 ratio = 1.000e+000
Problem data seem to be well scaled
Constructing initial basis...
Size of triangular part = 40
1442: obj = 0.000000000e+000 infeas = 2.000e+000 (0)
* 1443: obj = 0.000000000e+000 infeas = 0.000e+000 (0)
* 1470: obj = 1.000000000e+002 infeas = 0.000e+000 (0)
OPTIMAL SOLUTION FOUND
GLPK Integer Optimizer, v4.44
40 rows, 391 columns, 1177 non-zeros
352 integer variables, 350 of which are binary
Integer optimization begins...
+ 1470: mip = not found yet <= +inf (1; 0)
+ 1472: >>>>> 1.000000000e+002 <= 1.000000000e+002 0.0% (1; 0)
+ 1472: mip = 1.000000000e+002 <= tree is empty 0.0% (0; 1)
INTEGER OPTIMAL SOLUTION FOUND
GLPK Simplex Optimizer, v4.44
14562 rows, 393 columns, 884 non-zeros
Preprocessing...
211 rows, 377 columns, 858 non-zeros
Scaling...
A: min|aij| = 1.000e+000 max|aij| = 1.000e+000 ratio = 1.000e+000
Problem data seem to be well scaled
Constructing initial basis...
Size of triangular part = 189
2906: obj = 0.000000000e+000 infeas = 3.000e+000 (22)
* 2978: obj = -2.500000000e-001 infeas = 0.000e+000 (8)
* 3000: obj = -1.875000000e-001 infeas = 1.665e-016 (7)
* 3002: obj = -1.666666667e-001 infeas = 0.000e+000 (7)
OPTIMAL SOLUTION FOUND
GLPK Integer Optimizer, v4.44
14562 rows, 393 columns, 884 non-zeros
352 integer variables, all of which are binary
Integer optimization begins...
+ 3002: mip = not found yet <= +inf (1; 0)
+ 3094: >>>>> -5.000000000e-001 <= -2.500000000e-001 50.0% (18; 0)
+ 4122: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (47; 141)
+ 5166: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (67; 280)
+ 6299: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (41; 516)
+ 7494: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (54; 665)
+ 8501: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (78; 793)
+ 9609: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (52; 1025)
+ 10829: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (38; 1197)
+ 11910: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (43; 1384)
+ 13045: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (37; 1578)
+ 14268: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (53; 1763)
+ 15839: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (46; 1964)
Time used: 60.0 secs. Memory used: 10.8 Mb.
+ 17378: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (54; 2158)
+ 18742: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (56; 2365)
+ 20010: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (63; 2528)
+ 21433: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (53; 2735)
+ 23037: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (59; 2914)
+ 24626: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (55; 3115)
+ 26025: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (59; 3317)
+ 27219: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (60; 3525)
+ 28526: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (63; 3729)
+ 29914: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (63; 3903)
+ 31387: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (55; 4117)
+ 32653: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (63; 4322)
Time used: 120.0 secs. Memory used: 10.8 Mb.
+ 34051: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (59; 4542)
+ 35588: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (61; 4758)
+ 36878: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (56; 5000)
+ 38334: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (54; 5215)
+ 39495: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (53; 5404)
+ 40839: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (50; 5611)
+ 41776: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (59; 5767)
+ 43000: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (55; 5958)
+ 44319: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (60; 6161)
+ 45709: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (50; 6374)
+ 46950: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (44; 6597)
+ 48089: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (52; 6777)
Time used: 180.0 secs. Memory used: 10.8 Mb.
+ 49135: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (46; 6967)
+ 50682: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (56; 7141)
+ 52158: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (52; 7314)
+ 53718: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (55; 7485)
+ 55182: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (53; 7688)
+ 56812: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (59; 7865)
+ 58323: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (52; 8079)
+ 59873: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (50; 8254)
+ 61298: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (41; 8497)
+ 62576: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (46; 8707)
+ 63934: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (43; 8920)
+ 65371: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (42; 9119)
Time used: 240.0 secs. Memory used: 10.9 Mb.
+ 67315: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (38; 9313)
+ 68746: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (43; 9486)
+ 70199: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (42; 9698)
+ 71423: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (70; 9844)
+ 72273: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (69; 9964)
+ 73068: mip = -5.000000000e-001 <= -2.500000000e-001 50.0% (107; 10024)
On Fri, Sep 3, 2010 at 10:01 AM, Xypron <[email protected]> wrote:
> Hello Manish,
>
> Output log is attached.
>>>
>>
> I could not find any appendix in your mail.
>
> lpx_simplex(lp);
>>>
>>> I am using GLPK-4.44 Java bindings.
>>> The code is all in Java.
>>>
>>
> Which Java binding do you use?
> The code on bjoern.dapnet.de (which calls lpx_simplex()) has not been
> maintained for years.
> Consider using GLPK for Windows available at
> http://glpk-java.sourceforge.net which supports the current API.
>
>
> Best regards
>
> Xypron
>
>
>
> Manish Jain wrote:
>
>> Hello all,
>>
>> I have a cut/column generation implementation using GLPK 4.44 in Java.
>> I am seeing some weird behavior when I increase the problem size.
>> Glpk just gets stuck in an infinite loop every time after 42 iterations in
>> my case. The problem size is big here (details in the attachment).
>>
>> The weirdness is not that it just gets stuck in an infinite loop. The
>> weird part is that it works fine if instead of calling
>> lpx_simplex/lpx_integer on the problem that is already in memory, I write
>> the problem to a file and load it again.
>> i.e.
>> lpx_simplex(lp);
>> lpx_integer(lp)<- Glpk gets stuck. There is no discernible error message.
>> Output log attached.
>>
>> lpx_write_cpxlp(lp, fileName)
>> lpx_delete_prob(lp)
>> lp = lpx_create_prob()
>> lp = lpx_read_cpxlp(fileName)
>> lpx_simple(lp);
>> lpx_integer(lp);<- Works and gives the solution in about 2 seconds
>>
>> Additionally, if I write the problem to a file when it gets stuck, then I
>> can solve it with glpsol --lp fileName in a matter of 2 secs without any
>> troubles as well.
>>
>> Any ideas, anyone?
>> Also, can anyone explain to me the meaning of various lines of GLPK
>> output, e.g.:
>> + 49135: mip = -5.000000000e-001<= -2.500000000e-001 50.0% (46; 6967)
>> Are these: [Iteration No] [Problem Class] [... ?] ( ...; row-No)
>>
>> I am using GLPK-4.44 Java bindings.
>> The code is all in Java.
>> Output log is attached.
>>
>> Thanks.
>>
>> Manish Jain
>> University of Southern California
>>
>>
>>
>>
>
>
_______________________________________________
Help-glpk mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/help-glpk
