Wrong Upper Bound
Answered
Hi,
According to the MIP logging I've attached, Gurobi explored 515 nodes when solving the problem. The last node is 514, and the best bound at this node is 1616.99. However, Gurobi stopped at this node and reported that the optimal solution was found with the value of 1470.55. How is this possible?
Set parameter Username
Academic license - for non-commercial use only - expires 2025-03-08
Indices of the middle 5 members of the vector (excluding member with index 0):
Set parameter LazyConstraints to value 1
Set parameter PreCrush to value 1
Set parameter TimeLimit to value 1996.884
Set parameter MIPGap to value 0
Set parameter Threads to value 1
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (win64 - Windows 10.0 (19045.2))
CPU model: 11th Gen Intel(R) Core(TM) i7-11700 @ 2.50GHz, instruction set [SSE2|AVX|AVX2|AVX512]
Thread count: 8 physical cores, 16 logical processors, using up to 1 threads
Optimize a model with 82649 rows, 81586 columns and 415060 nonzeros
Model fingerprint: 0xc270a543
Variable types: 70951 continuous, 10635 integer (0 binary)
Coefficient statistics:
Matrix range [1e-02, 5e+02]
Objective range [1e-02, 1e-02]
Bounds range [2e+09, 2e+09]
RHS range [6e-01, 4e+01]
Warning: Model contains large bounds
Consider reformulating model or setting NumericFocus parameter
to avoid numerical issues.
Presolve removed 15900 rows and 13074 columns (presolve time = 5s) ...
Presolve removed 15900 rows and 13074 columns
Presolve time: 5.04s
Presolved: 66749 rows, 68512 columns, 340115 nonzeros
Variable types: 59533 continuous, 8979 integer (5999 binary)
objVal = -1e+100 & bestBound = 5313.23
Root relaxation presolved: 66787 rows, 68512 columns, 352565 nonzeros
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
0 5.3132300e+03 3.308461e+04 0.000000e+00 24s
9232 3.7692065e+03 6.652288e+04 0.000000e+00 25s
14451 1.6234500e+03 0.000000e+00 0.000000e+00 26s
Root relaxation: objective 1.623450e+03, 14451 iterations, 1.46 seconds (2.69 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 1623.45000 0 118 - 1623.45000 - - 26s
objVal = -1e+100 & bestBound = 1623.45
0 0 1623.45000 0 118 - 1623.45000 - - 32s
objVal = -1e+100 & bestBound = 1623.45
objVal = -1e+100 & bestBound = 1623.45
objVal = -1e+100 & bestBound = 1623.45
H 0 0 670.9500000 1623.45000 142% - 33s
objVal = 670.95 & bestBound = 1623.45
0 0 1623.45000 0 118 670.95000 1623.45000 142% - 37s
objVal = 670.95 & bestBound = 1623.45
objVal = 670.95 & bestBound = 1623.45
objVal = 670.95 & bestBound = 1623.45
H 0 0 704.7600000 1623.45000 130% - 39s
objVal = 704.76 & bestBound = 1623.45
0 0 1623.45000 0 118 704.76000 1623.45000 130% - 41s
objVal = 704.76 & bestBound = 1623.45
objVal = 704.76 & bestBound = 1623.45
0 0 1623.45000 0 118 704.76000 1623.45000 130% - 48s
objVal = 704.76 & bestBound = 1623.45
0 0 1623.45000 0 118 704.76000 1623.45000 130% - 51s
objVal = 704.76 & bestBound = 1623.45
0 0 1623.45000 0 118 704.76000 1623.45000 130% - 55s
0 0 1619.79926 0 142 704.76000 1619.79926 130% - 58s
objVal = 704.76 & bestBound = 1619.69
0 0 1619.68731 0 142 704.76000 1619.68731 130% - 62s
objVal = 704.76 & bestBound = 1619.69
objVal = 704.76 & bestBound = 1619.69
0 0 1619.68731 0 142 704.76000 1619.68731 130% - 67s
objVal = 704.76 & bestBound = 1619.69
0 0 1619.68731 0 142 704.76000 1619.68731 130% - 70s
objVal = 704.76 & bestBound = 1619.69
objVal = 704.76 & bestBound = 1619.69
0 0 1619.68731 0 142 704.76000 1619.68731 130% - 87s
objVal = 704.76 & bestBound = 1619.69
0 0 1619.68731 0 142 704.76000 1619.68731 130% - 103s
objVal = 704.76 & bestBound = 1619.69
0 0 1619.68731 0 142 704.76000 1619.68731 130% - 118s
objVal = 704.76 & bestBound = 1619.69
0 0 1619.68731 0 142 704.76000 1619.68731 130% - 133s
objVal = 704.76 & bestBound = 1619.69
0 0 1619.68731 0 142 704.76000 1619.68731 130% - 149s
0 0 1619.52699 0 146 704.76000 1619.52699 130% - 153s
objVal = 704.76 & bestBound = 1619.49
0 0 1619.48577 0 146 704.76000 1619.48577 130% - 157s
objVal = 704.76 & bestBound = 1619.49
0 0 1619.48577 0 146 704.76000 1619.48577 130% - 161s
objVal = 704.76 & bestBound = 1619.49
objVal = 704.76 & bestBound = 1619.49
0 0 1619.48577 0 146 704.76000 1619.48577 130% - 168s
objVal = 704.76 & bestBound = 1619.49
0 0 1619.48577 0 146 704.76000 1619.48577 130% - 172s
objVal = 704.76 & bestBound = 1619.49
0 0 1619.48577 0 146 704.76000 1619.48577 130% - 181s
objVal = 704.76 & bestBound = 1619.49
0 0 1619.48577 0 146 704.76000 1619.48577 130% - 190s
objVal = 704.76 & bestBound = 1619.49
0 0 1619.48577 0 146 704.76000 1619.48577 130% - 204s
objVal = 704.76 & bestBound = 1619.49
0 0 1619.48577 0 146 704.76000 1619.48577 130% - 215s
objVal = 704.76 & bestBound = 1619.49
0 0 1619.48577 0 146 704.76000 1619.48577 130% - 229s
objVal = 704.76 & bestBound = 1619.49
0 0 1619.48577 0 146 704.76000 1619.48577 130% - 238s
objVal = 704.76 & bestBound = 1619.49
0 0 1619.48577 0 146 704.76000 1619.48577 130% - 245s
objVal = 704.76 & bestBound = 1619.49
0 0 1619.48577 0 146 704.76000 1619.48577 130% - 253s
objVal = 704.76 & bestBound = 1619.49
0 0 1619.48577 0 146 704.76000 1619.48577 130% - 261s
objVal = 704.76 & bestBound = 1619.49
0 0 1619.48577 0 146 704.76000 1619.48577 130% - 269s
objVal = 704.76 & bestBound = 1617
0 0 1616.99826 0 266 704.76000 1616.99826 129% - 277s
objVal = 704.76 & bestBound = 1617
0 0 1616.99826 0 266 704.76000 1616.99826 129% - 283s
objVal = 704.76 & bestBound = 1617
0 0 1616.99826 0 266 704.76000 1616.99826 129% - 288s
objVal = 704.76 & bestBound = 1617
0 0 1616.99826 0 266 704.76000 1616.99826 129% - 295s
objVal = 704.76 & bestBound = 1617
0 0 1616.99826 0 266 704.76000 1616.99826 129% - 302s
0 2 1616.99826 0 266 704.76000 1616.99826 129% - 302s
2 4 1616.99826 2 264 704.76000 1616.99826 129% 872 306s
6 8 1616.99826 6 143 704.76000 1616.99826 129% 507 310s
8 10 1616.99826 7 258 704.76000 1616.99826 129% 857 319s
9 11 1616.99826 8 141 704.76000 1616.99826 129% 809 323s
10 12 1616.99826 9 255 704.76000 1616.99826 129% 871 328s
11 13 1616.99826 9 146 704.76000 1616.99826 129% 960 332s
12 14 1616.99826 10 253 704.76000 1616.99826 129% 947 335s
14 16 1616.99826 12 249 704.76000 1616.99826 129% 881 342s
15 17 1616.99826 13 213 704.76000 1616.99826 129% 881 346s
16 18 1616.99826 14 208 704.76000 1616.99826 129% 899 353s
17 19 1616.99826 15 243 704.76000 1616.99826 129% 857 357s
18 20 1616.99826 16 247 704.76000 1616.99826 129% 818 360s
20 22 1616.99826 17 239 704.76000 1616.99826 129% 893 369s
21 23 1616.99826 18 233 704.76000 1616.99826 129% 867 371s
23 25 1616.99826 20 230 704.76000 1616.99826 129% 809 375s
25 27 1616.99826 22 225 704.76000 1616.99826 129% 774 381s
objVal = 704.76 & bestBound = 1617
26 28 1616.99826 23 192 704.76000 1616.99826 129% 765 398s
28 30 1616.99826 25 121 704.76000 1616.99826 129% 739 400s
32 34 1616.99826 29 149 704.76000 1616.99826 129% 729 405s
37 39 1616.99826 33 132 704.76000 1616.99826 129% 679 410s
39 41 1616.99826 35 112 704.76000 1616.99826 129% 703 415s
41 43 1616.99826 36 119 704.76000 1616.99826 129% 713 420s
44 46 1616.99826 39 190 704.76000 1616.99826 129% 702 426s
46 48 1616.99826 41 182 704.76000 1616.99826 129% 687 430s
49 51 1616.99826 44 174 704.76000 1616.99826 129% 656 435s
objVal = 704.76 & bestBound = 1617
52 54 1616.99826 47 155 704.76000 1616.99826 129% 631 464s
53 55 1616.99826 48 153 704.76000 1616.99826 129% 629 465s
60 62 1616.96457 55 157 704.76000 1616.99826 129% 577 470s
68 70 1616.90670 63 108 704.76000 1616.99826 129% 528 475s
75 77 1616.44320 69 96 704.76000 1616.99826 129% 509 480s
88 90 1615.18948 79 85 704.76000 1616.99826 129% 488 485s
101 103 1614.38415 90 76 704.76000 1616.99826 129% 467 490s
108 110 1614.01267 96 76 704.76000 1616.99826 129% 461 495s
117 119 1613.41062 104 70 704.76000 1616.99826 129% 439 500s
127 129 1611.16137 111 67 704.76000 1616.99826 129% 425 505s
143 145 1607.63533 122 36 704.76000 1616.99826 129% 401 510s
objVal = 704.76 & bestBound = 1617
objVal = 704.76 & bestBound = 1617
158 160 1513.69200 132 4 704.76000 1616.99826 129% 374 517s
objVal = 704.76 & bestBound = 1617
159 161 1506.86933 133 6 704.76000 1616.99826 129% 372 520s
objVal = 704.76 & bestBound = 1617
objVal = 704.76 & bestBound = 1617
160 162 1616.99826 2 262 704.76000 1616.99826 129% 390 532s
161 163 1616.99826 3 280 704.76000 1616.99826 129% 402 539s
162 164 1616.99826 4 261 704.76000 1616.99826 129% 406 545s
163 165 1616.99826 5 253 704.76000 1616.99826 129% 411 551s
164 166 1616.99826 6 322 704.76000 1616.99826 129% 415 555s
165 167 1616.99826 7 329 704.76000 1616.99826 129% 417 560s
166 168 1616.99826 8 325 704.76000 1616.99826 129% 426 567s
167 169 1616.99826 9 302 704.76000 1616.99826 129% 431 572s
168 170 1616.99826 10 216 704.76000 1616.99826 129% 431 575s
170 172 1616.99826 12 169 704.76000 1616.99826 129% 430 580s
172 174 1616.99826 14 171 704.76000 1616.99826 129% 430 587s
174 176 1616.99826 16 173 704.76000 1616.99826 129% 431 591s
176 178 1616.99826 18 176 704.76000 1616.99826 129% 433 596s
178 180 1616.99826 20 188 704.76000 1616.99826 129% 434 600s
181 183 1616.99826 23 172 704.76000 1616.99826 129% 433 606s
184 186 1616.99826 26 185 704.76000 1616.99826 129% 428 610s
187 189 1616.99826 29 187 704.76000 1616.99826 129% 432 617s
189 191 1616.99826 31 183 704.76000 1616.99826 129% 433 621s
192 194 1616.99826 34 131 704.76000 1616.99826 129% 431 626s
196 198 1616.99826 38 129 704.76000 1616.99826 129% 429 630s
206 208 1616.99826 48 134 704.76000 1616.99826 129% 417 635s
216 218 1615.25229 57 119 704.76000 1616.99826 129% 416 643s
219 221 1616.13182 59 103 704.76000 1616.99826 129% 414 645s
229 231 1615.62876 68 115 704.76000 1616.99826 129% 406 650s
239 241 1614.96381 78 90 704.76000 1616.99826 129% 400 655s
248 250 1612.14369 85 63 704.76000 1616.99826 129% 394 660s
objVal = 704.76 & bestBound = 1617
261 263 1606.99926 94 40 704.76000 1616.99826 129% 386 710s
objVal = 704.76 & bestBound = 1617
262 264 1608.22384 95 43 704.76000 1616.99826 129% 384 720s
objVal = 704.76 & bestBound = 1617
281 283 1511.98600 105 12 704.76000 1616.99826 129% 371 727s
objVal = 704.76 & bestBound = 1617
objVal = 704.76 & bestBound = 1617
objVal = 704.76 & bestBound = 1617
283 285 1537.27280 105 8 704.76000 1616.99826 129% 370 732s
objVal = 704.76 & bestBound = 1617
objVal = 704.76 & bestBound = 1617
285 287 1508.72000 106 7 704.76000 1616.99826 129% 369 736s
objVal = 704.76 & bestBound = 1617
objVal = 704.76 & bestBound = 1617
objVal = 704.76 & bestBound = 1617
objVal = 704.76 & bestBound = 1617
288 290 1616.99826 5 275 704.76000 1616.99826 129% 374 747s
289 291 1616.99826 6 270 704.76000 1616.99826 129% 379 752s
290 292 1616.99826 7 274 704.76000 1616.99826 129% 382 758s
291 293 1616.99826 8 213 704.76000 1616.99826 129% 382 761s
292 294 1616.99826 9 262 704.76000 1616.99826 129% 386 767s
293 295 1616.99826 10 280 704.76000 1616.99826 129% 388 773s
294 296 1616.99826 11 224 704.76000 1616.99826 129% 389 776s
295 297 1616.99826 12 342 704.76000 1616.99826 129% 401 789s
296 298 1616.99826 13 356 704.76000 1616.99826 129% 403 793s
297 299 1616.99826 14 253 704.76000 1616.99826 129% 402 795s
299 301 1616.99826 16 165 704.76000 1616.99826 129% 402 802s
301 303 1616.99826 18 215 704.76000 1616.99826 129% 405 807s
303 305 1616.99826 20 211 704.76000 1616.99826 129% 406 811s
objVal = 704.76 & bestBound = 1617
304 306 1616.68602 21 215 704.76000 1616.99826 129% 412 852s
306 308 1616.36788 23 201 704.76000 1616.99826 129% 415 855s
312 314 1616.08488 29 165 704.76000 1616.99826 129% 415 860s
318 320 1614.29378 35 129 704.76000 1616.99826 129% 420 865s
330 332 1611.97319 47 133 704.76000 1616.99826 129% 418 870s
352 354 1610.25306 69 89 704.76000 1616.99826 129% 403 875s
objVal = 704.76 & bestBound = 1617
386 388 1552.51521 91 11 704.76000 1616.99826 129% 379 882s
objVal = 704.76 & bestBound = 1617
387 389 1528.56600 92 9 704.76000 1616.99826 129% 378 885s
objVal = 704.76 & bestBound = 1617
objVal = 704.76 & bestBound = 1617
392 394 1485.81619 94 8 704.76000 1616.99826 129% 375 890s
objVal = 704.76 & bestBound = 1617
objVal = 704.76 & bestBound = 1617
* 395 395 96 1470.5500000 1616.99826 10.0% 372 893s
objVal = 1470.55 & bestBound = 1617
397 395 cutoff 98 1470.55000 1616.99826 10.0% 371 895s
399 395 1616.99826 8 272 1470.55000 1616.99826 10.0% 377 902s
400 396 1616.99826 9 224 1470.55000 1616.99826 10.0% 381 908s
401 397 1616.99826 10 274 1470.55000 1616.99826 10.0% 382 912s
402 398 1616.99826 11 263 1470.55000 1616.99826 10.0% 385 919s
403 399 1616.99826 12 362 1470.55000 1616.99826 10.0% 391 930s
404 400 1616.99826 13 265 1470.55000 1616.99826 10.0% 393 936s
405 401 1616.99826 14 268 1470.55000 1616.99826 10.0% 395 943s
406 402 1616.99826 15 280 1470.55000 1616.99826 10.0% 396 948s
407 403 1616.99826 15 197 1470.55000 1616.99826 10.0% 398 953s
408 404 1616.95038 16 196 1470.55000 1616.99826 10.0% 398 956s
410 406 1561.91103 17 227 1470.55000 1616.99826 10.0% 406 968s
411 407 1616.84898 18 227 1470.55000 1616.99826 10.0% 405 970s
412 408 1616.31481 19 227 1470.55000 1616.99826 10.0% 408 975s
414 410 1616.12507 21 193 1470.55000 1616.99826 10.0% 410 980s
418 414 1615.97511 25 217 1470.55000 1616.99826 10.0% 412 986s
420 416 1615.79109 27 225 1470.55000 1616.99826 10.0% 413 990s
427 423 1615.59894 34 195 1470.55000 1616.99826 10.0% 412 996s
431 427 1615.48371 38 166 1470.55000 1616.99826 10.0% 410 1000s
438 434 1615.21606 45 144 1470.55000 1616.99826 10.0% 409 1005s
441 437 1614.64498 48 109 1470.55000 1616.99826 10.0% 410 1010s
445 441 1613.93977 52 112 1470.55000 1616.99826 10.0% 410 1015s
454 450 1612.83692 61 110 1470.55000 1616.99826 10.0% 406 1020s
462 458 1611.53636 68 103 1470.55000 1616.99826 10.0% 404 1025s
480 476 1606.01498 85 54 1470.55000 1616.99826 10.0% 394 1030s
objVal = 1470.55 & bestBound = 1617
objVal = 1470.55 & bestBound = 1617
495 491 1506.73333 95 10 1470.55000 1616.99826 10.0% 385 1038s
objVal = 1470.55 & bestBound = 1617
500 496 1489.84413 98 6 1470.55000 1616.99826 10.0% 381 1040s
objVal = 1470.55 & bestBound = 1617
objVal = 1470.55 & bestBound = 1617
objVal = 1470.55 & bestBound = 1617
501 495 cutoff 98 1470.55000 1616.99826 10.0% 381 1045s
objVal = 1470.55 & bestBound = 1617
objVal = 1470.55 & bestBound = 1617
503 497 1596.69407 4 237 1470.55000 1616.99826 10.0% 391 1059s
504 498 1596.66326 5 294 1470.55000 1616.99826 10.0% 391 1060s
506 500 1596.13939 7 231 1470.55000 1616.99826 10.0% 396 1068s
507 501 1595.93108 8 339 1470.55000 1616.99826 10.0% 402 1079s
508 502 1595.65134 9 209 1470.55000 1616.99826 10.0% 404 1088s
509 503 1595.59132 10 210 1470.55000 1616.99826 10.0% 405 1090s
511 505 1595.04184 12 209 1470.55000 1616.99826 10.0% 409 1100s
514 508 1595.19540 14 181 1470.55000 1616.99826 10.0% 412 1106s
Cutting planes:
Gomory: 3
MIR: 111
Flow cover: 340
RLT: 2
Lazy constraints: 5434
Explored 515 nodes (238900 simplex iterations) in 1108.01 seconds (1658.27 work units)
Thread count was 1 (of 16 available processors)
Solution count 3: 1470.55 704.76 670.95
Optimal solution found (tolerance 0.00e+00)
Best objective 1.470550000000e+03, best bound 1.470550000000e+03, gap 0.0000%
User-callback calls 73284, time in user-callback 185.07 sec
0
-
-
Gurobi Staff
Hi Amirhossein,
How is this possible?
I don't see anything impossible here (the result could be valid), but I think there's a chance the solver terminated incorrectly and the final solution is not actually an optimal one. If this was the case it is almost certainly due to numerical issues.
You should heed the warning in the log:
Warning: Model contains large bounds Consider reformulating model or setting NumericFocus parameter to avoid numerical issues.
- Riley
0 -
Please sign in to leave a comment.
Comments
1 comment