[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Help-glpk] Small Integer Program takes long time to solve
|
From: |
Jian Ye |
|
Subject: |
[Help-glpk] Small Integer Program takes long time to solve |
|
Date: |
Mon, 21 Jul 2008 10:09:24 +0400 |
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] Small Integer Program takes long time to solve,
Jian Ye <=