ILOG CPLEX 11.110, licensed to "arizona-tempe, az", options: e m b q p=8 FPgen-t 06/06/2005 - Bertacco, Fischetti, Lodi 09/16/2005 - Achterberg, Berthold applying MIP presolve... Selected objective sense: MINIMIZE Selected objective name: obj Selected RHS name: rhs Selected bound name: bnd Tried aggregator 2 times. MIP Presolve eliminated 1243 rows and 1127 columns. MIP Presolve modified 1 coefficients. Aggregator did 365 substitutions. Reduced MIP has 671 rows, 1971 columns, and 8489 nonzeros. presolving objective offset = 0 (restat: 0) Problem: bench/ns894788.mps Max iter Stage 1: 10000 Max iter Stage 2: 2000 Min change: 20 Initial Presolve: Yes Imported 671 rows and 1971 columns Objective sense: Minimize Problem is MIP: Yes Initial Algorithm: Auto 1971 integer variables (1971 of which are binary and 0 are general integer) 0 continuous variables Solving relaxed problem...0- 0 -1 0 6.3048 53.9431 done obj=6.3048 + 0 = 6.3048 Rounding solution...done Stage 1... improved distance by 0percent 1- 1 61.9018 0 6.30933 52.1237 improved distance by 0.733485percent 1- 2 45.4041 0 6.33761 44.7706 1- 3 46.7617 0 6.36585 42.7467 improved distance by 0.929699percent 1- 4 42.2121 0 6.49371 38.5844 1- 5 59.0914 0 6.54756 38.4095 improved distance by 0.967741percent 1- 6 40.8504 0 6.51001 37.6868 improved distance by 0.8315percent 1- 7 33.9671 0 6.58591 32.2982 improved distance by 0.889117percent 1- 8 30.2007 0 6.68923 28.6941 improved distance by 0.675897percent 1- 9 20.4126 0 7 16.8478 improved distance by 0.706674percent 1- 10 14.425 0 7 11.6606 improved distance by 0.758576percent 1- 11 10.9425 0 7 10.9425 1- 12 14.9878 0 7 11.7626 1- 13 11.5185 0 7 11.5163 1- 14 11.4516 0 7 11.4516 1- 15 23.47 0 7 12.3419 1- 16 15.7678 0 7 12.3811 1- 17 12.5121 0 7 12.0577 1- 18 13.8458 0 7 12.1038 1- 19 11.9007 0 7 11.8496 s iter delta rst obj fractionality incumbent 1- 20 11.729 0 7 11.5641 1- 21 29.8788 0 7 20.5166 1- 22 20.8611 0 7 19.1389 1- 23 21.2468 0 7 19.3247 1- 24 22.0524 0 7 20.6214 1- 25 21.7952 0 7 20.012 1- 26 17.5854 0 7 16.3228 1- 27 18.8949 0 7 14.3154 1- 28 19.4205 0 7 13.3523 1- 29 63.3 0 7 23.3 1- 30 17.825 0 7 10.075 improved distance by 0.863678percent 1- 31 9.45077 0 7 9.34842 1- 32 10.9772 0 7 9.98756 1- 33 9.70918 0 7 9.62347 improved distance by 0.981144percent 1- 34 9.27257 0 7 9.21188 improved distance by 0.986803percent 1- 35 9.1502 0 7 9.1502 1- 36 11.0803 0 7 9.19611 improved distance by 0.945142percent 1- 37 8.64824 0 7 8.64824 1- 38 23.5393 0 7 10.4719 improved distance by 0.877749percent 1- 39 7.59098 0 7 6.17915 s iter delta rst obj fractionality incumbent improved distance by 0.798452percent 1- 40 6.06103 0 7 6.00325 improved distance by 0.987696percent 1- 41 5.98646 0 7 5.98646 1- 42 71.5032 1 7 6.65942 1- 43 6.11551 1 7 6.0994 1- 44 8.69036 1 7 6.12288 1- 45 6.05417 1 7 6.00841 1- 46 19.2504 1 7 6.92486 1- 47 6.06103 1 7 6.00325 1- 48 9.34453 1 7 6.25121 1- 49 8.32931 1 7 6.41897 1- 50 10.8514 1 7 6.31818 1- 51 60.5066 2 7 6.25322 1- 52 61.3641 3 7 7.42074 1- 53 7.05406 3 7 6.57662 1- 54 6.05752 3 7 6.05752 1- 55 8.69036 3 7 6.12288 1- 56 6.05417 3 7 6.00366 1- 57 50.2549 4 7 6.2815 1- 58 11.4899 4 7 9.71046 1- 59 7.75548 4 7 6.80259 s iter delta rst obj fractionality incumbent 1- 60 9.11013 4 7 6.43216 1- 61 70.643 5 7 6.57778 1- 62 13.5073 5 7 6.27412 1- 63 51.6135 6 7 6.13707 1- 64 6.97959 6 7 6.05068 1- 65 59.6479 7 7 6.18145 1- 66 5.98753 7 7 5.98753 1- 67 22.5164 7 7 9.19056 1- 68 6.58127 7 7 5.99087 improved distance by 1percent 1- 69 5.98646 7 7 5.98646 1- 70 6.06103 7 7 6.00325 1- 71 70.9451 8 7 6.25 1- 72 73.5191 9 7 6.40056 1- 73 58.3961 10 7 6.0556 1- 74 10.0605 10 7 6.29675 1- 75 6.11551 10 7 6.10764 1- 76 60.0499 11 7 6.10288 1- 77 65.8614 12 7 7.4498 1- 78 6.94548 12 7 6.18513 1- 79 6.11775 12 7 6.00147 s iter delta rst obj fractionality incumbent 1- 80 59.6735 13 7 6.59165 1- 81 70.2861 14 7 6.25017 1- 82 74.1827 15 7 6.20298 1- 83 59.6816 16 7 6.07286 1- 84 74.8061 17 7 7.35994 1- 85 8.1824 17 7 6.16967 1- 86 59.8667 18 7 6.25964 1- 87 68.4913 19 7 6.27726 1- 88 68.7089 20 7 6.1531 1- 89 55.4282 21 7 6.07169 1- 90 76.704 22 7 6.11514 1- 91 59.7681 23 7 6.10714 1- 92 64.4591 24 7 6.19556 1- 93 6.0563 24 7 6.0049 1- 94 57.5007 25 7 6.25418 1- 95 62.3036 26 7 6.18693 1- 96 72.1391 27 7 6.35157 1- 97 66.4189 28 7 6.29294 1- 98 68.0327 29 7 6.83152 1- 99 73.4294 30 7 6.43263 s iter delta rst obj fractionality incumbent 1- 100 10.3445 30 7 6.30235 1- 101 78.1814 31 7 6.19992 1- 102 59.9273 32 7 6.09235 1- 103 68.618 33 7 6.37303 1- 104 81.787 34 7 6.26491 1- 105 63.9361 35 7 6.48238 1- 106 8.1824 35 7 6.16967 1- 107 70.504 36 7 6.69201 1- 108 72.7469 37 7 6.10324 1- 109 62.7636 38 7 6.75025 1- 110 73.8429 39 7 6.15796 1- 111 61.6229 40 7 6.41151 1- 112 64.6931 41 7 6.73558 1- 113 73.5672 42 7 6.70149 Too many iteration without 10% improvement Total stage 1 restarts: 42 Stage 2... Using best point from iter: 69 2- 114 6.06225 42 7 6.00325 2- 115 6.05525 42 7 6.00366 2- 116 12.0755 42 7 6.36028 2- 117 6.06192 42 7 6.00325 2- 118 5.98725 42 7 5.98646 2- 119 25.0543 43 7 6.01001 s iter delta rst obj fractionality incumbent 2- 120 8.69101 43 7 6.12288 2- 121 7.05462 43 7 6.57662 2- 122 45.6906 44 7 6.12163 2- 123 53.6849 45 7 6.12936 2- 124 87.6988 46 7 6.14078 2- 125 24.5784 46 7 6.48427 2- 126 10.0608 46 7 6.22732 2- 127 75.9756 47 7 6.25661 2- 128 6.09778 47 7 6.03214 2- 129 78.8256 48 7 6.37764 2- 130 81.964 49 7 6.14861 2- 131 98.702 50 7 6.61185 2- 132 90.4689 51 7 6.87633 2- 133 5.9877 51 7 5.98753 2- 134 100.694 52 7 6.22855 2- 135 115.945 53 7 8.67409 2- 136 8.22982 53 7 7.31859 2- 137 100.376 54 7 7.01964 2- 138 6.67377 54 7 6.11615 2- 139 90.7409 55 7 6.38812 s iter delta rst obj fractionality incumbent 2- 140 6.11782 55 7 6.00147 2- 141 8.32938 55 7 6.41897 2- 142 12.6469 55 7 6.33585 2- 143 9.11018 55 7 6.43216 2- 144 68.3074 56 7 6.34064 2- 145 98.8432 57 7 6.29412 2- 146 105.175 58 7 6.20595 2- 147 92.7561 59 7 6.24827 2- 148 103.777 60 7 6.24691 2- 149 97.5116 61 7 6.19277 2- 150 15.4877 61 7 6.03081 2- 151 104.44 62 7 6.18545 2- 152 92.322 63 7 6.70596 2- 153 94.6314 64 7 6.99654 2- 154 108.612 65 7 6.59939 2- 155 83.7185 66 7 6.15063 2- 156 95.6198 67 7 6.48021 2- 157 7.76691 67 7 7.73587 2- 158 22.7407 67 7 8.62067 2- 159 7.16641 67 7 6.97493 s iter delta rst obj fractionality incumbent 2- 160 7.27898 67 7 7.26658 2- 161 15.6057 67 7 9.5874 2- 162 9.23132 67 7 8.38392 2- 163 9.25361 67 7 7.50393 2- 164 50.0834 68 7 7.2753 2- 165 179.428 68 7 29.39 2- 166 14.617 68 7 10.5422 2- 167 18.0146 68 7 7.70267 2- 168 50.5687 69 7 7.60752 2- 169 76.5814 69 7 12.7674 2- 170 17.3409 69 7 10.9091 2- 171 13.8849 69 7 10.0369 2- 172 10.9021 69 7 9.69578 2- 173 23.9143 69 7 10.3214 2- 174 19.1637 69 7 8.93363 2- 175 7.81679 69 7 7.46741 2- 176 39.0744 70 7 7.21932 2- 177 61.9049 71 7 7.20961 2- 178 75.2364 72 7 7.67925 2- 179 10.3381 72 7 6.9679 s iter delta rst obj fractionality incumbent 2- 180 7.44694 72 7 6.55141 2- 181 6.48581 72 7 6.48581 2- 182 17.0197 72 7 6.68379 2- 183 64.6355 73 7 6.24081 2- 184 81.6173 74 7 6.31699 2- 185 104.925 75 7 6.2472 2- 186 93.6803 76 7 7.11475 2- 187 94.9741 77 7 7.42709 2- 188 101.727 78 7 6.23694 2- 189 103.811 79 7 6.23216 2- 190 43.2521 79 7 6.73077 2- 191 93.7408 80 7 6.26034 2- 192 6.97959 80 7 6.05068 2- 193 83.7231 81 7 6.17827 2- 194 96.8839 82 7 6.13176 2- 195 104.523 83 7 7.36804 2- 196 6.91741 83 7 6.70378 2- 197 16.1099 83 7 9.90814 2- 198 13.8039 83 7 7.18337 2- 199 10.0334 83 7 6.78028 s iter delta rst obj fractionality incumbent 2- 200 7.25819 83 7 6.55076 2- 201 16.9542 83 7 6.5971 2- 202 61.834 84 7 6.03191 2- 203 80.9587 85 7 6.53713 2- 204 15.3131 85 7 6.51963 2- 205 88.8487 86 7 6.21482 2- 206 6.05752 86 7 6.05752 2- 207 100.267 87 7 6.51659 2- 208 99.4771 88 7 6.38226 2- 209 101.549 89 7 6.26006 2- 210 95.6413 90 7 6.62451 2- 211 108.607 91 7 6.30624 2- 212 95.0293 92 7 6.71451 2- 213 99.6026 93 7 6.48599 2- 214 96.7778 94 7 6.27778 2- 215 103.177 95 7 6.24236 2- 216 103.777 96 7 6.3043 2- 217 98.3836 97 7 6.93211 2- 218 102.782 98 7 6.23998 2- 219 103.205 99 7 6.38698 s iter delta rst obj fractionality incumbent 2- 220 87.914 100 7 6.0785 2- 221 97.8686 101 7 6.25241 2- 222 98.0813 102 7 6.1382 2- 223 84.6436 103 7 6.26232 2- 224 14.6518 103 7 6.09886 2- 225 107.961 104 7 8.12244 2- 226 92.9443 105 7 6.14604 2- 227 99.6907 106 7 6.22498 2- 228 94.4284 107 7 6.66733 2- 229 92.6891 108 7 6.06997 2- 230 97.3378 109 7 6.44421 2- 231 13.9282 109 7 6.04035 2- 232 90.6773 110 7 6.67557 2- 233 112.439 111 7 6.31528 2- 234 91.8063 112 7 6.36593 2- 235 115.466 113 7 6.41093 2- 236 36.1517 113 7 26.1874 2- 237 22.6154 113 7 17.9427 2- 238 10.5863 113 7 9.5 2- 239 11.9071 113 7 9.23131 s iter delta rst obj fractionality incumbent 2- 240 8.21936 113 7 8.21936 2- 241 8.19983 113 7 8.19983 2- 242 17.5442 113 7 7.2686 2- 243 6.92943 113 7 6.92943 2- 244 6.91545 113 7 6.85229 2- 245 46.8525 114 7 6.79308 2- 246 57.7022 115 7 6.86265 2- 247 80.5627 116 7 6.97698 2- 248 8.48262 116 7 7.67623 2- 249 95.5298 117 7 7.25517 2- 250 6.91504 117 7 6.91504 2- 251 11.1453 117 7 7.04342 2- 252 6.96686 117 7 6.96686 2- 253 18.9901 117 7 10.1254 2- 254 10.6736 117 7 9.73132 2- 255 60.8846 118 7 6.02756 2- 256 92.5061 119 7 6.17491 2- 257 88.8186 120 7 6.11269 2- 258 109.132 121 7 6.15957 2- 259 98.1497 122 7 6.191 s iter delta rst obj fractionality incumbent 2- 260 97.8462 123 7 7.74893 2- 261 11.4156 123 7 6.24732 2- 262 103.613 124 7 6.30652 2- 263 102.316 125 7 6.29248 2- 264 79.7165 126 7 6.17778 2- 265 103.332 127 7 6.6484 2- 266 109.238 128 7 7.03322 2- 267 6.94131 128 7 6.86829 2- 268 9.1492 128 7 6.50338 2- 269 105.789 129 7 6.24899 2- 270 92.6893 130 7 7.50571 2- 271 7.99547 130 7 7.26088 2- 272 89.8155 131 7 6.4105 2- 273 96.3242 132 7 6.36319 2- 274 103.77 133 7 6.18564 2- 275 103.416 134 7 6.43113 2- 276 95.1786 135 7 6.44564 2- 277 102.913 136 7 6.14196 2- 278 104.87 137 7 6.04299 2- 279 95.2948 138 7 6.20426 s iter delta rst obj fractionality incumbent 2- 280 100.534 139 7 6.90379 2- 281 28.1625 139 7 6.72008 2- 282 33.8919 139 7 28.1216 2- 283 26.6357 139 7 23.092 2- 284 20.3329 139 7 19.3122 2- 285 16.16 139 7 15.6133 2- 286 15.1079 139 7 15.1079 2- 287 38.901 139 7 16.4323 2- 288 26.1944 139 7 18.0833 2- 289 17.1048 139 7 15.5751 2- 290 15.4967 139 7 15.1393 2- 291 16.0395 139 7 13.1293 2- 292 10.4064 139 7 10.4064 2- 293 13.9165 139 7 10.9414 2- 294 11.3854 139 7 10.9029 2- 295 19.6682 139 7 11.1175 2- 296 17.2226 139 7 11.2122 2- 297 14.8056 139 7 11.8123 2- 298 10.791 139 7 10.6254 2- 299 11.0833 139 7 10.9431 s iter delta rst obj fractionality incumbent 2- 300 10.8972 139 7 10.6854 2- 301 10.514 139 7 10.514 2- 302 16.5625 139 7 11.6875 2- 303 19.6655 139 7 11.7653 2- 304 38.6518 140 7 12.1458 2- 305 48.5755 141 7 10.8293 2- 306 10.5103 141 7 10.4845 2- 307 69.7906 142 7 10.9036 Too many restarts Total stage 2 restarts: 100 Stage 3... Using best point from iter: 118 obj offset: 85 + 0 = 85 Clique table members: 516. MIP emphasis: hidden feasible solutions. MIP search method: dynamic search. Parallel mode: none, using 1 thread. Root relaxation solution time = 0.18 sec. Nodes Cuts/ Node Left Objective IInf Best Integer Best Node ItCnt Gap 0 0 -78.9458 199 -78.9458 4610 0 0 -75.8382 226 Cuts: 25 6011 0 0 -75.4102 215 ZeroHalf: 1 6362 0 0 -74.3903 218 ZeroHalf: 1 6783 0 2 -74.3903 218 -74.3903 6783 100 92 -26.4501 197 -73.2818 20193 200 179 16.7261 219 -72.9072 32854 300 271 -18.9397 235 -68.7472 44031 400 361 -15.9701 181 -63.7992 54251 500 451 -35.6246 181 -62.7828 64757 600 535 -18.7230 161 -62.2413 75804 700 625 -21.1899 229 -61.0313 85227 800 711 -25.2152 266 -60.7979 98892 900 791 -14.6897 161 -60.2654 112363 1000 875 -24.5000 83 -59.2877 124864 Elapsed time = 18.35 sec. (tree size = 0.66 MB, solutions = 0) 1100 951 -10.2564 189 -56.3971 137748 1200 1040 -5.5015 190 -55.2357 146871 1300 1129 -37.2415 207 -54.8977 155303 1400 1205 -19.3893 226 -53.9851 171748 1500 1295 -31.4941 156 -53.8583 179774 1600 1367 -31.8175 128 -53.2513 194836 1700 1457 -30.5143 154 -53.2162 202664 1800 1541 -44.9168 223 -52.8369 215117 1900 1637 -31.7363 190 -52.5673 222721 2000 1727 -28.5070 172 -52.4639 231811 Elapsed time = 29.40 sec. (tree size = 1.32 MB, solutions = 0) 2100 1803 -20.4427 212 -52.1704 245181 2200 1875 -27.9500 161 -51.9718 260149 2300 1957 -40.9894 134 -51.5813 268416 2400 2041 -28.8247 167 -51.3144 280283 2500 2114 -43.4434 171 -51.2156 293958 2600 2200 -42.1825 213 -50.7927 303221 2700 2278 -39.5362 267 -50.7300 313868 2800 2366 -14.4123 163 -50.6556 322291 2900 2442 -11.8700 165 -50.5354 333517 3000 2524 -40.8006 208 -50.2742 341293 Elapsed time = 39.93 sec. (tree size = 1.95 MB, solutions = 0) 3100 2602 -38.1934 239 -50.1255 352636 3200 2694 -14.1375 201 -49.7395 360125 3300 2767 -12.1022 196 -49.5081 375882 3400 2845 -27.6596 148 -49.4585 386059 3500 2927 -18.8990 155 -49.3376 395254 3600 3003 -4.4023 243 -49.2472 408842 3700 3079 -29.3411 229 -49.1450 419268 3800 3171 infeasible -49.0701 425034 3900 3257 -29.8265 184 -48.9891 432671 4000 3347 -24.5989 183 -48.9100 439478 Elapsed time = 49.53 sec. (tree size = 2.57 MB, solutions = 0) 4100 3427 -39.6932 191 -48.8559 449187 4200 3517 -34.5625 94 -48.7812 456547 4300 3587 -31.9286 119 -48.6496 470917 4400 3675 -24.1366 160 -48.4269 480767 4500 3757 -33.7577 144 -48.3591 490798 4600 3837 -31.2855 205 -48.2019 500443 4700 3927 -32.7007 195 -48.1909 508597 4800 4013 -30.4726 214 -48.1354 519088 4900 4085 -39.2469 189 -47.9985 530864 5000 4161 -41.1335 171 -47.9287 543241 Elapsed time = 59.56 sec. (tree size = 3.26 MB, solutions = 0) 5100 4249 11.0096 212 -47.9025 551295 5200 4331 -33.5757 187 -47.8669 562617 5300 4405 -28.0827 164 -47.7554 573486 5400 4481 infeasible -47.6929 585596 5500 4563 -20.2716 146 -47.5949 594728 5600 4651 -34.3664 203 -47.5209 601903 5700 4735 -10.0702 189 -47.4029 610183 5800 4819 -37.8145 172 -47.3142 620948 5900 4893 -28.2494 224 -47.2133 632420 6000 4973 -27.5556 123 -47.1590 643354 Elapsed time = 69.23 sec. (tree size = 3.87 MB, solutions = 0) 6100 5047 -23.9202 196 -47.0702 655886 6200 5129 -32.2724 135 -47.0059 665909 6300 5217 -23.9542 167 -46.9587 672829 6400 5295 -35.1964 166 -46.8688 682439 6500 5361 -34.2079 158 -46.7350 699273 6600 5435 -37.2486 188 -46.6468 711709 6700 5517 infeasible -46.6009 720485 6800 5579 -34.1591 185 -46.4932 736723 6900 5650 -42.4994 128 -46.4353 751008 * 6994 959 integral 0 -38.0000 -46.3727 759998 22.03% Clique cuts applied: 2 Zero-half cuts applied: 2 Gomory fractional cuts applied: 2 Status: Feasible CplexStatus:SolLim Solution with obj=7 + 0 = 7 found Writing MIP start values to file bench/ns894788.mst Solution (only non-zero entries are reported): obj = 7 R3457 = 1 R3458 = 1 R3459 = 1 R3460 = 1 R3461 = 1 R3462 = 1 R3463 = 1 R1214 = 1 R1092 = 1 R841 = 1 R83 = 1 R955 = 1 R68 = 1 R1124 = 1 R1005 = 1 R86 = 1 R1131 = 1 R784 = 1 R73 = 1 R1066 = 1 R90 = 1 R1181 = 1 R1179 = 1 R943 = 1 R93 = 1 R986 = 1 R94 = 1 R1062 = 1 R95 = 1 R1268 = 1 R200 = 1 R1319 = 1 R203 = 1 R1527 = 1 R1285 = 1 R205 = 1 R1219 = 1 R207 = 1 R1864 = 1 R329 = 1 R377 = 1 R2061 = 1 R2430 = 1 R2242 = 1 R450 = 1 R2399 = 1 R2142 = 1 R453 = 1 R2556 = 1 R2382 = 1 R2538 = 1 R2479 = 1 R2307 = 1 R463 = 1 R2196 = 1 R464 = 1 R2948 = 1 R2660 = 1 R581 = 1 R550 = 1 R598 = 1 R2667 = 1 R584 = 1 R2896 = 1 R2602 = 1 R586 = 1 R2771 = 1 R588 = 1 R2650 = 1 R590 = 1 R638 = 1 R2726 = 1 R591 = 1 R2710 = 1 R592 = 1 R3392 = 1 R3266 = 1 R3353 = 1 R3170 = 1 R709 = 1 R3416 = 1 R3192 = 1 R712 = 1 R3244 = 1 R714 = 1 R3229 = 1 R715 = 1 R3036 = 1 R718 = 1 R3348 = 1 Feasible FOUND in 307 iterations! First sol: obj=7 time=93 iter=307 restarts=142 stage=3 93.95user 0.02system 1:33.96elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+808outputs (0major+9506minor)pagefaults 0swaps