Show description

Ii. k is odd, l Tf = 3k/2 +2i for some i ∈ such that l gT ≥ k. + , and ∃g ∈ C ∩(E \ T \ f ) 342 P. Bauer et al. In this subcase, we know that wlTf = (5−k)/2 and we = 2−leT ∀e ∈ (C\ f )∩(E\T ). 3) implies that (2 − leT ) ≥ 3 − (5 − k)/2 + e∈(C\ f )∩(E\T ) Using the fact that e∈T xe. 16) and applying Lemma 3, we get that |P Tf ∩ C| − |PeT \ P Tf | ≥ k − m + 3. e∈(C\ f )∩(E\T ) Therefore, |C| ≥ |P Tf ∩ C| + m ≥ k + 3 + |PeT \ P Tf | ≥ k + 3, e∈E\T \ f which gives the contradiction |C| > k. We have shown that in all possible cases, if the coefficient of an edge e ∈ E \ T in the original tree inequality cannot be improved to wlTe , then there is a contradiction.

G is on the boundary of two interior faces, so g is also on some PeT for e ∈ (C \ f ) ∩ (E \ T ). Fig. 1. An embedding of C and PeT Now, suppose for a contradiction that the coefficient for edge f ∈ E \ T cannot be increased to wlTf , this implies by Lemma 2 that 2 − l Tf + 2 − z f ≤ wlTf − 1. 1) Since edge f must be in an optimal solution x to problem (CIP), we have zf = x e + 2 − l Tf + e∈T we x e . 2) gives that wlTf + we x e ≥ 3 − e∈(E\T )\ f xe. 3) e∈T Let C be the optimal circuit defined by incidence vector x.

Cut statistics for modified WGPLIB instances Name k Total Cuts Max Loaded Parity DCE Cut 2For Simple Forest Path Tree K-Part bayg29m47 bayg29m47 bayg29m47 bayg29m50 bayg29m50 bayg29m50 bayg29m120 bayg29m120 bayg29m120 berlin52m50 berlin52m50 berlin52m50 berlin52m200 berlin52m200 berlin52m200 berlin52m500 berlin52m500 berlin52m500 brazil58m200 brazil58m200 brazil58m200 brazil58m2000 brazil58m2000 brazil58m2000 brazil58m500 brazil58m500 brazil58m500 cn100am100 cn100am100 cn100am100 cn100am30 cn100am30 cn100am30 cn100bm20 cn100bm20 cn100bm20 cn100bm40 cn100bm40 cn100bm40 dlo49m700 dlo49m700 dlo49m700 dlo49m1000 dlo49m1000 dlo49m1000 dlo49m2000 dlo49m2000 dlo49m2000 dlo61m2000 dlo61m2000 dlo61m2000 4 9 14 5 10 16 9 19 29 4 8 12 12 25 38 17 34 52 4 8 12 19 38 58 16 32 48 33 66 100 29 58 87 11 22 33 31 62 94 3 6 10 6 13 20 16 32 49 19 38 58 75 223 193 198 381 230 537 382 158 29 201 118 109 325 663 443 468 65 83 230 479 1068 5477 318 784 1075 1016 11913 11021 9434 13700 16280 1446 5079 4909 2220 2532 4165 1234 62 67 92 67 721 532 495 15795 202 2212 3300 502 75 223 193 198 381 230 537 382 158 29 201 118 109 325 663 443 468 65 83 230 479 1068 1857 318 784 1075 1016 4271 4028 1950 5786 4087 1446 1672 1997 2132 2471 2842 1234 62 67 92 67 721 532 495 1394 202 1366 1424 502 17 16 20 19 17 22 21 20 2 10 10 13 14 24 18 19 14 1 17 18 23 38 61 2 29 28 19 79 101 6 61 112 60 71 59 64 53 94 43 18 17 22 17 41 36 42 210 2 62 76 5 11 78 90 53 149 113 173 200 132 6 90 54 50 176 392 265 290 50 24 108 260 636 3485 264 422 733 697 7218 8112 7807 8669 12463 912 2750 2880 1319 1501 2779 811 4 21 36 21 375 321 296 11200 135 1193 2303 409 34 99 75 62 157 85 182 121 20 8 68 40 33 111 227 117 116 11 23 72 167 359 1120 40 289 271 269 4115 2614 317 4164 3430 427 1538 1700 776 773 1099 332 27 22 30 22 235 149 132 2565 51 489 556 62 0 0 0 0 1 0 0 3 2 0 0 3 4 4 11 8 3 2 0 0 0 2 38 8 1 6 17 0 13 355 0 5 6 0 0 0 2 33 25 0 0 0 0 10 7 6 129 11 13 18 16 0 0 0 0 1 0 2 4 0 0 2 1 1 4 5 1 3 0 0 1 0 2 244 0 0 17 1 26 26 872 8 24 31 3 20 27 21 94 14 0 0 0 0 22 6 4 550 0 44 10 3 0 11 0 27 22 0 88 20 0 0 10 0 0 0 0 17 34 0 10 0 0 0 419 0 5 0 0 0 2 0 1 7 0 55 46 0 140 16 0 7 0 0 0 18 0 1 722 0 366 271 0 6 10 6 12 19 6 23 11 2 3 15 5 4 6 10 15 8 1 9 10 13 25 110 4 19 19 13 150 150 77 190 236 10 169 90 30 33 49 9 6 4 3 4 19 11 14 386 3 44 66 7 7 9 2 25 15 4 48 3 0 2 6 2 3 0 0 1 0 0 0 21 16 6 0 0 19 1 0 325 3 0 607 3 0 493 114 4 9 1 0 0 3 1 3 1 2 0 33 0 1 0 0 A branch and cut approach to the cardinality constrained circuit problem 347 Name k Total Cuts Max Loaded Parity DCE Cut 2For Simple Forest Path Tree K-Part dlo61m5000 dlo61m5000 dlo61m5000 eil76m6 eil76m6 eil76m6 eil76m15 eil76m15 eil76m15 eil76m25 eil76m25 eil76m25 kroA100m200 kroA100m200 kroA100m200 kroA100m300 kroA100m300 kroA100m300 kroC100m200 kroC100m200 kroC100m200 kroE100m400 kroE100m400 kroE100m400 pr76m1500 pr76m1500 pr76m1500 pr76m9000 pr76m9000 pr76m9000 rat99m12 rat99m12 rat99m12 st70m10 st70m10 st70m10 st70m40 st70m40 st70m40 20 40 61 13 26 39 24 48 72 25 50 76 16 32 48 31 62 93 26 52 78 32 64 97 18 36 54 25 50 76 24 48 73 14 28 42 23 46 70 1155 1654 627 675 1662 829 1936 2029 292 1312 1111 181 17699 10492 4967 19009 6421 1411 8575 5903 4637 6257 15054 938 3736 1738 593 8256 462 10249 7590 3545 4637 1486 2856 1146 22963 1884 452 1155 1466 627 675 1662 829 1402 1767 292 1312 1111 181 4670 4406 3168 4979 3071 1411 4808 4622 3676 3913 4194 938 1248 956 593 1194 462 1368 2234 2532 3184 1486 1892 1146 2203 1669 452 53 62 1 33 38 47 49 56 6 38 56 0 61 62 65 67 68 38 58 57 60 67 85 25 68 71 46 106 50 0 80 72 79 44 53 56 145 53 0 618 1155 570 300 836 423 921 1268 185 663 609 147 8246 6466 3070 11567 4298 948 4715 3630 2709 3877 9799 649 1749 583 330 3784 244 8857 4297 2217 3143 705 1592 658 13551 1076 362 313 342 22 276 672 344 698 606 96 547 349 27 7530 3717 1766 6734 1843 342 3509 2142 1816 1770 3853 225 1598 424 195 3168 153 212 2999 1150 1209 575 1102 397 7867 395 72 3 16 24 0 10 2 10 23 2 3 18 6 0 0 0 1 15 28 0 0 0 18 44 18 0 1 7 1 7 466 6 8 47 0 3 8 54 28 11 20 30 4 0 5 3 19 39 1 1 14 0 18 8 0 77 10 43 3 7 1 163 50 14 7 7 10 13 3 562 41 26 84 0 6 13 194 42 3 126 18 0 28 72 0 197 7 0 34 52 0 22 36 0 129 100 0 27 0 0 277 1051 0 125 634 0 939 0 0 8 23 0 89 46 0 519 262 0 21 31 6 15 28 10 41 30 2 21 13 1 285 153 64 258 86 12 110 66 51 74 171 7 105 17 5 242 5 152 125 49 75 32 48 13 441 26 4 1 0 0 23 1 0 1 0 0 5 0 0 1537 50 2 176 1 0 153 1 0 11 1 0 84 1 0 3 0 0 34 0 0 41 6 1 192 2 0 Acknowledgements.