[Cbc] Convergence problem with miplib2010/30n20b8
ycollette.nospam at free.fr
ycollette.nospam at free.fr
Mon Jun 26 10:46:49 EDT 2017
I know the differences between MIP and LP. But I remember that with an old version of cbc it worked before the timeout of 300 sec I fixed for this test.
----- Mail original -----
De: "Stefan Vigerske" <stefan at math.hu-berlin.de>
À: cbc at list.coin-or.org
Envoyé: Lundi 26 Juin 2017 16:44:34
Objet: Re: [Cbc] Convergence problem with miplib2010/30n20b8
Maybe I missed some recent breakthrough in the world of optimization,
but just because Clp is able to solve the LP relaxation of 30n20b8
quickly, one cannot be sure that Cbc will quickly find a feasible
solution to the MIP.
On 06/26/2017 04:39 PM, ycollette.nospam at free.fr wrote:
> 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=
>
>
> _______________________________________________
> 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=BRcuJnQr5NAzU29t80hk2rsLc4vrlRySBDabuq0O1ZI&m=FAig13bHGHcoLArQxx2GnWpxX-0oBDkbbxHBj1RT_WQ&s=W4_gzRqdfHJ-Gz2ToEdQO0HTeLnCe1GsudjIWXAikCo&e=
>
--
https://urldefense.proofpoint.com/v2/url?u=http-3A__www.gams.com_-7Estefan&d=DwIGaQ&c=Ngd-ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=kY-tTJAFuHScYZHjojaaKVZZOEYVVkPpGiWUPr3h80U&m=kwhZTaz4xtoeDVYnyTu5fjfNUuM8pX9BkzNqaqRsX9Y&s=l2wqzn-a8_RpNtYu5PiSX7iIs4VkQjXh2tRoUx2azZM&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=kY-tTJAFuHScYZHjojaaKVZZOEYVVkPpGiWUPr3h80U&m=kwhZTaz4xtoeDVYnyTu5fjfNUuM8pX9BkzNqaqRsX9Y&s=UDDRax2ZXVWiGQUftNQi_TThA-S_BLez_6-k4BcCNvY&e=
More information about the Cbc
mailing list