Re: [Help-glpk] GLPK just hangs

[Manish Jain]

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 <address@hidden> 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