Attaining optimality without an incumbent solution
Answered
I am trying to solve a MIP where I minimize the absolute value of one of the decision variables. As a result, the minimum objective value of the MIP is 0. I'm coding the objective function as the sum of the positive and negative parts of the decision variables. In fact, even though it is not "mechanically obvious", I know that there exists a feasible solution whose objective value is 0; the purpose of solving the program is to find this solution.
After solving this MIP, I examined the log file (see below) and noticed two interesting features:
- Gurobi set the BestBd column to 0 from the first iteration all the way to the last.
- Gurobi solved the MIP without finding an incumbent solution.
My questions are as follows:
- How does Gurobi know that the best bound is 0?
- If there is no incumbent solution, does Gurobi do any pruning during the branch-and-bound process?
- Is it possible to specify an upper bound so that Gurobi can prune branches according to this upper bound instead of relying on an incumbent solution to prune the branches? The parameters BestObjStop and BestBdStop caught my attention but it isn't clear whether they are used only to terminate the program or if they are used for pruning as well.
I appreciate any help and guidance.
Best,
Omkar A. Katta
Here is the log:
Gurobi 9.1.1 (linux64, R) logging started Mon 23 Aug 2021 10:01:33 AM CDT
Gurobi Optimizer version 9.1.1 build v9.1.1rc0 (linux64)
Thread count: 48 physical cores, 48 logical processors, using up to 32 threads
Optimize a model with 5003 rows, 5009 columns and 27096 nonzeros
Model fingerprint: 0xb06fbff4
Variable types: 3011 continuous, 1998 integer (1998 binary)
Coefficient statistics:
Matrix range [4e-06, 2e+04]
Objective range [1e+00, 1e+00]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 4e+04]
Presolve time: 0.02s
Presolved: 5003 rows, 5009 columns, 26420 nonzeros
Variable types: 3011 continuous, 1998 integer (1998 binary)
Root relaxation: objective 0.000000e+00, 1865 iterations, 0.17 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 0.00000 0 32 - 0.00000 - - 0s
0 0 0.00000 0 35 - 0.00000 - - 0s
0 0 0.00000 0 35 - 0.00000 - - 1s
0 0 0.00000 0 62 - 0.00000 - - 1s
0 0 0.00000 0 55 - 0.00000 - - 2s
0 0 0.00000 0 55 - 0.00000 - - 2s
0 0 0.00000 0 54 - 0.00000 - - 2s
0 0 0.00000 0 52 - 0.00000 - - 3s
0 2 0.00000 0 52 - 0.00000 - - 20s
3 6 0.00000 2 334 - 0.00000 - 1542 30s
13 20 0.00000 4 370 - 0.00000 - 479 37s
23 38 0.00000 5 626 - 0.00000 - 679 51s
43 68 7843.41924 6 642 - 0.00000 - 857 65s
107 124 8324.60014 7 638 - 0.00000 - 632 76s
139 155 8556.45610 8 638 - 0.00000 - 604 80s
171 189 8634.33914 9 637 - 0.00000 - 553 97s
215 234 19457.6923 9 605 - 0.00000 - 732 105s
266 278 18124.7394 10 621 - 0.00000 - 755 114s
315 352 8975.43643 11 634 - 0.00000 - 767 128s
398 525 9039.87097 12 634 - 0.00000 - 745 139s
613 699 9875.51553 15 633 - 0.00000 - 619 153s
855 973 10310.3840 21 647 - 0.00000 - 570 170s
1203 1330 10486.4508 24 646 - 0.00000 - 539 189s
1660 1890 11239.6717 32 640 - 0.00000 - 515 214s
2453 2737 13702.7852 46 618 - 0.00000 - 458 248s
3866 4242 16167.6426 65 603 - 0.00000 - 384 290s
6175 6084 18846.2720 88 588 - 0.00000 - 305 335s
9265 7671 21024.5312 113 580 - 0.00000 - 257 377s
12423 7672 0.00000 190 52 - 0.00000 - 233 382s
12425 7673 0.00000 428 36 - 0.00000 - 233 390s
12435 7680 22886.3678 231 33 - 0.00000 - 233 629s
12436 7684 0.00000 13 104 - 0.00000 - 1.7 633s
12438 7687 0.00000 14 207 - 0.00000 - 1.8 638s
12442 7694 0.00000 15 253 - 0.00000 - 2.0 640s
12466 7732 7952.07533 17 485 - 0.00000 - 2.8 653s
12498 7749 infeasible 18 - 0.00000 - 5.2 665s
12530 7770 32755.4224 19 393 - 0.00000 - 7.6 677s
12562 7786 32755.4224 20 391 - 0.00000 - 8.1 686s
12594 7805 32755.4224 21 389 - 0.00000 - 10.0 693s
12626 7829 32755.4224 22 385 - 0.00000 - 10.7 707s
12670 7858 32755.4224 24 378 - 0.00000 - 15.1 724s
12719 7875 36565.6923 24 485 - 0.00000 - 20.6 739s
12763 7913 32755.4224 26 370 - 0.00000 - 26.0 747s
12819 7996 35733.6508 28 477 - 0.00000 - 30.9 758s
12934 8164 32755.4224 28 361 - 0.00000 - 35.9 771s
13194 8440 32755.4224 29 361 - 0.00000 - 45.0 789s
13657 8923 32755.4224 45 328 - 0.00000 - 60.8 817s
14486 9532 48405.9987 86 382 - 0.00000 - 81.2 857s
16007 10194 32755.4224 121 319 - 0.00000 - 110 909s
18338 11233 infeasible 199 - 0.00000 - 137 962s
21658 11665 0.00000 43 75 - 0.00000 - 153 1011s
25068 12221 0.00000 230 53 - 0.00000 - 160 1057s
28970 13020 infeasible 104 - 0.00000 - 160 1108s
33432 12776 infeasible 169 - 0.00000 - 160 1136s
36090 13714 infeasible 221 - 0.00000 - 160 1164s
39696 15475 0.00000 164 47 - 0.00000 - 156 1195s
43170 17573 infeasible 103 - 0.00000 - 154 1223s
47216 19258 infeasible 129 - 0.00000 - 150 1250s
50888 20793 infeasible 400 - 0.00000 - 147 1276s
54439 22016 11.22087 597 13 - 0.00000 - 145 1306s
57357 23523 infeasible 414 - 0.00000 - 145 1334s
61010 26459 0.00000 490 57 - 0.00000 - 143 1383s
67974 28186 infeasible 151 - 0.00000 - 140 1410s
72485 30581 35112.1168 182 360 - 0.00000 - 137 1439s
77768 32449 35112.1168 209 358 - 0.00000 - 134 1466s
82511 34380 infeasible 230 - 0.00000 - 131 1498s
87930 36433 35112.1168 248 365 - 0.00000 - 128 1526s
93226 41417 35112.1168 269 362 - 0.00000 - 125 1584s
105031 43594 35656.0377 324 373 - 0.00000 - 120 1606s
109821 45284 infeasible 358 - 0.00000 - 118 1628s
114340 47144 73649.4111 408 330 - 0.00000 - 117 1652s
118717 48965 545.62070 578 104 - 0.00000 - 116 1675s
123304 53027 1534.91175 588 71 - 0.00000 - 115 1723s
132924 54818 0.00000 104 59 - 0.00000 - 113 1747s
137886 56835 0.00000 125 55 - 0.00000 - 112 1769s
142982 59202 0.00000 158 62 - 0.00000 - 111 1797s
148369 61199 10138.4480 422 141 - 0.00000 - 109 1820s
153224 64365 0.00000 399 8 - 0.00000 - 108 1864s
162636 65773 infeasible 578 - 0.00000 - 106 1885s
167472 67265 infeasible 501 - 0.00000 - 105 1913s
171054 69281 infeasible 380 - 0.00000 - 105 1935s
175601 71613 infeasible 446 - 0.00000 - 104 1961s
180076 73644 0.00000 194 69 - 0.00000 - 104 1984s
184720 76377 0.00000 262 70 - 0.00000 - 104 2028s
192427 78703 infeasible 387 - 0.00000 - 103 2060s
197581 81171 0.00000 443 91 - 0.00000 - 102 2091s
203068 83131 0.00000 563 92 - 0.00000 - 101 2113s
208073 84856 0.00000 250 99 - 0.00000 - 101 2135s
212066 87498 0.00000 285 85 - 0.00000 - 101 2159s
217470 90131 0.00000 423 83 - 0.00000 - 100 2199s
224235 91688 3628.86929 89 227 - 0.00000 - 100 2224s
228160 94131 3628.86929 158 201 - 0.00000 - 100 2251s
233582 96426 3628.86929 284 206 - 0.00000 - 100 2278s
239265 98263 infeasible 531 - 0.00000 - 100 2302s
243892 100911 infeasible 479 - 0.00000 - 100 2328s
249233 103880 231.80493 506 77 - 0.00000 - 99.2 2365s
255434 106430 infeasible 402 - 0.00000 - 99.0 2392s
260714 108641 infeasible 505 - 0.00000 - 98.9 2416s
265427 110462 262.76729 358 101 - 0.00000 - 98.7 2442s
270282 112939 262.76729 416 97 - 0.00000 - 98.6 2467s
275382 115503 297.18928 328 134 - 0.00000 - 98.4 2496s
280649 118240 297.18928 522 147 - 0.00000 - 98.0 2535s
287305 120883 infeasible 501 - 0.00000 - 97.7 2560s
292867 123074 infeasible 375 - 0.00000 - 97.3 2583s
297748 125054 0.00000 462 29 - 0.00000 - 97.0 2605s
302486 126883 275.28168 483 136 - 0.00000 - 96.7 2627s
307809 128424 1042.06702 351 58 - 0.00000 - 96.2 2648s
312697 131448 1042.06702 515 60 - 0.00000 - 95.8 2683s
320426 133189 infeasible 562 - 0.00000 - 95.1 2706s
325146 134810 0.00000 264 102 - 0.00000 - 94.7 2731s
329218 136403 0.00000 303 100 - 0.00000 - 94.6 2757s
333544 138833 0.00000 373 99 - 0.00000 - 94.4 2787s
338423 140778 0.00000 443 114 - 0.00000 - 94.1 2818s
343293 143499 0.00000 503 113 - 0.00000 - 93.8 2857s
350088 145151 infeasible 515 - 0.00000 - 93.4 2884s
353013 145151 infeasible 470 - 0.00000 - 93.1 2885s
355118 146476 863.23451 500 95 - 0.00000 - 93.1 2911s
358881 148696 138.92962 439 87 - 0.00000 - 92.9 2943s
364304 151039 138.92962 528 91 - 0.00000 - 92.6 2972s
369945 153301 0.00000 423 8 - 0.00000 - 92.3 3002s
375593 156870 infeasible 527 - 0.00000 - 91.9 3043s
384315 159412 infeasible 456 - 0.00000 - 91.3 3066s
389707 161234 infeasible 533 - 0.00000 - 90.8 3089s
394414 163270 1777.16613 537 127 - 0.00000 - 90.4 3112s
399485 164939 0.88254 430 15 - 0.00000 - 90.0 3135s
404754 169133 infeasible 496 - 0.00000 - 89.6 3177s
414564 170601 infeasible 546 - 0.00000 - 88.7 3199s
419125 172407 0.00000 507 31 - 0.00000 - 88.4 3220s
424014 174172 infeasible 384 - 0.00000 - 88.0 3242s
429264 175947 0.00000 417 27 - 0.00000 - 87.5 3263s
434361 179068 0.00000 400 10 - 0.00000 - 87.1 3303s
443668 180236 infeasible 422 - 0.00000 - 86.4 3324s
448190 181689 10.43097 537 18 - 0.00000 - 86.1 3346s
452716 183094 infeasible 522 - 0.00000 - 85.8 3368s
457598 184292 0.00000 508 16 - 0.00000 - 85.5 3391s
461841 185704 infeasible 513 - 0.00000 - 85.3 3414s
466343 188667 0.00000 405 17 - 0.00000 - 85.2 3453s
474488 190550 0.00000 499 14 - 0.00000 - 84.7 3479s
479379 192636 1854.70213 375 106 - 0.00000 - 84.4 3504s
485003 194780 infeasible 386 - 0.00000 - 84.0 3528s
491150 196304 0.96320 392 11 - 0.00000 - 83.6 3550s
495648 199157 0.00000 346 71 - 0.00000 - 83.4 3588s
503382 201310 infeasible 557 - 0.00000 - 83.0 3613s
509224 202855 8541.53720 415 177 - 0.00000 - 82.7 3636s
514094 204378 8972.10985 477 137 - 0.00000 - 82.5 3658s
518910 206619 infeasible 471 - 0.00000 - 82.3 3682s
525088 209368 0.00000 510 13 - 0.00000 - 81.9 3719s
534249 211295 infeasible 503 - 0.00000 - 81.4 3736s
539482 212761 1.44341 493 12 - 0.00000 - 81.1 3754s
544241 214281 0.00000 549 62 - 0.00000 - 80.9 3774s
549221 215876 0.96250 521 12 - 0.00000 - 80.6 3795s
554066 218447 0.00000 581 18 - 0.00000 - 80.4 3831s
562627 220267 762.63074 467 125 - 0.00000 - 80.0 3852s
567225 221571 1168.96134 523 97 - 0.00000 - 79.8 3874s
571653 222803 383.94191 503 104 - 0.00000 - 79.7 3894s
575863 224416 46.09575 545 58 - 0.00000 - 79.6 3918s
579950 226441 0.00000 362 82 - 0.00000 - 79.6 3944s
584974 229681 251.28118 379 140 - 0.00000 - 79.4 3978s
593074 231293 0.00000 413 109 - 0.00000 - 79.1 4000s
597797 233115 10.93004 468 120 - 0.00000 - 78.9 4022s
603018 235160 infeasible 479 - 0.00000 - 78.7 4043s
608079 236747 infeasible 379 - 0.00000 - 78.4 4066s
612305 238242 infeasible 433 - 0.00000 - 78.3 4086s
617153 240606 infeasible 419 - 0.00000 - 78.2 4120s
623808 241909 0.00000 470 17 - 0.00000 - 78.0 4139s
627881 243686 infeasible 370 - 0.00000 - 77.9 4163s
633325 245927 infeasible 440 - 0.00000 - 77.8 4190s
639405 247445 0.00000 561 16 - 0.00000 - 77.6 4214s
644329 248930 0.84698 602 11 - 0.00000 - 77.4 4239s
648687 250771 0.00000 95 176 - 0.00000 - 77.4 4269s
653972 252474 0.00000 103 156 - 0.00000 - 77.3 4299s
658811 253686 0.00000 117 190 - 0.00000 - 77.3 4329s
662834 255734 infeasible 127 - 0.00000 - 77.4 4361s
667869 257581 0.00000 142 157 - 0.00000 - 77.4 4387s
672657 258771 0.00000 173 158 - 0.00000 - 77.4 4419s
676019 259765 0.62948 452 20 - 0.00000 - 77.6 4444s
679089 260659 infeasible 422 - 0.00000 - 77.9 4469s
681655 263779 0.00000 528 10 - 0.00000 - 78.2 4515s
*684495 4903 148 0.0000000 0.00000 0.00% 78.4 4521s
Cutting planes:
Gomory: 1
MIR: 20
Flow cover: 43
Inf proof: 10
Explored 688431 nodes (57063185 simplex iterations) in 4521.91 seconds
Thread count was 32 (of 48 available processors)
Solution count 1: 0
Optimal solution found (tolerance 1.00e-04)
Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0000%
0
-
Gurobi does find an incumbent solution to this problem after 4521 seconds, which turns out to be optimal:
*684495 4903 148 0.0000000 0.00000 0.00% 78.4 4521s
...
Explored 688431 nodes (57063185 simplex iterations) in 4521.91 seconds
Thread count was 32 (of 48 available processors)
Solution count 1: 0
Optimal solution found (tolerance 1.00e-04)
Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0000%It took Gurobi over an hour to find this solution. This new incumbent solution had an objective value of \( 0 \), which was equal to the dual bound of \( 0 \). As a result, Gurobi determined the solution was optimal.
1. How does Gurobi know that the best bound is 0?
The original dual bound comes from the optimal objective value of the root relaxation:
Root relaxation: objective 0.000000e+00, 1865 iterations, 0.17 seconds
This is the problem you get by relaxing the integrality restrictions on all of the variables and solving the resulting LP. The feasible region of this relaxed problem is larger than the feasible region of your original problem. As a result, the optimal objective value of the relaxed problem is a lower bound (for minimization problems) on the optimal objective value of your original problem.
2. If there is no incumbent solution, does Gurobi do any pruning during the branch-and-bound process?
If Gurobi solves a node LP and determines it is infeasible, then the node will be pruned.
3. Is it possible to specify an upper bound so that Gurobi can prune branches according to this upper bound instead of relying on an incumbent solution to prune the branches? The parameters BestObjStop and BestBdStop caught my attention but it isn't clear whether they are used only to terminate the program or if they are used for pruning as well.
No - the only way to do this is to pass the corresponding solution to Gurobi as a MIP start. The solution provides proof that the upper/primal bound is valid. If the solution is feasible, Gurobi will use it as the initial incumbent solution.
In your case, because the initial dual bound is \( 0 \), providing Gurobi with an incumbent solution with objective value \( 0 \) will be enough to solve the problem almost instantly.
0 -
Thank you, Eli, for your clear answers. I have a better understanding of how to read the log file now. I'll see what I can do with MIP starts.
Best,
Omkar A. Katta
0
Please sign in to leave a comment.
Comments
2 comments