[BUG] cuopt incorrectly report optimal integer solution when the objective offset is very large #417
Description
Branch-and-Bound incorrectly state that an optimal integer solution has been found within the relative gap tolerance when a large offset is applied to the objective during the presolve.
This can be trigger by running the PR #405 over the supportcase42 instance from MIPLIB. At the end of the procedure, B&B report that it found an optimal solution with user_objective = 9, however, the true optimal objective is 7.75863072227 according to the MIPLIB site. In this case, the solver actually see the bounds and relative gap as relative gap = 0.000062, upper_bound = 26784.000000, lower_bound = 26782.343661. Below are the full log.
❯ cuopt-ref/cpp/build/solve_MIP --path datasets/miplib2017/supportcase42.mps.bz2 --time-limit 100
running file supportcase42.mps.bz2 on gpu : 0
cuOpt version: 25.10.0, git hash: ef90a38, host arch: x86_64, device archs: 90a-real
CPU: Intel(R) Xeon(R) Silver 4314 CPU @ 2.40GHz, threads (physical/logical): 16/32, RAM: 152.80 GiB
CUDA 13.0, device: NVIDIA H100 (ID 0), VRAM: 95.07 GiB
CUDA device UUID: ffffff9947ffffffb571-051b-6d68-fffff
Unpresolved problem:: 18439 constraints, 19466 variables, 435653 nonzeros
Presolve status:: reduced the problem
Presolve removed:: 282 constraints, 283 variables, 564 nonzeros
Presolved problem:: 18157 constraints, 19183 variables, 435089 nonzeros
Third party presolve time: 0.122674
Solving a problem with 18157 constraints 19183 variables (1026 integers) and 435089 nonzeros
Objective offset -26775.000000 scaling_factor 1.000000
Free variable found! Make sure the correct bounds are given.
Running presolve!
After trivial presolve #constraints 18157 #variables 20069 objective offset -26775.000000.
Using 4 CPU threads for B&B
Solving LP root relaxation
Scaling matrix. Maximum column norm 5.562658e+01
Dual Simplex Phase 1
Dual feasible solution found.
Dual Simplex Phase 2
Iter Objective Num Inf. Sum Inf. Perturb Time
1 +0.0000000000000000e+00 2 3.33333333e+02 1.00e-07 0.07
Failed to remove perturbation of 1.85e-04.
Root relaxation solution found in 504 iterations and 0.37s
Root relaxation objective +7.34366096e+00
Strong branching using 4 threads and 174 fractional variables
CPUFJ added a solution to population, solution queue size 0 with objective 39.9999
CPUFJ added a solution to population, solution queue size 0 with objective 9.9999
CPUFJ added a solution to population, solution queue size 0 with objective 8.9999
New solution from primal heuristics. Objective +2.157089e+01. Time 0.58
Running FP alone!
CPUFJ added a solution to population, solution queue size 0 with objective 38.9999
CPUFJ added a solution to population, solution queue size 0 with objective 37.9999
CPUFJ added a solution to population, solution queue size 0 with objective 36.9998
CPUFJ added a solution to population, solution queue size 0 with objective 35.9999
CPUFJ added a solution to population, solution queue size 0 with objective 34.9999
CPUFJ added a solution to population, solution queue size 0 with objective 33.9999
CPUFJ added a solution to population, solution queue size 0 with objective 32.9999
CPUFJ added a solution to population, solution queue size 0 with objective 31.9999
CPUFJ added a solution to population, solution queue size 0 with objective 30.9999
CPUFJ added a solution to population, solution queue size 0 with objective 29.9999
CPUFJ added a solution to population, solution queue size 0 with objective 28.9999
CPUFJ added a solution to population, solution queue size 0 with objective 27.9999
CPUFJ added a solution to population, solution queue size 0 with objective 26.9999
| Explored | Unexplored | Objective | Bound | Depth | Iter/Node | Gap | Time
1 1 +2.157089e+01 +7.343661e+00 1 0.0e+00 66.0% 2.10
CPUFJ added a solution to population, solution queue size 0 with objective 25.9999
CPUFJ added a solution to population, solution queue size 0 with objective 24.9999
CPUFJ added a solution to population, solution queue size 0 with objective 24.238
CPUFJ added a solution to population, solution queue size 0 with objective 23.238
CPUFJ added a solution to population, solution queue size 0 with objective 22.238
CPUFJ added a solution to population, solution queue size 0 with objective 22.2379
48 48 +2.157089e+01 +7.343661e+00 14 4.2e-01 66.0% 3.10
CPUFJ added a solution to population, solution queue size 0 with objective 22.2378
97 97 +2.157089e+01 +7.343661e+00 22 2.1e-01 66.0% 4.10
145 145 +2.157089e+01 +7.343661e+00 29 1.4e-01 66.0% 5.11
194 194 +2.157089e+01 +7.343661e+00 35 1.0e-01 66.0% 6.13
243 243 +2.157089e+01 +7.343661e+00 41 8.2e-02 66.0% 7.14
292 292 +2.157089e+01 +7.343661e+00 47 6.8e-02 66.0% 8.15
341 341 +2.157089e+01 +7.343661e+00 51 5.9e-02 66.0% 9.15
388 388 +2.157089e+01 +7.343661e+00 58 5.2e-02 66.0% 10.15
437 437 +2.157089e+01 +7.343661e+00 63 4.6e-02 66.0% 11.17
486 486 +2.157089e+01 +7.343661e+00 67 4.1e-02 66.0% 12.18
535 535 +2.157089e+01 +7.343661e+00 74 3.7e-02 66.0% 13.19
584 584 +2.157089e+01 +7.343661e+00 79 3.4e-02 66.0% 14.20
633 633 +2.157089e+01 +7.343661e+00 45 3.2e-02 66.0% 15.21
682 682 +2.157089e+01 +7.343661e+00 89 2.9e-02 66.0% 16.23
731 731 +2.157089e+01 +7.343661e+00 92 2.7e-02 66.0% 17.25
779 779 +2.157089e+01 +7.343661e+00 87 2.6e-02 66.0% 18.26
828 828 +2.157089e+01 +7.343661e+00 103 2.4e-02 66.0% 19.27
878 878 +2.157089e+01 +7.343661e+00 108 2.3e-02 66.0% 20.29
927 927 +2.157089e+01 +7.343661e+00 113 2.2e-02 66.0% 21.31
976 976 +2.157089e+01 +7.343661e+00 118 2.0e-02 66.0% 22.32
2000 2000 +2.157089e+01 +7.343661e+00 173 1.0e-02 66.0% 44.36
3000 3000 +2.157089e+01 +7.343661e+00 257 6.7e-03 66.0% 65.45
4000 4000 +2.157089e+01 +7.343661e+00 379 5.0e-03 66.0% 86.25
FP alone finished!
Killing CPU solver
Killing CPU solver
4649 4649 +2.157089e+01 +7.343661e+00 391 4.3e-03 66.0% 99.80
Hit time limit. Stopping
H +1.000000e+01 +7.343661e+00 26.6% 99.81
H +9.000000e+00 +7.343661e+00 18.4% 99.81
Explored 4649 nodes in 99.81s.
Absolute Gap 1.422723e+01 Objective 9.0000000000000000e+00 Lower Bound 7.3436609543532541e+00
relative gap: 0.000062, upper_bound = 26784.000000, lower_bound = 26782.343661
Optimal solution found within relative MIP gap tolerance (1.0e-04)
Killing CPU solver
Killing CPU solver
Killing CPU solver
Killing CPU solver
Killing CPU solver
Killing CPU solver
Killing CPU solver
Killing CPU solver
Post-solve status:: succeeded
Solution objective: 9.000000 , relative_mip_gap 0.184038 solution_bound 7.343661 presolve_time 0.126977 total_solve_time 100.051471 max constraint violation 0.000000 max int violation 0.000000 max var bounds violation 0.000000 nodes 4649 simplex_iterations 20
first obj: 0.000000 last improvement of best feasible: 100.048658 last improvement after recombination: 0.000000
run_solver 100097
supportcase42.mps.bz2: solution found, obj: 9.000000