Hi there, I have a small integer program whose optimal solution value is 49. Root relaxation is 48.5454. Since all the variables are integer, one expects it to stop when a solution with value 49 is found. Instead, GLPK takes a long time to converge.
I also tried lp-solve, it found an optimal solution quickly (less than 0.1 second). Here is the output: Optimal solution 49 after 72 iter, 34 nodes (gap 0.0%). Value of objective function: 49 Branch Bound depth: 18 Nodes processed: 34 Simplex pivots: 72 Number of equal solutions: 1 I don #39;t think lp-solve is doing anything particular. It did not generate cuts and just branched on the first fractional integer variable. An mps file is attached. I would appreciate if someone can explain why it is taking so long. Thanks. John Part of output from glpsol: C:\glpk-4.28\w32>glpsol c:\binPacking.mps lpx_read_freemps: reading problem data from `c:\binPacking.mps #39;... lpx_read_freemps: problem name not specified lpx_read_freemps: 11 rows, 63 columns, 214 non-zeros lpx_read_freemps: 63 integer columns, none of which are binary lpx_read_freemps: 217 records were read glp_simplex: original LP has 11 rows, 63 columns, 214 non-zeros glp_simplex: presolved LP has 10 rows, 63 columns, 151 non-zeros lpx_adv_basis: size of triangular part = 10 0: objval = 2.858333333e+001 infeas = 1.000000000e+000 (0) 6: objval = 5.141666667e+001 infeas = 0.000000000e+000 (0) * 6: objval = 5.141666667e+001 infeas = 0.000000000e+000 (0) * 14: objval = 4.854545455e+001 infeas = 0.000000000e+000 (0) OPTIMAL SOLUTION FOUND Integer optimization begins... + 14: mip = not found yet >= -inf (1; 0) + 61: >>>>> 4.900000000e+001 >= 4.854545455e+001 0.9% (27; 0) + 12786: mip = 4.900000000e+001 >= 4.854545455e+001 0.9% (5969; 481) + 22206: mip = 4.900000000e+001 >= 4.857142857e+001 0.9% (10705; 883) + 30031: mip = 4.900000000e+001 >= 4.857142857e+001 0.9% (14314; 1294) + 37306: mip = 4.900000000e+001 >= 4.858333333e+001 0.9% (17191; 1690) + 44129: mip = 4.900000000e+001 >= 4.858333333e+001 0.9% (19829; 2067) + 50489: mip = 4.900000000e+001 >= 4.858333333e+001 0.9% (22296; 2419) + 57127: mip = 4.900000000e+001 >= 4.858333333e+001 0.9% (24795; 2734) + 62970: mip = 4.900000000e+001 >= 4.859259259e+001 0.8% (26956; 3049) + 68417: mip = 4.900000000e+001 >= 4.861111111e+001 0.8% (29517; 3316) + 73218: mip = 4.900000000e+001 >= 4.861111111e+001 0.8% (31220; 3611) Time used: 60.0 secs. Memory used: 28.6 Mb. + 77450: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (33126; 3880) + 81914: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (34911; 4141) + 85789: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (36463; 4406) + 89260: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (37852; 4670) + 91991: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (38844; 4937) + 94531: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (39749; 5212) + 97536: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (41015; 5442) +100782: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (42152; 5688) +103186: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (42870; 5944) +105438: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (43556; 6180) +108283: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (44593; 6411) +110995: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (45523; 6608) Time used: 120.0 secs. Memory used: 41.5 Mb. +114152: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (46677; 6822) +117147: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (47797; 7057) +120039: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (48872; 7273) +122422: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (49838; 7486) +125603: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (51022; 7689) +128500: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (52139; 7889) +131392: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (53167; 8084) +133711: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (54087; 8273) +135838: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (54813; 8436) +138047: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (55516; 8640) +140253: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (56277; 8829) +142835: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (57165; 9031) Time used: 180.0 secs. Memory used: 52.2 Mb. +145234: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (58148; 9193) +148262: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (59302; 9362) +150880: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (60157; 9538) +154224: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (61349; 9699) +157114: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (62689; 9858) +160208: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (63928; 10016) Time used: 277.6 secs. Memory used: 58.3 Mb. +163175: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (65073; 10178) +166361: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (66478; 10323) +168935: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (67596; 10475)
Hi there,
I have a small integer program whose optimal solution value is 49. Root relaxation is 48.5454. Since all the variables are integer, one expects it to stop when a solution with value 49 is found. Instead, GLPK takes a long time to converge.
I also tried lp-solve, it found an optimal solution quickly (less than 0.1 second). Here is the output:
Optimal solution 49 after 72 iter, 34 nodes (gap 0.0%).
Value of objective function: 49
Branch & Bound depth: 18
Nodes processed: 34
Simplex pivots: 72
Number of equal solutions: 1
I don't think lp-solve is doing anything particular. It did not generate cuts and just branched on the first fractional integer variable.
An mps file is attached. I would appreciate if someone can explain why it is taking so long.
Thanks.
John
Part of output from glpsol:
C:\glpk-4.28\w32>glpsol c:\binPacking.mps
lpx_read_freemps: reading problem data from `c:\binPacking.mps'...
lpx_read_freemps: problem name not specified
lpx_read_freemps: 11 rows, 63 columns, 214 non-zeros
lpx_read_freemps: 63 integer columns, none of which are binary
lpx_read_freemps: 217 records were read
glp_simplex: original LP has 11 rows, 63 columns, 214 non-zeros
glp_simplex: presolved LP has 10 rows, 63 columns, 151 non-zeros
lpx_adv_basis: size of triangular part = 10
0: objval = 2.858333333e+001 infeas = 1.000000000e+000 (0)
6: objval = 5.141666667e+001 infeas = 0.000000000e+000 (0)
* 6: objval = 5.141666667e+001 infeas = 0.000000000e+000 (0)
* 14: objval = 4.854545455e+001 infeas = 0.000000000e+000 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+ 14: mip = not found yet >= -inf (1; 0)
+ 61: >>>>> 4.900000000e+001 >= 4.854545455e+001 0.9% (27; 0)
+ 12786: mip = 4.900000000e+001 >= 4.854545455e+001 0.9% (5969; 481)
+ 22206: mip = 4.900000000e+001 >= 4.857142857e+001 0.9% (10705; 883)
+ 30031: mip = 4.900000000e+001 >= 4.857142857e+001 0.9% (14314; 1294)
+ 37306: mip = 4.900000000e+001 >= 4.858333333e+001 0.9% (17191; 1690)
+ 44129: mip = 4.900000000e+001 >= 4.858333333e+001 0.9% (19829; 2067)
+ 50489: mip = 4.900000000e+001 >= 4.858333333e+001 0.9% (22296; 2419)
+ 57127: mip = 4.900000000e+001 >= 4.858333333e+001 0.9% (24795; 2734)
+ 62970: mip = 4.900000000e+001 >= 4.859259259e+001 0.8% (26956; 3049)
+ 68417: mip = 4.900000000e+001 >= 4.861111111e+001 0.8% (29517; 3316)
+ 73218: mip = 4.900000000e+001 >= 4.861111111e+001 0.8% (31220; 3611)
Time used: 60.0 secs. Memory used: 28.6 Mb.
+ 77450: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (33126; 3880)
+ 81914: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (34911; 4141)
+ 85789: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (36463; 4406)
+ 89260: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (37852; 4670)
+ 91991: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (38844; 4937)
+ 94531: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (39749; 5212)
+ 97536: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (41015; 5442)
+100782: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (42152; 5688)
+103186: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (42870; 5944)
+105438: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (43556; 6180)
+108283: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (44593; 6411)
+110995: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (45523; 6608)
Time used: 120.0 secs. Memory used: 41.5 Mb.
+114152: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (46677; 6822)
+117147: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (47797; 7057)
+120039: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (48872; 7273)
+122422: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (49838; 7486)
+125603: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (51022; 7689)
+128500: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (52139; 7889)
+131392: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (53167; 8084)
+133711: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (54087; 8273)
+135838: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (54813; 8436)
+138047: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (55516; 8640)
+140253: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (56277; 8829)
+142835: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (57165; 9031)
Time used: 180.0 secs. Memory used: 52.2 Mb.
+145234: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (58148; 9193)
+148262: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (59302; 9362)
+150880: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (60157; 9538)
+154224: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (61349; 9699)
+157114: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (62689; 9858)
+160208: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (63928; 10016)
Time used: 277.6 secs. Memory used: 58.3 Mb.
+163175: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (65073; 10178)
+166361: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (66478; 10323)
+168935: mip = 4.900000000e+001 >= 4.862500000e+001 0.8% (67596; 10475)
binPacking.mps
Description: Binary data
_______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
