ERGO-Code
Incorrect Best Bound when random_seed is set.
Hello again. This issue is fairly scary in that I, and assumably everyone else, expects that the Best Bounds are going to always be truthful. In this case they are not. This is particularly scary when, for reproducibility random_seed is set during development.
Consider the following two outputs (first without and second with random_seed) and note the final presolves and the BestBound values.
highs viz_model.mps
Running HiGHS 1.7.2 (git hash: 00e812dab): Copyright (c) 2024 HiGHS under MIT licence terms
Number of BV entries in BOUNDS section is 60239
Number of UI entries in BOUNDS section is 50508
MIP viz_model has 259400 rows; 110747 cols; 651106 nonzeros; 110747 integer variables
Coefficient ranges:
Matrix [1e+00, 2e+01]
Cost [1e+00, 3e+00]
Bound [1e+00, 2e+01]
RHS [1e+00, 2e+01]
Presolving model
166797 rows, 86937 cols, 426946 nonzeros 0s
131595 rows, 58866 cols, 335886 nonzeros 0s
87320 rows, 58711 cols, 247002 nonzeros 0s
82499 rows, 55421 cols, 236060 nonzeros 1s
Objective function is integral with scale 1
Solving MIP model with:
82499 rows
55421 cols (28530 binary, 26891 integer, 0 implied int., 0 continuous)
236060 nonzeros
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
0 0 0 0.00% 411 inf inf 0 0 0 0 2.1s
0 0 0 0.00% 425.6462312 inf inf 0 0 3 2567 2.5s
0 0 0 0.00% 431.9604451 inf inf 2510 222 139 6737 7.6s
0 0 0 0.00% 432.9199454 inf inf 2697 267 167 11511 12.6s
0 0 0 0.00% 433.9754869 inf inf 2152 328 184 17538 18.1s
0 0 0 0.00% 434.9020846 inf inf 1880 351 193 23230 23.3s
^C
highs --random_seed 42 viz_model.mps
Running HiGHS 1.7.2 (git hash: 00e812dab): Copyright (c) 2024 HiGHS under MIT licence terms
Number of BV entries in BOUNDS section is 60239
Number of UI entries in BOUNDS section is 50508
MIP viz_model has 259400 rows; 110747 cols; 651106 nonzeros; 110747 integer variables
Coefficient ranges:
Matrix [1e+00, 2e+01]
Cost [1e+00, 3e+00]
Bound [1e+00, 2e+01]
RHS [1e+00, 2e+01]
Presolving model
166797 rows, 86937 cols, 426946 nonzeros 0s
131595 rows, 58866 cols, 335886 nonzeros 0s
87320 rows, 58711 cols, 247002 nonzeros 0s
82472 rows, 55407 cols, 235841 nonzeros 1s
Objective function is integral with scale 1
Solving MIP model with:
82472 rows
55407 cols (28520 binary, 26887 integer, 0 implied int., 0 continuous)
235841 nonzeros
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
0 0 0 0.00% 414 inf inf 0 0 0 0 2.1s
0 0 0 0.00% 437.1700407 inf inf 0 0 1 5007 3.3s
0 0 0 0.00% 444.4279977 inf inf 2848 235 212 11426 8.7s
0 0 0 0.00% 445.4705785 inf inf 3467 264 225 17652 14.3s
^C
When run to completion (just over an hour on my Ryzen 5700G), the first finds the optimal answer (443) and the second arrives at 459! With presolve off and the random_seed set the incorrect BestBound was still used.
See discord for more info on how this was found by pure luck and almost not found prior to several days worth of processing with random_seed set (for reproducibilty).
Hello again. This issue is fairly scary in that I, and assumably everyone else, expects that the Best Bounds are going to always be truthful.
It's a reasonable assumption, and almost always correct with our MIP solver. However, as with any solver, there's no guarantee.
I'm running highs --random_seed 42 viz_model.mps, but it's found the optimal solution of 443.
Quite a few bug fixes and developments have been made since v1.7.2 (we're now on v1.10.0) and it's possible that whatever caused the error in your case has been fixed. What's more likely is that a change in behaviour as a result of the modifications means that the error is not exposed.
Given how long this problem takes to run, I can't see us investigating this further
Ok on the closure, but it literally took 8.7 seconds to see the error in the log so I don't think the time to investigate is either tied to the time to solve or that it is the factor.
I'll update the client though.
Ok on the closure, but it literally took 8.7 seconds to see the error in the log so I don't think the time to investigate is either tied to the time to solve or that it is the factor.
Fair point
Using the latest version the issue is not present with random seed 42 at 30 seconds. I don't know if you want to just mark this up as complete or see what caused it to determine if it may still exist since, in my mind incorrect Best Bound is sorta scary, so I'll leave it for you to close.
./highs --random_seed 42 C:\Users\thell\Downloads\viz_model.mps
Running HiGHS 1.10.0 (git hash: fd8665394e): Copyright (c) 2025 HiGHS under MIT licence terms
Set option random_seed to 42
Set option log_file to "HiGHS.log"
Number of BV entries in BOUNDS section is 60239
Number of UI entries in BOUNDS section is 50508
MIP viz_model has 259400 rows; 110747 cols; 651106 nonzeros; 110747 integer variables (60239 binary)
Coefficient ranges:
Matrix [1e+00, 2e+01]
Cost [1e+00, 3e+00]
Bound [1e+00, 2e+01]
RHS [1e+00, 2e+01]
Presolving model
166797 rows, 86937 cols, 426946 nonzeros 0s
131603 rows, 58870 cols, 335873 nonzeros 0s
87309 rows, 58706 cols, 246963 nonzeros 2s
82490 rows, 55415 cols, 236041 nonzeros 5s
Objective function is integral with scale 1
Solving MIP model with:
82490 rows
55415 cols (28528 binary, 26887 integer, 0 implied int., 0 continuous)
236041 nonzeros
Src: B => Branching; C => Central rounding; F => Feasibility pump; H => Heuristic; L => Sub-MIP;
P => Empty MIP; R => Randomized rounding; S => Solve LP; T => Evaluate node; U => Unbounded;
z => Trivial zero; l => Trivial lower; u => Trivial upper; p => Trivial point; X => User solution
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Src Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
0 0 0 0.00% 411 inf inf 0 0 0 0 5.8s
0 0 0 0.00% 424.8128979 inf inf 0 0 1 3472 6.7s
0 0 0 0.00% 430.7643595 inf inf 3616 201 255 7419 12.1s
0 0 0 0.00% 432.6468898 inf inf 5332 291 284 10284 17.2s
0 0 0 0.00% 433.9138478 inf inf 6629 345 306 14315 23.3s
0 0 0 0.00% 434.3436014 inf inf 6270 356 319 16755 28.6s
0 0 0 0.00% 434.418354 inf inf 5414 323 338 19351 34.2s