Why my Best objective value is greater than the best known?
AnsweredRecently I was solving a quadratic model with Gurobi. According to the log, I found that my best objective function value is 2314681.25, which is equal to the result of a heuristic program I developed.
However, what is interesting and confusing is that I found in the logs (see below) that the last Objective Bounds value is equal to 2314681.02, which is smaller than the best objective function value 2314681.25.
According to the manual MIPLogging (see https://www.gurobi.com/documentation/10.0/refman/refman.html )
The Objective Bounds section provides information on the best known objective value for a feasible solution (i.e., the objective value of the current incumbent)
So which of the above values is the optimal one? Why is this smaller value not optimal?
Thank you for your help.
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 2090945.02 0 3124 - 2090945.02 - - 31s
H 0 0 2566933.9985 2090945.02 18.5% - 41s
H 0 0 2528918.9260 2090945.02 17.3% - 42s
0 0 2219908.69 0 1422 2528918.93 2219908.69 12.2% - 81s
H 0 0 2324250.2586 2219908.69 4.49% - 102s
0 0 2258656.78 0 979 2324250.26 2258656.78 2.82% - 106s
0 0 2258656.78 0 979 2324250.26 2258656.78 2.82% - 106s
0 0 2263336.13 0 1052 2324250.26 2263336.13 2.62% - 112s
0 0 2263336.13 0 3630 2324250.26 2263336.13 2.62% - 131s
H 0 0 2322493.6454 2263336.13 2.55% - 133s
0 0 2275948.28 0 1840 2322493.65 2275948.28 2.00% - 155s
H 0 0 2320248.0735 2275948.28 1.91% - 164s
0 0 2284998.09 0 1053 2320248.07 2284998.09 1.52% - 167s
0 0 2286790.04 0 1204 2320248.07 2286790.04 1.44% - 168s
0 0 2286830.72 0 1139 2320248.07 2286830.72 1.44% - 168s
0 0 2292840.90 0 947 2320248.07 2292840.90 1.18% - 171s
0 0 2292840.90 0 4056 2320248.07 2292840.90 1.18% - 187s
H 0 0 2319498.0793 2292840.90 1.15% - 188s
0 0 2292840.90 0 1948 2319498.08 2292840.90 1.15% - 223s
H 0 0 2319355.9139 2292840.90 1.14% - 225s
0 0 2292840.90 0 1094 2319355.91 2292840.90 1.14% - 230s
0 0 2292840.90 0 1055 2319355.91 2292840.90 1.14% - 233s
0 0 2292877.36 0 831 2319355.91 2292877.36 1.14% - 234s
0 0 2294104.07 0 404 2319355.91 2294104.07 1.09% - 237s
H 0 0 2316750.4763 2294104.07 0.98% - 238s
0 0 2294104.07 0 384 2316750.48 2294104.07 0.98% - 238s
0 0 2294124.73 0 393 2316750.48 2294124.73 0.98% - 241s
H 0 0 2315212.1015 2294124.73 0.91% - 242s
0 0 2294124.73 0 390 2315212.10 2294124.73 0.91% - 242s
0 0 2294601.03 0 2140 2315212.10 2294601.03 0.89% - 250s
H 0 0 2315026.0108 2294601.03 0.88% - 251s
0 0 2294626.01 0 2064 2315026.01 2294626.01 0.88% - 252s
0 0 2295110.02 0 2014 2315026.01 2295110.02 0.86% - 256s
0 0 2295110.02 0 1199 2315026.01 2295110.02 0.86% - 259s
H 0 0 2315013.3276 2295110.02 0.86% - 262s
H 0 0 2314996.1560 2295110.02 0.86% - 267s
0 0 2295110.02 0 3975 2314996.16 2295110.02 0.86% - 285s
H 0 0 2314992.9001 2295110.02 0.86% - 286s
H 0 0 2314830.7572 2295110.02 0.85% - 301s
0 0 2295110.02 0 1856 2314830.76 2295110.02 0.85% - 330s
0 0 2295110.02 0 1309 2314830.76 2295110.02 0.85% - 335s
0 0 2295110.02 0 578 2314830.76 2295110.02 0.85% - 336s
0 0 2295110.02 0 1502 2314830.76 2295110.02 0.85% - 341s
H 0 0 2314791.7664 2295110.02 0.85% - 342s
0 0 2295110.02 0 1700 2314791.77 2295110.02 0.85% - 345s
0 0 2295110.02 0 719 2314791.77 2295110.02 0.85% - 349s
H 0 0 2314696.9683 2295110.02 0.85% - 351s
0 0 2295110.02 0 822 2314696.97 2295110.02 0.85% - 352s
0 0 2295499.34 0 2061 2314696.97 2295499.34 0.83% - 360s
H 0 0 2314685.3334 2295499.34 0.83% - 361s
0 0 2295812.72 0 1803 2314685.33 2295812.72 0.82% - 362s
0 0 2296188.44 0 853 2314685.33 2296188.44 0.80% - 365s
0 0 2296337.27 0 938 2314685.33 2296337.27 0.79% - 368s
0 0 2296391.81 0 2190 2314685.33 2296391.81 0.79% - 373s
0 0 2296391.81 0 1351 2314685.33 2296391.81 0.79% - 377s
H 0 2 2314683.4821 2296391.81 0.79% - 389s
0 2 2296391.81 0 1311 2314683.48 2296391.81 0.79% - 389s
1 4 2296521.95 1 722 2314683.48 2296424.57 0.79% 5244 390s
H 31 38 2314682.6564 2296587.08 0.78% 554 393s
H 33 38 2314681.2478 2296587.08 0.78% 521 393s
68 75 2300629.19 11 368 2314681.25 2296587.08 0.78% 258 396s
198 222 2301364.74 33 351 2314681.25 2296587.08 0.78% 107 400s
453 483 2302427.96 70 349 2314681.25 2296587.08 0.78% 56.9 405s
760 804 2303438.84 119 347 2314681.25 2296587.08 0.78% 43.8 410s
1001 1021 2303738.15 169 350 2314681.25 2296587.08 0.78% 36.4 416s
1277 1374 2303890.73 217 357 2314681.25 2296587.08 0.78% 30.7 420s
1938 2081 2304398.15 317 356 2314681.25 2296587.08 0.78% 23.1 426s
2254 2378 2305313.97 375 341 2314681.25 2296587.08 0.78% 21.4 431s
2726 2895 2305766.29 446 681 2314681.25 2296587.08 0.78% 19.4 435s
3042 3193 2305777.15 462 481 2314681.25 2296587.08 0.78% 18.4 443s
3218 3382 2305809.05 469 524 2314681.25 2296587.08 0.78% 17.8 446s
3753 3936 2306423.43 576 278 2314681.25 2296587.08 0.78% 16.6 452s
4122 4295 2307057.66 663 273 2314681.25 2296587.08 0.78% 16.1 456s
4384 4578 2307715.53 707 268 2314681.25 2296587.08 0.78% 15.6 460s
4884 5082 2308666.88 790 272 2314681.25 2296587.08 0.78% 14.4 465s
5438 5743 2309671.03 873 267 2314681.25 2296587.08 0.78% 13.7 470s
6211 6510 2311035.86 993 253 2314681.25 2296587.08 0.78% 12.5 477s
6554 6511 2305806.02 330 10616 2314681.25 2296587.08 0.78% 12.0 534s
6556 6512 2311247.92 1013 4800 2314681.25 2296587.08 0.78% 12.0 577s
6557 6513 2306463.40 28 2530 2314681.25 2296587.08 0.78% 12.0 616s
6558 6514 2302095.20 413 2330 2314681.25 2296587.08 0.78% 12.0 629s
6559 6514 2305503.58 134 2371 2314681.25 2296587.08 0.78% 12.0 631s
6561 6516 2300309.02 6 2721 2314681.25 2296587.08 0.78% 12.0 635s
6567 6520 2305816.95 304 2919 2314681.25 2296587.08 0.78% 12.0 640s
6570 6522 2307849.36 820 2751 2314681.25 2296587.08 0.78% 12.0 648s
6572 6523 2306441.01 329 2864 2314681.25 2296587.08 0.78% 12.0 650s
6576 6526 2305696.38 236 2951 2314681.25 2296587.08 0.78% 12.0 656s
6579 6528 2312359.20 1043 3335 2314681.25 2296587.08 0.78% 12.0 660s
6582 6530 2303711.90 19 3366 2314681.25 2296587.08 0.78% 12.0 668s
6583 6530 2311339.13 1025 3348 2314681.25 2296587.08 0.78% 12.0 670s
6584 6531 2303031.32 87 3346 2314681.25 2296587.08 0.78% 12.0 675s
6588 6534 2306645.85 567 3609 2314681.25 2296587.08 0.78% 12.0 681s
6593 6537 2306169.61 230 3925 2314681.25 2296587.08 0.78% 12.0 688s
6594 6538 2302813.47 501 3938 2314681.25 2296587.08 0.78% 12.0 690s
6596 6539 2301134.53 22 3933 2314681.25 2296587.08 0.78% 12.0 695s
6597 6540 2304572.29 328 3939 2314681.25 2296587.08 0.78% 12.0 700s
6598 6540 2311360.82 951 3931 2314681.25 2296587.08 0.78% 12.0 706s
6599 6541 2304450.24 394 3933 2314681.25 2296587.08 0.78% 12.0 710s
6600 6542 2307014.35 515 3924 2314681.25 2296587.08 0.78% 12.0 716s
6601 6542 2307063.33 525 3921 2314681.25 2296587.08 0.78% 12.0 721s
6602 6543 2303577.04 184 3933 2314681.25 2296587.08 0.78% 11.9 728s
6604 6544 2302745.83 492 3928 2314681.25 2296587.08 0.78% 11.9 733s
6606 6546 2304713.37 671 3935 2314681.25 2296587.08 0.78% 11.9 738s
6610 6548 2312353.86 1036 3941 2314681.25 2296587.08 0.78% 11.9 744s
6611 6549 2303295.78 542 3944 2314681.25 2296587.08 0.78% 11.9 750s
6612 6550 2305826.57 480 3947 2314681.25 2296587.08 0.78% 11.9 755s
6613 6550 2310529.91 948 3947 2314681.25 2296587.08 0.78% 11.9 762s
6614 6551 2300709.69 157 3947 2314681.25 2296587.08 0.78% 11.9 766s
6615 6552 2311648.21 1047 3947 2314681.25 2296589.80 0.78% 11.9 823s
H 6615 6225 2314681.1041 2296589.80 0.78% 25.1 825s
6618 6230 2296589.80 12 3929 2314681.10 2296589.80 0.78% 26.6 833s
6622 6233 2296589.80 13 3923 2314681.10 2296589.80 0.78% 26.9 835s
6662 6249 2296589.80 16 2969 2314681.10 2296589.80 0.78% 29.7 840s
6711 6254 2296589.80 20 708 2314681.10 2296589.80 0.78% 31.5 851s
H 6717 5940 2314681.0602 2296589.80 0.78% 31.8 851s
6771 5989 2296987.74 22 1095 2314681.06 2296589.80 0.78% 33.1 855s
7004 6082 2297306.47 36 549 2314681.06 2296589.80 0.78% 34.2 860s
7147 6174 2299588.37 47 551 2314681.06 2296589.80 0.78% 34.9 865s
7478 6428 2298376.27 71 525 2314681.06 2296589.80 0.78% 34.2 870s
H 7721 6255 2314681.0236 2296589.80 0.78% 33.5 873s
7865 6398 2298625.62 93 486 2314681.02 2296589.80 0.78% 33.2 876s
8048 6478 2298858.32 110 498 2314681.02 2296589.80 0.78% 33.0 880s
8326 6709 2299170.76 127 477 2314681.02 2296589.80 0.78% 32.5 885s
8653 6917 2299577.84 148 456 2314681.02 2296589.80 0.78% 32.1 890s
8994 7144 2300427.98 172 436 2314681.02 2296589.80 0.78% 31.5 896s
9258 7347 2301431.43 188 454 2314681.02 2296589.80 0.78% 31.3 900s
9591 7562 2301760.28 210 432 2314681.02 2296589.80 0.78% 30.9 905s
10137 7732 2302959.59 239 636 2314681.02 2296589.80 0.78% 30.3 912s
10318 7943 2307354.17 247 653 2314681.02 2296589.80 0.78% 30.7 917s
10471 8017 2305615.04 259 426 2314681.02 2296589.80 0.78% 31.0 920s
10801 8326 2306214.27 285 421 2314681.02 2296589.80 0.78% 31.1 926s
11305 8658 2307604.54 326 401 2314681.02 2296589.80 0.78% 30.2 932s
11579 8867 2307915.33 347 394 2314681.02 2296589.80 0.78% 29.9 936s
12221 9322 2309123.71 392 372 2314681.02 2296589.80 0.78% 28.8 943s
12570 9460 2309010.72 417 377 2314681.02 2296589.80 0.78% 28.4 977s
12839 9561 2309460.14 445 366 2314681.02 2296589.80 0.78% 28.2 983s
13048 9801 2309600.55 465 356 2314681.02 2296589.80 0.78% 28.1 991s
13384 10133 2310085.50 498 358 2314681.02 2296589.80 0.78% 28.2 998s
13828 10074 2311901.66 538 343 2314681.02 2296589.80 0.78% 27.8 1000s
Cutting planes:
Gomory: 1
Cover: 2
Implied bound: 975
MIR: 183
StrongCG: 2
Flow cover: 634
Zero half: 31
RLT: 353
Relax-and-lift: 5
BQP: 5
Explored 13917 nodes (768046 simplex iterations) in 1000.36 seconds (618.60 work units)
Thread count was 12 (of 12 available processors)
Solution count 10: 2.31468e+06 2.31468e+06 2.31468e+06 ... 2.315e+06
Time limit reached
Best objective 2.314681247625e+06, best bound 2.296589796396e+06, gap 0.7816%
-
-
Gurobi Staff
Hi Runfeng,
However, what is interesting and confusing is that I found in the logs (see below) that the last Objective Bounds value is equal to 2314681.02, which is smaller than the best objective function value 2314681.25.
Please note that 2314681.02 is not an objective bound but the currently best feasible point found (also called incumbent). It is possible that the solution found by Gurobi is a bit better than what you found with your heuristic, because Gurobi can exploit optimization tolerances FeasibilityTol, IntFeasTol, i.e., it is possible that the final solution found by Gurobi violates the model's constraints by a bit (up to the given tolerances). This is possible for bigger and more complex models. Additionally, please note that the optimal objective value differs from your heuristic solution in the 8th overall digit, which is very likely given the numerical complexity of the algorithms.
To check constraint and bound violations, you can call the printStats method, or check the solution quality attributes of the optimal solution. In particular, the values of the attributes MaxVio, BoundVio, and ConstrVio are of interest.
Best regards,
Jaromił0 -
-
Hi Jaromił,
Thank you very much for answering my questions.
Here is my understanding：
In the above question, 2314681.02 is the best feasible point Gurobi found. However, although this point is the best, it is in fact a little bit infeasible due to the optimization tolerances parameter that you have mentioned. Therefore, due to the infeasibility (violates the model's constraints by a bit), 2314681.02 was not adopted as the optimal objective function value. Meanwhile, the value 2314681.25 is a perfectly feasible objective value, so it is the result returned by Gurobi in the end of the log.Am I understanding correctly?
Thank you again for taking time out of your busy schedule to answer my question, which is very important for a novice!
Kind regards,
Runfeng
0 -
-
-
Hi Runfeng,
In the above question, 2314681.02 is the best feasible point Gurobi found. However, although this point is the best, it is in fact a little bit infeasible due to the optimization tolerances parameter that you have mentioned. Therefore, due to the infeasibility (violates the model's constraints by a bit), 2314681.02 was not adopted as the optimal objective function value. Meanwhile, the value 2314681.25 is a perfectly feasible objective value, so it is the result returned by Gurobi in the end of the log.
Am I understanding correctly?
Now I see what exactly you mean, sorry for the confusion. In addition to what I said, Gurobi performs as so-called "clean-up phase", where it tries to "polish the solution point", i.e., decrease constraint and bound violations while not deteriorating the optimal objective value. In this particular example, the objective value got a bit worse but only in the 8th overall digit which is completely acceptable within the default tolerances.
Best regards,
Jaromił0 -
-
Hi Jaromił,
Sorry, I am still confused about this problem.
Based on the 393rd second of the log, gurobi obtains the feasible solution 2314681.2478.
In the next process, gurobi looks for other possible better points.
Then at the 873rd second, gurobi gets the value 2314681.0236.H 33 38 2314681.2478 2296587.08 0.78% 521 393s
H 7721 6255 2314681.0236 2296589.80 0.78% 33.5 873s
Best objective 2.314681247625e+06, best bound 2.296589796396e+06, gap 0.7816%I know this is a very small difference.
But why did Gurobi accept 2314681.2478 as the return value instead of 2314681.0236? Apparently 2314681.0236 is smaller.It seems that "clean-up phase" did not deteriorate the value (2314681.2478 at the 393s) for a minimize problem, instead gurobi got a better one (2314681.0236 at the 873s).
Do these two values correspond to the same feasible point? I guess so. Gurobi found a point with objective value 2314681.2478. Then, the clean-up phase ''delete'' some constraint and and bound violations, which results a better solution 2314681.0236. But such a gap is irrelevant, then gurobi returns a worse one (2314681.2478).
Thank you for your answer, it is a pleasure to communicate with you.
Best regards,
Runfeng0 -
-
-
Hi Runfeng,
But why did Gurobi accept 2314681.2478 as the return value instead of 2314681.0236?
The two feasible points are found at different points in time. Gurobi first finds a feasible solution point with value 2314681.2478 and ~500 seconds, a different heuristic finds a slightly better point with objective value 2314681.0236.
It seems that "clean-up phase" did not deteriorate the value (2314681.2478 at the 393s) for a minimize problem, instead gurobi got a better one (2314681.0236 at the 873s).
The clean-up phase is called only once at the end of the optimization process, i.e., between the last line of the B&B algorithm and the output about optimal termination.
Do these two values correspond to the same feasible point?
No, see my next point.
Gurobi found a point with objective value 2314681.2478. Then, the clean-up phase ''delete'' some constraint and and bound violations, which results a better solution 2314681.0236. But such a gap is irrelevant, then gurobi returns a worse one (2314681.2478).
No, this is not how this works. Gurobi finds a feasible solution point with value 2314681.2478 at 393 seconds. It then finds a slightly better solution point with value 2314681.0236. After some termination criteria is reached (in this case time limit is hit), Gurobi takes the solution point with objective value 2314681.0236 and starts a "clean-up phase" where it tries it improve constraint/bound violations. In this phase the objective value is slightly deteriorated to value 2314681.247625.
Note that the final feasible point \(x\) with final objective value 2314681.247625 is (slightly) different from the feasible point \(y\) with objective value 2314681.0236 seen at 873 seconds because \(y\) has been "cleaned up", i.e., it has lower violations compared to \(x\). \(x\) is not equal to the point found at 393 seconds.
I hope this made it more clear.
Best regards,
Jaromił0 -
-
Hi Jaromił,
Thanks for your patient answer, now I finally understand how it works！
Best regards,
Runfeng
0 -
Please sign in to leave a comment.
Comments
6 comments