HiGHS
HiGHS copied to clipboard
ERGO-Code
Inconsistent optimal solution for map10
While testing some changes I've been finding different objective values for map10 (https://miplib.zib.de/instance_details_map10.html) Given this is a MIPLIB 2017 benchmark instance we can't blame the instance
On c4012f564 (some recent latest commit) a valid optimal solution test.sol.txt gets separated by HighsTableauSeparator when computing a lifted binary cover cut. I can't seem to find any numerical error that would cause this from the cut logic. The tableau row (aggregation) before separation is violated by some tiny amount 1e-17, but that shouldn't necessarily cause the bug..... I'm putting it here to track the issue and because I've failed to fix it today.
Warning: It's a bit annoying to recreate because the size of the problem and wait time.
I confirm the inconsistent optimal solution for problem map10.
Using the HiGHS version 1.12, and solving the non scaled problem map10 the objective value -494.86468647 was obtained. The reference value reported in MIPLIB is -495.
However, the output provided by HiGHS version 1.12 contains the important WARNING messages:
WARNING: Problem has some excessively large row bounds WARNING: Consider scaling the bounds by 1e-2, or setting the user_bound_scale option to -7
The full output listing is provided below:
Running HiGHS 1.12.0 (git hash: n/a): Copyright (c) 2025 HiGHS under MIT licence terms
Set option solver to "simplex"
Set option parallel to "off"
Set option time_limit to 1200
Set option log_file to "HiGHS.log"
Set option mip_rel_gap to 0
MIP map10 has 328818 rows; 164547 cols; 549920 nonzeros; 146 integer variables (146 binary)
Coefficient ranges:
Matrix [1e+00, 1e+07]
Cost [1e+00, 1e+00]
Bound [1e+00, 1e+00]
RHS [1e+00, 9e+07]
WARNING: Problem has some excessively large row bounds
WARNING: Consider scaling the bounds by 1e-2, or setting the user_bound_scale option to -7
Presolving model
71338 rows, 37549 cols, 151723 nonzeros 0s
42027 rows, 18750 cols, 90532 nonzeros 0s
29265 rows, 14387 cols, 65005 nonzeros 0s
29198 rows, 14348 cols, 64871 nonzeros 0s
Presolve reductions: rows 29198(-299620); columns 14348(-150199); nonzeros 64871(-485049)
Solving MIP model with:
29198 rows
14348 cols (118 binary, 0 integer, 0 implied int., 14230 continuous, 0 domain fixed)
64871 nonzeros
Src: B => Branching; C => Central rounding; F => Feasibility pump; H => Heuristic;
I => Shifting; J => Feasibility jump; L => Sub-MIP; P => Empty MIP; R => Randomized rounding;
S => Solve LP; T => Evaluate node; U => Unbounded; X => User solution; Y => HiGHS solution;
Z => ZI Round; l => Trivial lower; p => Trivial point; u => Trivial upper; z => Trivial zero
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Src Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
J 0 0 0 0.00% -inf 0 Large 0 0 0 0 0.5s
R 0 0 0 0.00% -602.1761806 -147 309.64% 0 0 0 24967 4.5s
C 0 0 0 0.00% -585.9184287 -204 187.21% 1438 101 0 30284 8.8s
0 0 0 0.00% -580.4709407 -204 184.54% 3237 211 0 35720 14.1s
L 0 0 0 0.00% -579.6213263 -443 30.84% 3391 221 0 36689 30.2s
Symmetry detection completed in 0.0s
No symmetry present
15 0 1 0.01% -579.6213263 -443 30.84% 3392 183 8 256995 126.2s
25 1 6 0.01% -579.6213263 -443 30.84% 3401 183 45 266633 132.0s
39 3 11 0.02% -579.6213263 -443 30.84% 3411 183 111 277034 138.7s
50 3 15 0.02% -579.6213263 -443 30.84% 3418 183 141 286223 144.5s
62 5 22 0.03% -579.6213263 -443 30.84% 3432 183 181 295773 151.1s
70 5 26 0.03% -579.6213263 -443 30.84% 3443 183 219 304477 156.7s
77 5 30 0.05% -579.6213263 -443 30.84% 3451 183 258 313295 162.3s
81 6 33 0.13% -579.6213263 -443 30.84% 3457 183 275 323474 168.6s
90 6 34 0.13% -579.6213263 -443 30.84% 3459 183 290 340349 178.1s
101 20 41 0.13% -579.4737589 -443 30.81% 3473 183 323 350345 185.3s
L 101 14 41 0.13% -579.4737589 -454 27.64% 3519 197 323 350870 196.1s
112 14 42 0.18% -579.4737589 -454 27.64% 3521 197 346 429884 218.2s
120 14 47 0.43% -579.4737589 -454 27.64% 3530 197 366 436968 223.5s
123 14 49 0.72% -579.4737589 -454 27.64% 3536 197 384 445120 228.9s
128 15 51 1.01% -579.4737589 -454 27.64% 3540 197 403 457844 236.6s
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Src Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
134 15 53 1.12% -579.4737589 -454 27.64% 3549 197 413 471447 245.1s
142 15 58 1.45% -579.4737589 -454 27.64% 3560 197 433 487295 255.9s
152 16 64 3.16% -579.4737589 -454 27.64% 3567 197 455 500723 265.1s
157 16 65 3.26% -579.4737589 -454 27.64% 3571 197 470 513197 272.5s
162 16 69 4.33% -579.4737589 -454 27.64% 3579 197 483 522739 278.7s
178 17 71 4.72% -579.4737589 -454 27.64% 3586 197 512 552421 296.4s
197 24 79 4.78% -579.4737589 -454 27.64% 3598 197 546 566078 305.4s
L 201 16 82 5.05% -579.4737589 -487 18.99% 3997 218 556 567769 316.4s
208 16 83 5.44% -579.4737589 -487 18.99% 4000 218 576 626017 330.3s
229 19 92 5.71% -579.4737589 -487 18.99% 4010 218 612 632973 335.3s
242 19 98 5.93% -579.4737589 -487 18.99% 4019 218 649 640770 340.6s
260 20 107 6.64% -579.4737589 -487 18.99% 4029 218 683 650136 347.0s
284 22 119 8.35% -579.4737589 -487 18.99% 4044 218 739 663856 356.1s
288 22 122 13.82% -579.4737589 -487 18.99% 4047 218 748 676211 363.4s
295 22 123 13.87% -579.4737589 -487 18.99% 4051 218 770 687510 370.0s
305 31 127 14.51% -569.3367326 -487 16.91% 4056 218 786 704742 381.0s
314 31 128 14.52% -569.3367326 -487 16.91% 3945 260 799 740721 402.6s
326 36 135 15.44% -569.3367326 -487 16.91% 3953 260 815 747602 407.8s
336 35 137 15.88% -569.3367326 -487 16.91% 3927 259 841 770184 422.5s
354 36 144 16.18% -569.3367326 -487 16.91% 3934 259 861 778393 427.7s
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Src Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
T 371 29 153 16.67% -569.3367326 -491 15.95% 3947 259 904 783970 436.1s
412 39 168 17.20% -569.3367326 -491 15.95% 3971 259 945 803112 443.9s
429 50 173 17.27% -569.3367326 -491 15.95% 3981 259 963 812476 449.9s
437 49 174 17.32% -569.3367326 -491 15.95% 3913 245 991 840514 466.9s
453 51 183 18.39% -569.3367326 -491 15.95% 3922 245 1007 850420 473.2s
465 51 189 20.73% -569.3367326 -491 15.95% 3932 245 1029 865661 482.4s
470 49 194 23.62% -569.3367326 -491 15.95% 3594 269 1038 873912 487.9s
480 49 195 23.62% -569.3367326 -491 15.95% 3417 154 1049 884931 494.6s
505 56 208 23.63% -569.3367326 -491 15.95% 3298 156 1093 893087 500.4s
512 54 210 24.02% -569.3367326 -491 15.95% 3188 243 1122 965507 539.7s
523 56 216 29.88% -569.3367326 -491 15.95% 3194 243 1154 983525 550.6s
526 56 218 33.00% -569.3367326 -491 15.95% 3196 243 1166 992606 555.8s
536 56 219 33.00% -569.3367326 -491 15.95% 3197 243 1178 1008k 564.2s
546 58 226 33.13% -569.3367326 -491 15.95% 3208 243 1198 1018k 571.6s
549 59 228 33.62% -569.3367326 -491 15.95% 3213 243 1208 1030k 578.0s
T 551 26 230 35.62% -561.0954193 -494.8646865 13.38% 3215 243 1210 1034k 583.1s
558 24 233 35.83% -561.0954193 -494.8646865 13.38% 3645 248 1224 1056k 593.4s
579 23 243 36.02% -561.0954193 -494.8646865 13.38% 3515 171 1259 1080k 609.9s
600 27 253 36.05% -561.0954193 -494.8646865 13.38% 3527 171 1306 1087k 615.0s
621 27 262 36.10% -561.0954193 -494.8646865 13.38% 3536 171 1339 1095k 620.6s
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Src Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
633 27 271 36.34% -561.0954193 -494.8646865 13.38% 3412 183 1354 1103k 625.8s
646 26 273 36.34% -561.0954193 -494.8646865 13.38% 3485 215 1385 1146k 649.5s
661 29 283 37.47% -561.0954193 -494.8646865 13.38% 3495 215 1433 1153k 655.0s
670 30 287 39.42% -561.0954193 -494.8646865 13.38% 3500 215 1479 1182k 671.3s
678 31 291 40.16% -561.0954193 -494.8646865 13.38% 3506 215 1490 1192k 677.5s
681 31 292 40.55% -561.0954193 -494.8646865 13.38% 3507 215 1510 1203k 684.2s
692 32 294 40.94% -561.0954193 -494.8646865 13.38% 3511 215 1526 1220k 694.0s
703 36 300 41.00% -561.0954193 -494.8646865 13.38% 3517 215 1547 1228k 699.6s
706 36 302 41.14% -561.0954193 -494.8646865 13.38% 3521 215 1560 1241k 707.3s
713 36 304 41.25% -561.0954193 -494.8646865 13.38% 3531 215 1581 1257k 716.7s
719 36 309 41.44% -561.0954193 -494.8646865 13.38% 3539 215 1591 1264k 722.0s
723 36 310 41.46% -561.0954193 -494.8646865 13.38% 3545 215 1606 1273k 727.8s
731 35 315 41.64% -553.8870572 -494.8646865 11.93% 3356 233 1632 1299k 744.4s
737 35 319 41.69% -553.8870572 -494.8646865 11.93% 3178 165 1636 1307k 749.9s
739 33 321 41.69% -553.8870572 -494.8646865 11.93% 3118 168 1644 1315k 755.4s
744 32 322 41.71% -553.8870572 -494.8646865 11.93% 3147 201 1653 1383k 791.5s
755 34 328 41.96% -553.8870572 -494.8646865 11.93% 3153 201 1665 1390k 796.5s
762 33 330 42.02% -553.8870572 -494.8646865 11.93% 3187 215 1679 1399k 801.8s
775 33 339 42.38% -553.8870572 -494.8646865 11.93% 3196 215 1699 1408k 808.2s
782 31 341 43.16% -553.8870572 -494.8646865 11.93% 4170 277 1726 1447k 831.2s
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Src Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
791 32 346 48.63% -553.8870572 -494.8646865 11.93% 4175 277 1750 1461k 839.5s
798 34 349 53.32% -553.8870572 -494.8646865 11.93% 4181 277 1775 1472k 845.9s
804 33 353 62.71% -547.5987558 -494.8646865 10.66% 4197 309 1788 1489k 853.9s
812 32 358 62.82% -547.5987558 -494.8646865 10.66% 4031 293 1802 1496k 858.9s
814 31 359 63.60% -547.5987558 -494.8646865 10.66% 4150 324 1816 1508k 866.3s
818 30 362 64.39% -547.5987558 -494.8646865 10.66% 4156 324 1824 1521k 874.1s
819 29 363 67.51% -547.5987558 -494.8646865 10.66% 4223 338 1853 1534k 881.7s
821 27 365 67.55% -547.5987558 -494.8646865 10.66% 4225 338 1855 1544k 887.0s
825 25 367 68.33% -547.5987558 -494.8646865 10.66% 4053 290 1870 1624k 931.3s
835 25 372 69.51% -547.5987558 -494.8646865 10.66% 4060 290 1900 1646k 944.4s
844 26 374 69.90% -547.5987558 -494.8646865 10.66% 4064 290 1914 1657k 951.8s
852 26 380 70.38% -547.5987558 -494.8646865 10.66% 4071 290 1927 1664k 957.5s
856 24 384 70.77% -537.8758566 -494.8646865 8.69% 4068 294 1941 1674k 963.7s
862 20 388 71.14% -537.8758566 -494.8646865 8.69% 4260 270 1950 1700k 974.9s
872 18 393 71.82% -537.8758566 -494.8646865 8.69% 4074 283 1967 1719k 986.9s
879 17 398 72.94% -537.8758566 -494.8646865 8.69% 4247 300 1989 1736k 998.2s
889 17 403 73.53% -537.8758566 -494.8646865 8.69% 4255 300 2009 1750k 1007.5s
896 16 408 74.12% -531.8980979 -494.8646865 7.48% 4260 300 2021 1759k 1013.7s
898 15 409 80.37% -531.8980979 -494.8646865 7.48% 4351 261 2043 1772k 1019.6s
903 13 413 86.77% -530.3340045 -494.8646865 7.17% 4355 261 2048 1784k 1026.6s
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Src Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
906 10 416 86.91% -530.3340045 -494.8646865 7.17% 4358 261 2051 1797k 1033.9s
909 8 418 90.04% -530.3340045 -494.8646865 7.17% 4435 280 2077 1810k 1042.4s
914 7 421 92.38% -530.3340045 -494.8646865 7.17% 4456 294 2083 1817k 1047.7s
921 6 425 94.92% -530.3340045 -494.8646865 7.17% 4436 209 2110 1830k 1057.1s
933 5 431 95.36% -505.9552778 -494.8646865 2.24% 4417 217 2132 1839k 1063.3s
937 3 435 98.63% -505.9552778 -494.8646865 2.24% 4543 238 2159 1847k 1069.0s
943 0 439 99.80% -505.9552778 -494.8646865 2.24% 4517 251 2211 1854k 1074.5s
944 0 440 100.00% -494.8646865 -494.8646865 0.00% 4517 251 2212 1854k 1074.9s
Solving report
Model map10
Status Optimal
Primal bound -494.864686471
Dual bound -494.864686471
Gap 0%
P-D integral 235.801379436
Solution status feasible
-494.864686471 (objective)
0 (bound viol.)
4.04899226211e-14 (int. viol.)
0 (row viol.)
Timing 1074.87
Max sub-MIP depth 4
Nodes 944
Repair LPs 0
LP iterations 1854516
547884 (strong br.)
52232 (separation)
121647 (heuristics)
Model name : map10
Model status : Optimal
Simplex iterations: 1854516
IPM iterations: -1
Crossover iterations: -1
PDLP iterations: -1
QP ASM iterations: -1
Objective value : -4.9486468647e+02
HiGHS run time : 1074.88
Setting the HiGHS option user_bound_scale = -7 and solving the scaled problem map10 the objective value -495 was obtained, what is consistent with the reference value reported in the MIPLIB.
The full output listing is provided below:
Running HiGHS 1.12.0 (git hash: n/a): Copyright (c) 2025 HiGHS under MIT licence terms
Set option solver to "simplex"
Set option parallel to "off"
Set option time_limit to 72000
Set option user_bound_scale to -7
Set option log_file to "HiGHS.log"
Set option mip_rel_gap to 0
MIP map10 has 328818 rows; 164547 cols; 549920 nonzeros; 146 integer variables (146 binary)
Assessing costs and bounds after applying user_bound_scale option value of -7
Coefficient ranges:
Matrix [8e-03, 9e+04]
Cost [1e+00, 1e+00]
Bound [8e-03, 1e+00]
RHS [8e-03, 7e+05]
Presolving model
71338 rows, 37549 cols, 151723 nonzeros 0s
42027 rows, 18750 cols, 90532 nonzeros 0s
29265 rows, 14387 cols, 65005 nonzeros 0s
29198 rows, 14348 cols, 64871 nonzeros 0s
Presolve reductions: rows 29198(-299620); columns 14348(-150199); nonzeros 64871(-485049)
Solving MIP model with:
29198 rows
14348 cols (118 binary, 0 integer, 0 implied int., 14230 continuous, 0 domain fixed)
64871 nonzeros
Src: B => Branching; C => Central rounding; F => Feasibility pump; H => Heuristic;
I => Shifting; J => Feasibility jump; L => Sub-MIP; P => Empty MIP; R => Randomized rounding;
S => Solve LP; T => Evaluate node; U => Unbounded; X => User solution; Y => HiGHS solution;
Z => ZI Round; l => Trivial lower; p => Trivial point; u => Trivial upper; z => Trivial zero
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Src Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
J 0 0 0 0.00% -inf 0 Large 0 0 0 0 0.6s
R 0 0 0 0.00% -4.704501411 -1.1484375 309.64% 0 0 0 20402 4.8s
C 0 0 0 0.00% -4.565835316 -1.59375 186.48% 834 312 0 23833 8.7s
0 0 0 0.00% -4.527180479 -1.59375 184.06% 1272 256 0 28422 13.8s
L 0 0 0 0.00% -4.527180479 -3.1953125 41.68% 1294 244 0 28465 46.3s
Symmetry detection completed in 0.0s
No symmetry present
18 0 1 0.00% -4.527180479 -3.1953125 41.68% 1297 183 27 280084 164.1s
29 0 6 0.01% -4.527180479 -3.1953125 41.68% 1305 183 64 292493 173.2s
50 1 16 0.01% -4.527180479 -3.1953125 41.68% 1318 183 130 299250 178.8s
69 4 24 0.01% -4.527180479 -3.1953125 41.68% 1327 183 182 308244 185.4s
83 4 29 0.01% -4.527180479 -3.1953125 41.68% 1332 183 215 315586 190.6s
L 104 9 38 0.10% -4.526672452 -3.8046875 18.98% 1430 227 267 323028 236.4s
110 9 39 1.66% -4.526672452 -3.8046875 18.98% 1433 227 291 449054 260.2s
115 10 40 1.76% -4.526672452 -3.8046875 18.98% 1435 227 299 459689 268.5s
119 10 43 2.73% -4.526672452 -3.8046875 18.98% 1440 227 313 467064 275.0s
122 10 45 4.69% -4.526672452 -3.8046875 18.98% 1445 227 323 480295 284.8s
125 10 46 5.08% -4.526672452 -3.8046875 18.98% 1446 227 329 491814 292.6s
128 10 48 5.86% -4.526672452 -3.8046875 18.98% 1452 227 349 500215 298.7s
129 10 49 6.25% -4.526672452 -3.8046875 18.98% 1456 227 358 508808 304.8s
131 10 50 9.38% -4.526672452 -3.8046875 18.98% 1458 227 378 521381 313.2s
136 10 51 9.57% -4.526672452 -3.8046875 18.98% 1464 227 401 544040 328.1s
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Src Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
142 10 54 10.25% -4.526672452 -3.8046875 18.98% 1469 227 410 557677 338.1s
147 10 58 11.72% -4.526672452 -3.8046875 18.98% 1478 227 428 571156 347.6s
152 11 61 18.75% -4.526672452 -3.8046875 18.98% 1482 227 448 587583 358.7s
156 11 62 21.88% -4.526672452 -3.8046875 18.98% 1484 227 472 609992 373.0s
158 11 63 23.44% -4.526672452 -3.8046875 18.98% 1488 227 478 619575 379.4s
163 12 66 28.12% -4.526672452 -3.8046875 18.98% 1492 227 488 631756 387.9s
168 12 68 32.81% -4.526672452 -3.8046875 18.98% 1494 227 503 641676 394.4s
174 11 71 43.75% -4.526672452 -3.8046875 18.98% 1587 259 507 667871 412.0s
178 11 73 45.31% -4.526672452 -3.8046875 18.98% 1589 259 532 674763 417.1s
190 11 74 45.31% -4.526672452 -3.8046875 18.98% 1592 259 564 686568 425.8s
206 14 83 45.36% -4.526672452 -3.8046875 18.98% 1601 259 606 692531 430.9s
223 15 91 45.45% -4.526672452 -3.8046875 18.98% 1609 259 629 699916 436.7s
241 18 99 45.54% -4.526672452 -3.8046875 18.98% 1617 259 663 707352 442.6s
253 20 103 45.62% -4.526672452 -3.8046875 18.98% 1621 259 679 713346 447.8s
270 27 112 45.65% -4.445974488 -3.8046875 16.86% 1634 259 729 723085 455.4s
275 26 113 45.65% -4.445974488 -3.8046875 16.86% 1526 238 738 735502 464.2s
289 25 122 45.70% -4.445974488 -3.8046875 16.86% 1414 249 770 747042 473.9s
301 25 125 45.71% -4.445974488 -3.8046875 16.86% 1460 163 801 786976 499.8s
315 26 132 45.88% -4.445974488 -3.8046875 16.86% 1467 163 824 795918 506.6s
328 27 138 46.02% -4.445974488 -3.8046875 16.86% 1473 163 834 802680 512.2s
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Src Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
342 27 146 46.09% -4.445974488 -3.8046875 16.86% 1481 163 874 813882 521.2s
353 29 152 46.31% -4.445974488 -3.8046875 16.86% 1488 163 892 819875 526.4s
368 28 160 46.36% -4.445974488 -3.8046875 16.86% 1507 182 908 826451 532.7s
377 27 165 46.37% -4.445974488 -3.8046875 16.86% 1418 94 929 834345 539.5s
384 27 168 47.93% -4.445974488 -3.8046875 16.86% 1370 277 949 894987 584.8s
393 28 172 51.84% -4.445974488 -3.8046875 16.86% 1375 277 986 910246 595.8s
397 28 174 54.18% -4.445974488 -3.8046875 16.86% 1378 277 1010 923586 605.3s
406 29 176 54.98% -4.445974488 -3.8046875 16.86% 1381 277 1023 937996 615.3s
413 32 181 56.03% -4.378425337 -3.8046875 15.08% 1386 277 1036 943849 620.4s
418 31 182 56.03% -4.378425337 -3.8046875 15.08% 1477 354 1042 957277 630.7s
427 32 187 56.11% -4.378425337 -3.8046875 15.08% 1647 415 1056 967811 639.9s
433 30 191 59.25% -4.378425337 -3.8046875 15.08% 1654 282 1079 999410 663.8s
440 31 194 60.62% -4.378425337 -3.8046875 15.08% 1657 282 1087 1005k 668.9s
449 32 198 63.35% -4.378425337 -3.8046875 15.08% 1661 282 1107 1018k 679.0s
458 33 202 64.43% -4.378425337 -3.8046875 15.08% 1667 282 1117 1025k 685.0s
467 33 205 66.43% -4.378425337 -3.8046875 15.08% 1670 282 1127 1035k 692.5s
478 32 212 68.72% -4.378425337 -3.8046875 15.08% 1766 345 1155 1058k 712.0s
488 32 214 68.78% -4.378425337 -3.8046875 15.08% 1768 345 1165 1065k 717.7s
501 33 222 68.96% -4.378425337 -3.8046875 15.08% 1776 345 1183 1071k 722.8s
512 34 227 69.31% -4.378425337 -3.8046875 15.08% 1781 345 1194 1079k 728.9s
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Src Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
539 35 231 69.48% -4.378425337 -3.8046875 15.08% 1789 345 1222 1089k 737.1s
563 45 244 69.49% -4.378425337 -3.8046875 15.08% 1802 345 1262 1096k 743.0s
583 56 251 69.51% -4.378425337 -3.8046875 15.08% 1812 349 1299 1110k 754.3s
598 59 258 69.52% -4.378425337 -3.8046875 15.08% 1823 349 1320 1117k 761.7s
610 61 263 69.52% -4.378425337 -3.8046875 15.08% 1836 349 1353 1123k 767.3s
621 58 270 69.54% -4.378425337 -3.8046875 15.08% 1699 192 1378 1141k 781.7s
T 621 23 270 70.48% -4.378425337 -3.8671875 13.22% 1700 192 1379 1141k 783.4s
648 26 279 70.55% -4.378425337 -3.8671875 13.22% 1709 206 1417 1238k 849.9s
662 28 286 70.73% -4.378425337 -3.8671875 13.22% 1716 206 1440 1247k 857.8s
670 29 290 70.82% -4.378425337 -3.8671875 13.22% 1720 206 1458 1253k 862.8s
674 29 293 71.09% -4.378425337 -3.8671875 13.22% 1723 206 1467 1261k 869.3s
680 29 294 71.09% -4.378425337 -3.8671875 13.22% 1724 206 1483 1270k 877.5s
691 29 298 71.14% -4.378425337 -3.8671875 13.22% 1728 206 1496 1277k 884.6s
704 30 304 71.16% -4.378425337 -3.8671875 13.22% 1734 206 1505 1286k 892.0s
713 32 311 71.25% -4.378425337 -3.8671875 13.22% 1742 206 1523 1294k 900.0s
721 35 314 71.66% -4.378425337 -3.8671875 13.22% 1749 206 1554 1307k 910.6s
728 34 318 73.83% -4.342207215 -3.8671875 12.28% 1778 219 1585 1331k 929.0s
735 34 321 74.25% -4.342207215 -3.8671875 12.28% 1782 219 1594 1337k 934.9s
741 34 325 74.62% -4.342207215 -3.8671875 12.28% 1787 219 1606 1344k 941.0s
753 33 329 75.21% -4.324717996 -3.8671875 11.83% 1726 191 1637 1372k 960.3s
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Src Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
760 34 333 75.25% -4.324717996 -3.8671875 11.83% 1730 191 1650 1378k 965.3s
775 35 337 75.34% -4.324717996 -3.8671875 11.83% 1735 191 1674 1394k 977.6s
793 39 347 75.38% -4.324717996 -3.8671875 11.83% 1745 191 1689 1403k 986.0s
798 39 351 75.47% -4.324717996 -3.8671875 11.83% 1750 191 1696 1410k 992.2s
801 39 353 75.72% -4.324717996 -3.8671875 11.83% 1753 191 1711 1423k 1001.8s
808 39 354 75.72% -4.324717996 -3.8671875 11.83% 1758 191 1723 1435k 1010.8s
813 39 358 75.76% -4.324717996 -3.8671875 11.83% 1765 191 1732 1443k 1017.0s
817 39 361 75.82% -4.324717996 -3.8671875 11.83% 1771 191 1741 1449k 1022.1s
823 39 362 75.82% -4.324717996 -3.8671875 11.83% 1775 191 1751 1462k 1031.4s
828 39 367 75.91% -4.273936424 -3.8671875 10.52% 1782 194 1759 1468k 1036.9s
832 37 369 75.91% -4.273936424 -3.8671875 10.52% 1777 201 1769 1481k 1045.4s
836 35 373 76.32% -4.273936424 -3.8671875 10.52% 1781 201 1773 1490k 1052.6s
838 33 375 76.32% -4.273936424 -3.8671875 10.52% 1783 201 1778 1498k 1058.2s
840 32 376 76.32% -4.273936424 -3.8671875 10.52% 1846 178 1785 1507k 1066.8s
845 30 379 77.10% -4.273936424 -3.8671875 10.52% 1792 218 1810 1548k 1099.1s
848 30 380 77.30% -4.273936424 -3.8671875 10.52% 1794 218 1817 1556k 1104.9s
855 30 384 77.69% -4.273936424 -3.8671875 10.52% 1799 218 1830 1561k 1110.0s
867 31 390 78.28% -4.273936424 -3.8671875 10.52% 1806 218 1854 1573k 1120.4s
872 31 392 78.76% -4.273936424 -3.8671875 10.52% 1808 218 1864 1582k 1127.1s
878 31 395 79.08% -4.227819073 -3.8671875 9.33% 1813 238 1873 1593k 1134.0s
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Src Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
884 28 400 79.65% -4.227819073 -3.8671875 9.33% 1931 245 1890 1602k 1141.5s
890 25 405 80.08% -4.227819073 -3.8671875 9.33% 1936 245 1898 1609k 1147.8s
892 23 407 80.18% -4.227819073 -3.8671875 9.33% 1938 245 1900 1618k 1153.6s
894 22 408 81.74% -4.227819073 -3.8671875 9.33% 1941 333 1922 1627k 1160.9s
900 22 409 81.79% -4.227819073 -3.8671875 9.33% 1943 333 1928 1634k 1166.1s
912 22 414 82.53% -4.227819073 -3.8671875 9.33% 1949 333 1940 1642k 1172.1s
919 22 421 83.31% -4.198338457 -3.8671875 8.56% 1936 347 1952 1650k 1179.8s
921 20 423 83.70% -4.198338457 -3.8671875 8.56% 1938 347 1954 1664k 1190.9s
923 18 425 83.94% -4.198338457 -3.8671875 8.56% 1940 347 1956 1671k 1196.1s
929 16 427 83.95% -4.198338457 -3.8671875 8.56% 1930 377 1969 1702k 1220.6s
935 14 433 84.01% -4.198338457 -3.8671875 8.56% 1936 377 1978 1710k 1227.2s
938 14 434 84.41% -4.198338457 -3.8671875 8.56% 1952 243 2000 1781k 1277.0s
945 14 436 84.82% -4.198338457 -3.8671875 8.56% 1954 243 2012 1790k 1283.6s
949 14 440 85.14% -4.088776695 -3.8671875 5.73% 1958 243 2017 1797k 1289.2s
952 13 442 85.16% -4.088776695 -3.8671875 5.73% 1944 262 2020 1804k 1294.5s
956 12 443 85.35% -4.088776695 -3.8671875 5.73% 1919 303 2035 1819k 1305.2s
963 11 448 86.74% -4.088776695 -3.8671875 5.73% 1947 212 2045 1831k 1315.1s
968 10 450 86.82% -4.088776695 -3.8671875 5.73% 1942 247 2051 1844k 1324.4s
975 9 454 87.26% -4.088776695 -3.8671875 5.73% 1968 283 2058 1859k 1336.4s
980 8 458 88.33% -4.088776695 -3.8671875 5.73% 1953 257 2065 1867k 1344.1s
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Src Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
985 6 461 88.87% -4.088776695 -3.8671875 5.73% 1947 272 2068 1879k 1353.4s
992 5 465 90.72% -4.088776695 -3.8671875 5.73% 1994 360 2079 1894k 1364.7s
1000 4 470 95.80% -4.061534502 -3.8671875 5.03% 2082 301 2105 1909k 1376.3s
1008 3 475 99.32% -3.95564372 -3.8671875 2.29% 2179 369 2117 1921k 1385.9s
1009 2 476 99.51% -3.95564372 -3.8671875 2.29% 2198 380 2146 1928k 1391.3s
1011 0 478 100.00% -3.8671875 -3.8671875 0.00% 2164 399 2176 1933k 1395.6s
Solving report
Model map10
Status Optimal
Primal bound -3.8671875
Dual bound -3.8671875
Gap 0%
P-D integral 315.314613959
Solution status feasible
-3.8671875 (objective)
0 (bound viol.)
2.68976155565e-13 (int. viol.)
0 (row viol.)
Timing 1395.60
Max sub-MIP depth 2
Nodes 1011
Repair LPs 0
LP iterations 1933410
550022 (strong br.)
39406 (separation)
174487 (heuristics)
Model name : map10
Model status : Optimal
Simplex iterations: 1933410
IPM iterations: -1
Crossover iterations: -1
PDLP iterations: -1
QP ASM iterations: -1
Objective value : -3.8671875000e+00
HiGHS run time : 1395.61
After solving the user-scaled model, the unscaled solution has objective value -495
Similar behavior of HiGHS was reported for the benchmark model mas76 from the MIPLIB.
See Issue #2653
@romz-pl That's a great example for advocating the use of user_bound_scale!
The instance isn't that poorly scaled though, and I want people to be confident that default HiGHS is returning the correct result. The issue with mas76 also needs to be fixed (I'd just classify it as less critical than this one).
@Opt-Mucca I completely agree with you. The default HiGHS options should produce the correct results :-)
But how can you achieve that? Would you like to scale the problem by default?
@romz-pl We need to determine exactly why the optimal solution is removed from the search procedure. Eventually it will be narrowed down to some logical flaw in the code, e.g. some epsilon was not tight enough or some global change was not buffered correctly, and we then change the code.
It's a complicated process, especially so for instances that aren't small (take long to reproduce) and which don't trigger some safety asserts.
Automatic scaling of the problem would be a cool and helpful feature, but it doesn't fix the underlying bug.