Incorrect Best Bound when random_seed is set.

[Thell]

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).

viz_model.zip

[jajhall]

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

[Thell]

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.

[jajhall]

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

[Thell]

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