[Cbc] Convergence problem with miplib2010/30n20b8
ycollette.nospam at free.fr
ycollette.nospam at free.fr
Mon Jun 26 10:39:20 EDT 2017
The missing part of cbc:
At line 1 NAME 30n20b8
At line 2 ROWS
At line 580 COLUMNS
At line 110291 RHS
At line 110322 BOUNDS
At line 128761 ENDATA
Problem 30n20b8 has 576 rows, 18380 columns and 109706 elements
Coin0008I 30n20b8 read with 0 errors
Continuous objective value is 1.56641 - 0.10 seconds
Cgl0004I processed model has 491 rows, 8028 columns (8028 integer (7971 of which binary)) and 53138 elements
Cutoff increment increased from 1e-05 to 0.9999
Cbc0045I 2 integer variables out of 8028 objects (8028 integer) have costs - high priority
Cbc0045I branch on satisfied Y create fake objective Y random cost Y
Cbc0038I Initial state - 196 integers unsatisfied sum - 33.5079
Cbc0038I Pass 1: suminf. 3.44346 (60) obj. 453 iterations 582
Cbc0038I Pass 2: suminf. 3.34653 (60) obj. 453 iterations 19
Cbc0038I Pass 3: suminf. 7.03585 (60) obj. 454.594 iterations 35
Cbc0038I Pass 4: suminf. 7.03585 (60) obj. 454.594 iterations 10
Cbc0038I Pass 5: suminf. 7.10415 (59) obj. 454.594 iterations 8
Cbc0038I Pass 6: suminf. 7.10415 (59) obj. 454.594 iterations 4
Cbc0038I Pass 7: suminf. 10.14507 (56) obj. 454.594 iterations 32
Cbc0038I Pass 8: suminf. 9.78964 (61) obj. 454.594 iterations 14
Cbc0038I Pass 9: suminf. 10.94741 (58) obj. 454.594 iterations 22
Cbc0038I Pass 10: suminf. 11.40422 (62) obj. 454.594 iterations 12
Cbc0038I Pass 11: suminf. 23.07154 (82) obj. 499.914 iterations 27
Cbc0038I Pass 12: suminf. 12.18306 (60) obj. 487.595 iterations 19
Cbc0038I Pass 13: suminf. 12.18306 (60) obj. 487.595 iterations 2
Cbc0038I Pass 14: suminf. 12.19694 (61) obj. 454.594 iterations 15
Cbc0038I Pass 15: suminf. 12.26858 (62) obj. 454.594 iterations 9
Cbc0038I Pass 16: suminf. 12.59845 (64) obj. 454.594 iterations 7
Cbc0038I Pass 17: suminf. 12.59845 (64) obj. 454.594 iterations 5
Cbc0038I Pass 18: suminf. 16.19725 (74) obj. 487.595 iterations 17
Cbc0038I Pass 19: suminf. 12.66110 (61) obj. 487.595 iterations 10
Cbc0038I Pass 20: suminf. 15.78065 (85) obj. 454.594 iterations 25
Cbc0038I Pass 21: suminf. 12.49605 (63) obj. 454.594 iterations 18
Cbc0038I Pass 22: suminf. 12.49605 (63) obj. 454.594 iterations 2
Cbc0038I Pass 23: suminf. 14.74148 (72) obj. 454.594 iterations 9
Cbc0038I Pass 24: suminf. 12.85834 (63) obj. 454.594 iterations 7
Cbc0038I Pass 25: suminf. 14.77824 (70) obj. 454.594 iterations 14
Cbc0038I Pass 26: suminf. 12.03422 (61) obj. 454.594 iterations 12
Cbc0038I Pass 27: suminf. 12.03422 (61) obj. 454.594 iterations 2
Cbc0038I Pass 28: suminf. 12.51226 (62) obj. 454.594 iterations 8
Cbc0038I Pass 29: suminf. 12.51226 (62) obj. 454.594 iterations 5
Cbc0038I Pass 30: suminf. 21.85301 (81) obj. 454.594 iterations 10
Cbc0038I Pass 31: suminf. 12.03422 (61) obj. 454.594 iterations 10
Cbc0038I Pass 32: suminf. 12.03422 (61) obj. 454.594 iterations 2
Cbc0038I Pass 33: suminf. 14.74148 (72) obj. 454.594 iterations 10
Cbc0038I Pass 34: suminf. 12.85834 (63) obj. 454.594 iterations 6
Cbc0038I Pass 35: suminf. 14.41276 (72) obj. 454.594 iterations 7
Cbc0038I Pass 36: suminf. 12.84212 (64) obj. 454.594 iterations 6
Cbc0038I Pass 37: suminf. 15.02805 (72) obj. 454.594 iterations 10
Cbc0038I Pass 38: suminf. 20.44714 (95) obj. 925.549 iterations 126
Cbc0038I Pass 39: suminf. 16.41279 (71) obj. 983.301 iterations 62
Cbc0038I Pass 40: suminf. 13.27421 (65) obj. 973.911 iterations 30
Cbc0038I Pass 41: suminf. 9.79846 (50) obj. 973.74 iterations 3
Cbc0038I Pass 42: suminf. 12.51723 (48) obj. 693.605 iterations 18
Cbc0038I Pass 43: suminf. 12.70067 (53) obj. 713.45 iterations 15
Cbc0038I Pass 44: suminf. 11.23859 (51) obj. 713.45 iterations 14
Cbc0038I Pass 45: suminf. 11.45577 (50) obj. 713.45 iterations 8
Cbc0038I Pass 46: suminf. 15.45592 (58) obj. 717.459 iterations 27
Cbc0038I Pass 47: suminf. 14.36702 (56) obj. 794.134 iterations 18
Cbc0038I Pass 48: suminf. 13.47185 (54) obj. 794.134 iterations 3
Cbc0038I Pass 49: suminf. 15.50911 (58) obj. 717.459 iterations 21
Cbc0038I Pass 50: suminf. 14.37117 (56) obj. 798.021 iterations 18
Cbc0038I Pass 51: suminf. 13.47600 (54) obj. 798.021 iterations 3
Cbc0038I Pass 52: suminf. 22.68284 (84) obj. 846.461 iterations 128
Cbc0038I Pass 53: suminf. 18.57079 (72) obj. 887.407 iterations 59
Cbc0038I Pass 54: suminf. 18.43260 (72) obj. 862.071 iterations 21
Cbc0038I Pass 55: suminf. 19.74845 (78) obj. 873.792 iterations 12
Cbc0038I Pass 56: suminf. 19.06775 (69) obj. 863.075 iterations 15
Cbc0038I Pass 57: suminf. 13.50916 (52) obj. 891.173 iterations 10
Cbc0038I Pass 58: suminf. 22.87530 (75) obj. 988.677 iterations 20
Cbc0038I Pass 59: suminf. 18.28259 (67) obj. 988.677 iterations 7
Cbc0038I Pass 60: suminf. 13.99150 (58) obj. 1094.75 iterations 18
Cbc0038I Pass 61: suminf. 15.40796 (61) obj. 1267.08 iterations 18
Cbc0038I Pass 62: suminf. 7.88882 (46) obj. 1340.87 iterations 5
Cbc0038I Pass 63: suminf. 13.54525 (55) obj. 1196.52 iterations 16
Cbc0038I Pass 64: suminf. 8.41569 (57) obj. 1295.73 iterations 19
Cbc0038I Pass 65: suminf. 9.96606 (64) obj. 1295.73 iterations 15
Cbc0038I Pass 66: suminf. 10.37178 (62) obj. 1295.73 iterations 3
Cbc0038I Pass 67: suminf. 11.56677 (60) obj. 1295.73 iterations 17
Cbc0038I Pass 68: suminf. 11.55920 (62) obj. 1295.73 iterations 8
Cbc0038I Pass 69: suminf. 11.01049 (70) obj. 1295.73 iterations 11
Cbc0038I Pass 70: suminf. 7.48935 (55) obj. 1295.73 iterations 7
Cbc0038I Pass 71: suminf. 10.84838 (58) obj. 1297.3 iterations 14
Cbc0038I Pass 72: suminf. 10.91403 (60) obj. 1295.73 iterations 1
Cbc0038I Pass 73: suminf. 8.88900 (72) obj. 1268.52 iterations 8
Cbc0038I Pass 74: suminf. 8.83585 (75) obj. 1312.12 iterations 5
Cbc0038I Pass 75: suminf. 5.77727 (73) obj. 1348.14 iterations 11
Cbc0038I Pass 76: suminf. 2.40838 (45) obj. 1351.23 iterations 30
Cbc0038I Pass 77: suminf. 2.50573 (46) obj. 1350.17 iterations 5
Cbc0038I Pass 78: suminf. 3.43292 (43) obj. 1178.68 iterations 25
Cbc0038I Pass 79: suminf. 1.68753 (47) obj. 1178.68 iterations 25
Cbc0038I Pass 80: suminf. 10.49116 (53) obj. 1178.46 iterations 30
Cbc0038I Pass 81: suminf. 5.19409 (53) obj. 1275.35 iterations 41
Cbc0038I Pass 82: suminf. 4.34798 (52) obj. 1275.35 iterations 5
Cbc0038I Pass 83: suminf. 2.30426 (42) obj. 1254.5 iterations 31
Cbc0038I Pass 84: suminf. 1.66459 (45) obj. 1275.35 iterations 26
Cbc0038I Pass 85: suminf. 9.65069 (55) obj. 1178.46 iterations 29
Cbc0038I Pass 86: suminf. 6.36467 (54) obj. 1222.02 iterations 27
Cbc0038I Pass 87: suminf. 2.13080 (48) obj. 1275.35 iterations 24
Cbc0038I Pass 88: suminf. 2.13080 (48) obj. 1275.35 iterations 0
Cbc0038I Pass 89: suminf. 9.97728 (55) obj. 1178.46 iterations 35
Cbc0038I Pass 90: suminf. 7.67562 (57) obj. 1222.02 iterations 36
Cbc0038I Pass 91: suminf. 3.16010 (50) obj. 1275.35 iterations 19
Cbc0038I Pass 92: suminf. 2.38080 (50) obj. 1275.35 iterations 6
Cbc0038I Pass 93: suminf. 3.74856 (53) obj. 1243.41 iterations 38
Cbc0038I Pass 94: suminf. 1.71964 (46) obj. 1275.35 iterations 38
Cbc0038I Pass 95: suminf. 2.34377 (42) obj. 1254.5 iterations 21
Cbc0038I Pass 96: suminf. 1.53098 (39) obj. 1275.35 iterations 21
Cbc0038I Pass 97: suminf. 9.55188 (55) obj. 1178.46 iterations 31
Cbc0038I Pass 98: suminf. 7.80986 (51) obj. 1222.02 iterations 26
Cbc0038I Pass 99: suminf. 2.83396 (43) obj. 1178.68 iterations 43
Cbc0038I Pass 100: suminf. 24.56681 (92) obj. 858.79 iterations 124
Cbc0038I No solution found this major pass
Cbc0038I Before mini branch and bound, 7605 integers at bound fixed and 0 continuous
Cbc0038I Full problem 491 rows 8028 columns, reduced to 366 rows 423 columns
Cbc0038I Mini branch and bound did not improve solution (1.40 seconds)
Cbc0038I After 1.40 seconds - Feasibility pump exiting - took 0.90 seconds
Cbc0031I 59 added rows had average density of 233.55932
Cbc0013I At root node, 59 cuts changed objective from 43.335573 to 86.107549 in 20 passes
Cbc0014I Cut generator 0 (Probing) - 283 row cuts average 172.1 elements, 0 column cuts (0 active) in 1.356 seconds - new frequency is 1
Cbc0014I Cut generator 1 (Gomory) - 15 row cuts average 743.3 elements, 0 column cuts (0 active) in 0.314 seconds - new frequency is -100
Cbc0014I Cut generator 2 (Knapsack) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.049 seconds - new frequency is -100
Cbc0014I Cut generator 3 (Clique) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.007 seconds - new frequency is -100
Cbc0014I Cut generator 4 (MixedIntegerRounding2) - 50 row cuts average 224.3 elements, 0 column cuts (0 active) in 0.088 seconds - new frequency is 1
Cbc0014I Cut generator 5 (FlowCover) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.104 seconds - new frequency is -100
Cbc0014I Cut generator 6 (TwoMirCuts) - 78 row cuts average 236.0 elements, 0 column cuts (0 active) in 0.179 seconds - new frequency is 1
Cbc0027I Exiting on user event
Cbc0005I Partial search - best objective 1e+50 (best possible 86.107549), took 5432 iterations and 0 nodes (5.24 seconds)
----- Mail original -----
De: "Fausto Richetti Blanco" <fausto.blanco at gmail.com>
À: "ycollette nospam" <ycollette.nospam at free.fr>
Cc: "cbc" <cbc at list.coin-or.org>
Envoyé: Lundi 26 Juin 2017 16:35:11
Objet: Re: [Cbc] Convergence problem with miplib2010/30n20b8
CLP:
Problem 30n20b8 has 576 rows, 18380 columns and 109706 elements
CBS:
Cbc0038I Full problem 491 rows 8028 columns, reduced to 366 rows 423 columns
Are you sure you're comparing the same problem?
On Mon, Jun 26, 2017 at 11:30 AM, < ycollette.nospam at free.fr > wrote:
At the beginning of the cbc run, I got this in the logs:
Cbc0038I Full problem 491 rows 8028 columns, reduced to 366 rows 423 columns
Cbc0038I Mini branch and bound did not improve solution (1.51 seconds)
Cbc0038I After 1.51 seconds - Feasibility pump exiting - took 0.98 seconds
Cbc0031I 59 added rows had average density of 233.55932
Cbc0013I At root node, 59 cuts changed objective from 43.335573 to 86.107549 in 20 passes
Cbc0014I Cut generator 0 (Probing) - 283 row cuts average 172.1 elements, 0 column cuts (0 active) in 1.322 seconds - new frequency is 1
Cbc0014I Cut generator 1 (Gomory) - 15 row cuts average 743.3 elements, 0 column cuts (0 active) in 0.283 seconds - new frequency is -100
Cbc0014I Cut generator 2 (Knapsack) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.045 seconds - new frequency is -100
Cbc0014I Cut generator 3 (Clique) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.005 seconds - new frequency is -100
Cbc0014I Cut generator 4 (MixedIntegerRounding2) - 50 row cuts average 224.3 elements, 0 column cuts (0 active) in 0.075 seconds - new frequency is 1
Cbc0014I Cut generator 5 (FlowCover) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.092 seconds - new frequency is -100
Cbc0014I Cut generator 6 (TwoMirCuts) - 78 row cuts average 236.0 elements, 0 column cuts (0 active) in 0.169 seconds - new frequency is 1
----- Mail original -----
De: "ycollette nospam" < ycollette.nospam at free.fr >
À: "cbc" < cbc at list.coin-or.org >
Envoyé: Lundi 26 Juin 2017 16:28:31
Objet: [Cbc] Convergence problem with miplib2010/30n20b8
Hello,
I am trying to run somes tests from miplib2010. And I meet some strange behavior.
If I run clp on 30n20b8.mps without specific options, it converges quickly to a solution:
At line 1 NAME 30n20b8
At line 2 ROWS
At line 580 COLUMNS
At line 110291 RHS
At line 110322 BOUNDS
At line 128761 ENDATA
Problem 30n20b8 has 576 rows, 18380 columns and 109706 elements
Model was imported from /home/artelys/repository/coin/Cbc/build/Dependencies/.//MIPLIB2000/src/EP_MIPLIB2000/instances/miplib2010/30n20b8.mps.gz in 0.114319 seconds
Presolve 493 (-83) rows, 11093 (-7287) columns and 63118 (-46588) elements
Perturbing problem by 0.001%%of 301.52267 - largest nonzero change 0.00028965583 ( 9.6064362e-05%%) - largest zero change 0.00028962251
0 Obj 0.041886881 Primal inf 253.60538 (88)
78 Obj 0.044696222 Primal inf 359.4158 (159)
142 Obj 0.04542365 Primal inf 105.42604 (119)
214 Obj 0.045885186 Primal inf 83.292978 (114)
298 Obj 0.046155092 Primal inf 32.89186 (74)
380 Obj 0.048508765 Primal inf 87.130897 (64)
464 Obj 0.057466585 Primal inf 99.796642 (62)
548 Obj 0.068410705 Primal inf 276.03475 (64)
632 Obj 0.077664609 Primal inf 167.63095 (63)
716 Obj 0.08533722 Primal inf 123.90711 (47)
800 Obj 0.093453993 Primal inf 94.340415 (35)
884 Obj 1.079625 Primal inf 0.56385768 (23)
950 Obj 1.669254
Optimal - objective value 1.5664076
After Postsolve, objective 1.5664076, infeasibilities - dual 0 (0), primal 0 (0)
Optimal objective 1.566407646 - 950 iterations time 0.112, Presolve 0.03
Now, If I run cbc on this problem, it never stops.
An example of the log I've got:
Cbc0010I After 91600 nodes, 675 on tree, 1e+50 best solution, best possible 202 (1278.41 seconds)
Cbc0010I After 91700 nodes, 626 on tree, 1e+50 best solution, best possible 202 (1279.79 seconds)
Cbc0010I After 91800 nodes, 724 on tree, 1e+50 best solution, best possible 202 (1281.46 seconds)
Cbc0010I After 91900 nodes, 805 on tree, 1e+50 best solution, best possible 202 (1283.06 seconds)
Cbc0010I After 92000 nodes, 709 on tree, 1e+50 best solution, best possible 202 (1284.15 seconds)
I feel the number of best solutions is quite strange: 1e+50 (this number never changes).
I performed these tests on the trunk version of cbc. I will try the same test on an older version of cbc.
Best regards,
YC
_______________________________________________
Cbc mailing list
Cbc at list.coin-or.org
https://urldefense.proofpoint.com/v2/url?u=https-3A__list.coin-2Dor.org_mailman_listinfo_cbc&d=DwICAg&c=Ngd-ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=kY-tTJAFuHScYZHjojaaKVZZOEYVVkPpGiWUPr3h80U&m=EqDbNlOmPhOlal3SI7C5XWuE8KhPe3sA5awi8py-lBA&s=o5HK9S3C5JZo5CHwNMumDoTjHXpYF-W3LjyehdeuF7w&e=
_______________________________________________
Cbc mailing list
Cbc at list.coin-or.org
https://urldefense.proofpoint.com/v2/url?u=https-3A__list.coin-2Dor.org_mailman_listinfo_cbc&d=DwIGaQ&c=Ngd-ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=QLQl3jHZx6hPNKTb0I9pud73uBDZjSYyVOorevkAFrU&m=oRCE3ZWfhw5CzXVvq3XW5L7Hm5bKjiC3gT_F_qL8yfw&s=zHJEZcVYlhOOruUvsI8rMvBRloUvGYesE99_H866lr4&e=
More information about the Cbc
mailing list