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 6023 rows and 5611 columns. MIP Presolve modified 87 coefficients. Aggregator did 2091 substitutions. Reduced MIP has 4015 rows, 14154 columns, and 63183 nonzeros. presolving objective offset = 0 (restat: 0) Problem: bench/ns894244.mps Max iter Stage 1: 10000 Max iter Stage 2: 2000 Min change: 20 Initial Presolve: Yes Imported 4015 rows and 14154 columns Objective sense: Minimize Problem is MIP: Yes Initial Algorithm: Auto 14154 integer variables (14154 of which are binary and 0 are general integer) 0 continuous variables Solving relaxed problem...0- 0 -1 0 12.3401 153.746 done obj=12.3401 + 0 = 12.3401 Rounding solution...done Stage 1... improved distance by 0percent 1- 1 166.51 0 12.3433 135.568 improved distance by 0.70091percent 1- 2 116.709 0 12.3564 113.543 improved distance by 0.957021percent 1- 3 111.693 0 12.3795 108.892 improved distance by 0.994564percent 1- 4 111.086 0 12.4161 102.78 1- 5 156.902 0 12.4726 108.733 improved distance by 0.937709percent 1- 6 104.166 0 12.5425 98.6534 improved distance by 0.886869percent 1- 7 92.3815 0 12.6004 90.5088 improved distance by 0.954333percent 1- 8 88.1627 0 12.8165 81.8011 improved distance by 0.845007percent 1- 9 74.4981 0 12.9606 74.3009 improved distance by 0.921424percent 1- 10 68.6443 0 13.2318 67.7487 improved distance by 0.859497percent 1- 11 58.9996 0 13.75 58.848 improved distance by 0.93818percent 1- 12 55.3522 0 13.7407 51.8523 improved distance by 0.836424percent 1- 13 46.2979 0 14 45.7652 improved distance by 0.962039percent 1- 14 44.5404 0 14 44.4886 1- 15 128.095 0 14 54.7188 1- 16 90.2708 0 14 55.4369 1- 17 51.935 0 14 48.9595 1- 18 47.8167 0 14 45.28 1- 19 45.8843 0 14.2159 42.537 s iter delta rst obj fractionality incumbent improved distance by 0.857783percent 1- 20 38.206 0 14.3056 36.0657 1- 21 65.2094 0 14.6208 48.6982 1- 22 46.5623 0 14.5301 44.2932 1- 23 38.721 0 14.9903 36.3403 improved distance by 0.929634percent 1- 24 35.5176 0 15.1517 31.8533 improved distance by 0.951796percent 1- 25 33.8055 0 15.3965 29.4272 improved distance by 0.712633percent 1- 26 24.0909 0 16 21.9687 improved distance by 0.978985percent 1- 27 23.5846 0 16 23.2995 improved distance by 0.992227percent 1- 28 23.4013 0 16 22.7819 1- 29 161.591 0 16 42.6043 1- 30 34.1313 0 16 27.6937 improved distance by 0.947419percent 1- 31 22.1709 0 16 16.48 improved distance by 0.61391percent 1- 32 13.6109 0 16 11.2932 improved distance by 0.799338percent 1- 33 10.8797 0 16 10.8797 improved distance by 0.928294percent 1- 34 10.0996 0 16 9.91681 improved distance by 0.95007percent 1- 35 9.59531 0 16 9.46679 improved distance by 0.984765percent 1- 36 9.44913 0 16 9.44913 1- 37 13.7281 0 16 10.124 1- 38 24.3362 0 16 13.3274 1- 39 12.0157 0 16 11.3124 s iter delta rst obj fractionality incumbent 1- 40 11.2204 0 16 10.2517 1- 41 10.0687 0 16 10.0687 1- 42 10.5129 0 16 10.2625 1- 43 392.102 1 16 12.1546 1- 44 16.1513 1 16 13.1595 1- 45 11.2415 1 16 10.5928 1- 46 10.4178 1 16 10.4178 1- 47 11.4593 1 16 10.4295 1- 48 15.7826 1 16 10.5855 1- 49 10.3828 1 16 9.46646 1- 50 22.3065 1 16 12.2805 1- 51 10.7868 1 16 10.7868 1- 52 11.7419 1 16 9.82698 1- 53 10.1156 1 16 9.80824 1- 54 9.51441 1 16 9.32883 1- 55 16.7086 1 16 10.1648 1- 56 9.49721 1 16 9.37583 1- 57 13.322 1 16 11.4074 1- 58 14.2121 1 16 11.393 1- 59 10.4487 1 16 10.4487 s iter delta rst obj fractionality incumbent 1- 60 12.3292 1 16 9.70368 1- 61 9.62652 1 16 9.02652 1- 62 27.7032 1 16 11.0665 1- 63 17.7826 1 16 13.6049 1- 64 15.7989 1 16 13.9383 1- 65 12.1577 1 16 10.2232 improved distance by 0.986397percent 1- 66 9.32059 1 16 8.85344 improved distance by 0.911151percent 1- 67 8.49247 1 16 8.38135 improved distance by 0.945752percent 1- 68 8.03176 1 16 8.03176 1- 69 15.4928 1 16 10.0948 1- 70 9.99148 1 16 9.99148 1- 71 15.1711 1 16 9.99606 1- 72 10.7848 1 16 8.42442 1- 73 8.03176 1 16 8.03176 1- 74 15.0383 1 16 8.45497 1- 75 14.2321 1 16 8.6437 1- 76 8.03494 1 16 8.03494 1- 77 8.03494 1 16 8.03494 1- 78 438.037 2 16 8.93317 improved distance by 0.995363percent 1- 79 7.99452 2 16 7.99452 s iter delta rst obj fractionality incumbent 1- 80 7.99466 2 16 7.99466 1- 81 7.99466 2 16 7.99466 1- 82 441.291 3 16 8.75739 1- 83 408.738 4 16 9.41731 1- 84 11.1608 4 16 8.32808 1- 85 9.3424 4 16 8.32426 1- 86 8.32758 4 16 8.23526 1- 87 21.3952 4 16 10.6664 1- 88 16.2229 4 16 9.16852 1- 89 8.06667 4 16 8.06667 1- 90 8.06689 4 16 8.06689 1- 91 19.5478 4 16 8.78548 improved distance by 0.965763percent 1- 92 7.72081 4 16 7.72081 1- 93 14.0635 4 16 9.2999 1- 94 12.8182 4 16 8.85266 1- 95 7.97328 4 16 7.63959 1- 96 12.0652 4 16 7.55797 improved distance by 0.978316percent 1- 97 7.55339 4 16 7.55339 1- 98 7.55435 4 16 7.55435 1- 99 16.98 4 16 9.71506 s iter delta rst obj fractionality incumbent 1- 100 13.7542 4 16 8.85329 improved distance by 0.963515percent 1- 101 7.27781 4 16 7.26328 1- 102 12.7547 4 16 8.04084 1- 103 16.4332 4 16 8.23392 1- 104 11.4345 4 16 8.23542 1- 105 8.0288 4 16 7.97752 1- 106 10.5308 4 16 7.99607 1- 107 8.02999 4 16 8.00308 1- 108 7.9399 4 16 7.60656 1- 109 7.59068 4 16 7.59068 1- 110 7.59068 4 16 7.59068 1- 111 474.119 5 16 10.3288 1- 112 8.47074 5 16 7.25487 improved distance by 0.913279percent 1- 113 6.64667 5 16 6.64667 1- 114 15.503 5 16 7.75482 1- 115 432.841 6 16 7.72382 Too many iteration without 10% improvement Total stage 1 restarts: 6 Stage 2... Using best point from iter: 113 2- 116 6.65078 6 16 6.64667 2- 117 8.85476 6 16 6.69557 2- 118 6.69157 6 16 6.68794 2- 119 11.7999 6 16 6.57581 s iter delta rst obj fractionality incumbent 2- 120 10.3829 6 16 6.71354 2- 121 7.28023 6 16 7.26328 2- 122 10.5101 6 16 7.31303 2- 123 22.2776 7 16 7.27125 2- 124 7.281 7 16 7.26029 2- 125 24.5792 7 16 7.31027 2- 126 16.1055 7 16 7.18333 2- 127 7.16276 7 16 7.12442 2- 128 7.04848 7 16 7.04732 2- 129 7.05004 7 16 7.04899 2- 130 7.0279 7 16 6.67404 2- 131 6.6849 7 16 6.67404 2- 132 8.70827 7 16 6.68767 2- 133 6.68957 7 16 6.67638 2- 134 24.6889 8 16 6.68794 2- 135 48.6548 9 16 6.71082 2- 136 78.6688 10 16 6.69642 2- 137 97.6781 11 16 6.6985 2- 138 116.564 12 16 6.96113 2- 139 129.361 13 16 6.8402 s iter delta rst obj fractionality incumbent 2- 140 142.646 14 16 6.67638 2- 141 7.2781 14 16 6.74449 2- 142 15.7269 14 16 7.6837 2- 143 8.02904 14 16 6.80082 2- 144 6.65368 14 16 6.65346 2- 145 6.68844 14 16 6.68794 2- 146 9.28091 14 16 6.80545 2- 147 6.68904 14 16 6.67638 2- 148 17.4195 14 16 10.3071 2- 149 8.93609 14 16 8.28712 2- 150 21.0004 14 16 8.05977 2- 151 7.22001 14 16 7.21991 2- 152 17.8699 14 16 7.89378 2- 153 9.04495 14 16 8.40064 2- 154 8.39623 14 16 7.90992 2- 155 7.62191 14 16 7.62002 2- 156 8.67828 14 16 6.34926 2- 157 7.00075 14 16 6.39961 2- 158 6.29811 14 16 6.29806 2- 159 11.1464 14 16 7.03282 s iter delta rst obj fractionality incumbent 2- 160 7.00208 14 16 6.9812 2- 161 9.42537 14 16 7.09641 2- 162 7.06183 14 16 6.67882 2- 163 7.69969 14 16 6.73819 2- 164 7.01439 14 16 6.79226 2- 165 61.2 14 16 18.2 2- 166 16.2143 14 16 11.2143 2- 167 19.1875 14 16 9.3125 2- 168 11.5455 14 16 9.27273 2- 169 16.5 14 16 10 2- 170 12.25 14 16 10 2- 171 14.5 14 16 10 2- 172 32.25 15 16 10.25 2- 173 53.25 16 16 10.25 2- 174 67.6667 17 16 10 2- 175 7.28449 17 16 7.28448 2- 176 7.20092 17 16 6.95527 2- 177 10.4514 17 16 7.3125 2- 178 58.1984 18 16 7.01788 2- 179 8.28449 18 16 7.28448 s iter delta rst obj fractionality incumbent 2- 180 7.28449 18 16 7.28448 2- 181 7.20091 18 16 6.95527 2- 182 6.54809 18 16 6.53689 2- 183 5.27334 18 16 3.28667 2- 184 3.28447 18 16 3.28446 2- 185 3.28449 18 16 3.28448 2- 186 35.2653 19 16 3.31205 2- 187 65.2845 20 16 3.28446 2- 188 85.0694 21 16 3.34722 2- 189 97.2453 22 16 3.29522 2- 190 19.2346 22 16 3.31844 2- 191 3.27778 22 16 3.27778 2- 192 4.27778 22 16 3.27778 2- 193 91.2778 23 16 3.27778 2- 194 94.2569 24 16 3.29861 2- 195 4.81597 24 16 3.36458 2- 196 108.196 25 16 3.30405 2- 197 133.278 26 16 3.27778 2- 198 146.278 27 16 3.27778 2- 199 149.196 28 16 3.30357 s iter delta rst obj fractionality incumbent 2- 200 183.589 29 16 3.30357 2- 201 10.6073 29 16 3.36126 2- 202 166.278 30 16 3.27778 2- 203 208.257 31 16 3.29861 2- 204 13.4185 31 16 3.29758 2- 205 188.232 32 16 3.33929 2- 206 3.27749 32 16 3.27749 2- 207 18.125 32 16 3.75 2- 208 3.23 32 16 3.23 2- 209 4.23 32 16 3.23 2- 210 3.22901 32 16 3.22901 2- 211 102.23 33 16 3.23 2- 212 110.229 34 16 3.22901 2- 213 153.1 35 16 3.3 2- 214 150.229 36 16 3.22901 2- 215 179.23 37 16 3.23 2- 216 214.136 38 16 3.27273 2- 217 211.168 39 16 3.22901 2- 218 229.168 40 16 3.22901 2- 219 3.22901 40 16 3.22901 s iter delta rst obj fractionality incumbent 2- 220 3.23 40 16 3.23 2- 221 194.168 41 16 3.22901 2- 222 227.104 42 16 3.31693 2- 223 244.206 43 16 3.23529 2- 224 8.96375 43 16 3.24419 2- 225 218.594 44 16 3.24752 2- 226 232.483 45 16 4.91954 2- 227 4.23 45 16 3.23 2- 228 3.22901 45 16 3.22901 2- 229 11.7557 45 16 3.12214 2- 230 3.10227 45 16 3.10227 2- 231 7.09924 45 16 3.09924 2- 232 3.09924 45 16 3.09924 2- 233 11.6853 45 16 3.31469 2- 234 3.23 45 16 3.23 2- 235 93.229 46 16 3.22901 2- 236 13.7381 46 16 6.64286 2- 237 6.36667 46 16 5.7 2- 238 5.7 46 16 5.7 2- 239 6.27778 46 16 3.38889 s iter delta rst obj fractionality incumbent 2- 240 3.36667 46 16 3.36667 2- 241 3.36667 46 16 3.36667 2- 242 46.3 47 16 3.7 2- 243 71.3667 48 16 3.36667 2- 244 98.3667 49 16 3.36667 2- 245 104.367 50 16 3.36667 2- 246 150.367 51 16 3.36667 2- 247 149.355 52 16 3.3871 2- 248 3.83333 52 16 3.36667 2- 249 143.367 53 16 3.36667 2- 250 179.367 54 16 3.36667 2- 251 174.167 55 16 3.36667 2- 252 219.3 56 16 3.36667 2- 253 235.226 57 16 3.3871 2- 254 233.269 58 16 3.42308 2- 255 295.367 59 16 3.36667 2- 256 3.36667 59 16 3.36667 2- 257 14.5 59 16 8.16667 2- 258 8 59 16 8 2- 259 8 59 16 8 s iter delta rst obj fractionality incumbent 2- 260 168 60 16 8 2- 261 10.5 60 16 8 2- 262 178 61 16 8 2- 263 185 62 16 8 2- 264 210.25 63 16 8.75 2- 265 8.5 63 16 8.5 2- 266 8.57143 63 16 6.14286 2- 267 5.47872 63 16 5.47872 2- 268 8.16667 63 16 5.5 2- 269 5.5 63 16 5.5 2- 270 6.16667 63 16 5.5 2- 271 9.33333 63 16 6.33333 2- 272 86.5 64 16 6.16667 2- 273 5.76471 64 16 5.23529 2- 274 5 64 16 5 2- 275 4 64 16 4 2- 276 9.66667 64 16 5 2- 277 4 64 16 4 2- 278 4 64 16 4 2- 279 7 64 16 5 s iter delta rst obj fractionality incumbent 2- 280 5 64 16 5 2- 281 5 64 16 5 2- 282 43 65 16 5 2- 283 64 66 16 5 2- 284 81 67 16 5 2- 285 103 68 16 5 2- 286 126 69 16 5 2- 287 150 70 16 5 2- 288 159 71 16 5 2- 289 187 72 16 5 2- 290 214 73 16 5 2- 291 221 74 16 5 2- 292 241 75 16 5 2- 293 264 76 16 0 Total stage 2 restarts: 70 Solution with obj=16 + 0 = 16 found Writing MIP start values to file bench/ns894244.mst Solution (only non-zero entries are reported): obj = 16 R21841 = 1 R21842 = 1 R21843 = 1 R21844 = 1 R21845 = 1 R21846 = 1 R21847 = 1 R21848 = 1 R21849 = 1 R21850 = 1 R21851 = 1 R21852 = 1 R21853 = 1 R21854 = 1 R21855 = 1 R21856 = 1 R4680 = 1 R178 = 1 R226 = 1 R4552 = 1 R133 = 1 R181 = 1 R229 = 1 R4198 = 1 R72 = 1 R120 = 1 R168 = 1 R216 = 1 R4415 = 1 R125 = 1 R173 = 1 R221 = 1 R4517 = 1 R126 = 1 R174 = 1 R222 = 1 R4569 = 1 R128 = 1 R176 = 1 R224 = 1 R272 = 1 R5501 = 1 R346 = 1 R394 = 1 R442 = 1 R490 = 1 R7192 = 1 R6974 = 1 R706 = 1 R754 = 1 R7509 = 1 R7290 = 1 R757 = 1 R7514 = 1 R806 = 1 R7083 = 1 R711 = 1 R759 = 1 R7014 = 1 R712 = 1 R760 = 1 R6577 = 1 R604 = 1 R652 = 1 R700 = 1 R748 = 1 R7299 = 1 R767 = 1 R6661 = 1 R624 = 1 R672 = 1 R720 = 1 R768 = 1 R8082 = 1 R930 = 1 R978 = 1 R1026 = 1 R8242 = 1 R996 = 1 R1044 = 1 R7732 = 1 R885 = 1 R933 = 1 R981 = 1 R1029 = 1 R8328 = 1 R982 = 1 R1030 = 1 R7867 = 1 R887 = 1 R935 = 1 R983 = 1 R1031 = 1 R8424 = 1 R1001 = 1 R1049 = 1 R1065 = 1 R8280 = 1 R1002 = 1 R1050 = 1 R8359 = 1 R1003 = 1 R1051 = 1 R8210 = 1 R956 = 1 R1004 = 1 R1052 = 1 R8140 = 1 R941 = 1 R989 = 1 R1037 = 1 R8187 = 1 R991 = 1 R1039 = 1 R9257 = 1 R1222 = 1 R1270 = 1 R1318 = 1 R1350 = 1 R9460 = 1 R1241 = 1 R1289 = 1 R1337 = 1 R8833 = 1 R1167 = 1 R1215 = 1 R1263 = 1 R1311 = 1 R1359 = 1 R10006 = 1 R1426 = 1 R1474 = 1 R1522 = 1 R1570 = 1 R10883 = 1 R1578 = 1 R11262 = 1 R1697 = 1 R1745 = 1 R1793 = 1 R1841 = 1 R11414 = 1 R1698 = 1 R1746 = 1 R1794 = 1 R1842 = 1 R11868 = 1 R1828 = 1 R11212 = 1 R1701 = 1 R1749 = 1 R1797 = 1 R1845 = 1 R11235 = 1 R1686 = 1 R1734 = 1 R1782 = 1 R1830 = 1 R12073 = 1 R1850 = 1 R12095 = 1 R1852 = 1 R12140 = 1 R1869 = 1 R11447 = 1 R1743 = 1 R1791 = 1 R1839 = 1 R11229 = 1 R1712 = 1 R1760 = 1 R1808 = 1 R1856 = 1 R12964 = 1 R2065 = 1 R2113 = 1 R12450 = 1 R1970 = 1 R2018 = 1 R2066 = 1 R2114 = 1 R12669 = 1 R2019 = 1 R2067 = 1 R2115 = 1 R12986 = 1 R2069 = 1 R2117 = 1 R12883 = 1 R2022 = 1 R2070 = 1 R2118 = 1 R13423 = 1 R2167 = 1 R12901 = 1 R2074 = 1 R2122 = 1 R12833 = 1 R2027 = 1 R2075 = 1 R2123 = 1 R12761 = 1 R2028 = 1 R2076 = 1 R2124 = 1 R13396 = 1 R12459 = 1 R1983 = 1 R2031 = 1 R2079 = 1 R2127 = 1 R13926 = 1 R2289 = 1 R2337 = 1 R2385 = 1 R13720 = 1 R2228 = 1 R2276 = 1 R2324 = 1 R2372 = 1 R13871 = 1 R2300 = 1 R2348 = 1 R2396 = 1 R13967 = 1 R2288 = 1 R2336 = 1 R2384 = 1 R15702 = 1 R15747 = 1 R2675 = 1 R15574 = 1 R2676 = 1 R14861 = 1 R2486 = 1 R2534 = 1 R2582 = 1 R2630 = 1 R2678 = 1 R15442 = 1 R2632 = 1 R2680 = 1 R15754 = 1 R2682 = 1 R15671 = 1 R15536 = 1 R2652 = 1 R15396 = 1 R2637 = 1 R2685 = 1 R15065 = 1 R2542 = 1 R2590 = 1 R2638 = 1 R2686 = 1 R2718 = 1 R15517 = 1 R2639 = 1 R2687 = 1 R2719 = 1 R15595 = 1 R2688 = 1 R16668 = 1 R2898 = 1 R2946 = 1 R16676 = 1 R2932 = 1 R16466 = 1 R2853 = 1 R2901 = 1 R2949 = 1 R16176 = 1 R2806 = 1 R2854 = 1 R2902 = 1 R2950 = 1 R16860 = 1 R2969 = 1 R16270 = 1 R2842 = 1 R2890 = 1 R2938 = 1 R16419 = 1 R2844 = 1 R2892 = 1 R2940 = 1 R15977 = 1 R2797 = 1 R2845 = 1 R2893 = 1 R2941 = 1 R16061 = 1 R2814 = 1 R2862 = 1 R2910 = 1 R2958 = 1 R16660 = 1 R2912 = 1 R2960 = 1 R18232 = 1 R18181 = 1 R3263 = 1 R18438 = 1 R3329 = 1 R3377 = 1 R3425 = 1 R3473 = 1 R19182 = 1 R3490 = 1 R18672 = 1 R3379 = 1 R3427 = 1 R3475 = 1 R19278 = 1 R3493 = 1 R18838 = 1 R3430 = 1 R3478 = 1 R18622 = 1 R3383 = 1 R3431 = 1 R3479 = 1 R18478 = 1 R3336 = 1 R3384 = 1 R3432 = 1 R3480 = 1 R19302 = 1 R3497 = 1 R3513 = 1 R18513 = 1 R3339 = 1 R3387 = 1 R3435 = 1 R3483 = 1 R18343 = 1 R3340 = 1 R3388 = 1 R3436 = 1 R3484 = 1 R18569 = 1 R3341 = 1 R3389 = 1 R3437 = 1 R3485 = 1 R18965 = 1 R3438 = 1 R3486 = 1 R19472 = 1 R20586 = 1 R20452 = 1 R19646 = 1 R3605 = 1 R3653 = 1 R3701 = 1 R3749 = 1 R20318 = 1 R3750 = 1 R20225 = 1 R3751 = 1 R20569 = 1 R20646 = 1 R20397 = 1 R3759 = 1 R20434 = 1 R3760 = 1 R21474 = 1 R4017 = 1 R20865 = 1 R3883 = 1 R3931 = 1 R3979 = 1 R4027 = 1 R4075 = 1 Feasible FOUND in 293 iterations! First sol: obj=16 time=433 iter=293 restarts=76 stage=2 432.79user 0.19system 7:12.96elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+5520outputs (0major+90399minor)pagefaults 0swaps