[BUG] Negative gap on air05 instance

[mtanneau]

[Edit]: issue updated following discussion in #858 to focus on negative difference between upper and lower bound.

Describe the bug

Solving instance air05 (see below for MPS file) on a DGX Spark desktop results in a final dual bound that exceeds the final primal bound.

Sample log (see logs from additional runs on v26.02 below)

Setting CUDA_MODULE_LOADING to EAGER
Reading file air05.mps
cuOpt version: 26.4.0, git hash: b3bb21e4, host arch: aarch64, device archs: 121a-real
CPU: Unknown, threads (physical/logical): 1/20, RAM: 96.08 GiB
CUDA 12.9, device: NVIDIA GB10 (ID 0), VRAM: 119.70 GiB
CUDA device UUID: 43bce240-d7d6-65e5-ca7a-e351bab5de7a

Solving a problem with 426 constraints, 7195 variables (7195 integers), and 52121 nonzeros
Problem scaling:
Objective coefficents range:          [4e+01, 3e+03]
Constraint matrix coefficients range: [1e+00, 1e+00]
Constraint rhs / bounds range:        [1e+00, 1e+00]
Variable bounds range:                [0e+00, 1e+00]

Original problem: 426 constraints, 7195 variables, 52121 nonzeros
Calling Papilo presolver (git hash 741a2b9c)
Presolve status: reduced the problem
Presolve removed: 90 constraints, 1116 variables, 16171 nonzeros
Presolved problem: 336 constraints, 6079 variables, 35950 nonzeros
Objective function is integral
Papilo presolve time: 0.42
Objective offset 9167.000000 scaling_factor 1.000000
Model fingerprint: 0x3257a27
Running presolve!
Unused variables detected, eliminating them! Unused var count 4
After cuOpt presolve: 335 constraints, 6075 variables, objective offset 9167.000000.
cuOpt presolve time: 3.85

Solving LP root relaxation in concurrent mode
Skipping column scaling
Dual Simplex Phase 1
Dual feasible solution found.
Dual Simplex Phase 2
 Iter     Objective           Num Inf.  Sum Inf.     Perturb  Time
    0 -8.1936000000000000e+04     277 2.31020000e+04 0.00e+00 4.51
    1 -8.0926000000000000e+04     266 1.48790000e+04 0.00e+00 4.51
 1000 -5.7784953825729302e+04     127 1.13852044e+02 0.00e+00 4.61


Root relaxation solution found in 1194 iterations and 0.13s by Dual Simplex
Root relaxation objective +2.58776093e+04


 | Explored | Unexplored |    Objective    |     Bound     | IntInf | Depth | Iter/Node |   Gap    |  Time  |
           0            0             +inf    +2.588508e+04      228      0   1.2e+03        -        4.74
Gomory    cuts : 1
MIR       cuts : 0
Knapsack  cuts : 0
Strong CG cuts : 0
Cut pool size  : 211
Size with cuts : 336 constraints, 6411 variables, -1488061860 nonzeros
Strong branching using 19 threads and 228 fractional variables
Strong branching completed in 0.47s
Exploring the B&B tree using 19 threads

 | Explored | Unexplored |    Objective    |     Bound     | IntInf | Depth | Iter/Node |   Gap    |  Time  |
H                            +4.466800e+04    +2.588508e+04                                42.1%      5.28
H                            +4.448000e+04    +2.588508e+04                                41.8%      5.28
H                            +4.430000e+04    +2.588508e+04                                41.6%      5.29
H                            +4.387300e+04    +2.588508e+04                                41.0%      5.29
H                            +4.354400e+04    +2.588508e+04                                40.6%      5.30
H                            +4.287600e+04    +2.588508e+04                                39.6%      5.31
H                            +4.191500e+04    +2.588508e+04                                38.2%      5.32
H                            +4.166800e+04    +2.588508e+04                                37.9%      5.34
H                            +4.149500e+04    +2.588508e+04                                37.6%      5.35
H                            +4.121300e+04    +2.588508e+04                                37.2%      5.37
D         42           44    +2.657100e+04    +2.591578e+04        0     16   1.4e+02       2.5%      6.78
B         44           44    +2.645600e+04    +2.591578e+04        0     19   1.3e+02       2.0%      6.78
D         62           56    +2.644800e+04    +2.591578e+04        0     30   1.3e+02       2.0%      6.85
D         71           63    +2.644500e+04    +2.595460e+04        0     30   1.3e+02       1.9%      6.87
D         71           63    +2.644100e+04    +2.595460e+04        0     29   1.3e+02       1.8%      6.87
D         77           63    +2.643900e+04    +2.595460e+04        0     27   1.3e+02       1.8%      6.88
B        170          110    +2.640200e+04    +2.610151e+04        0     12   1.1e+02       1.1%      7.16
D        342          127    +2.640000e+04    +2.624972e+04        0     19   9.6e+01       0.6%      7.60
D        344          129    +2.637500e+04    +2.624972e+04        0     17   9.6e+01       0.5%      7.61
D        348          128    +2.637400e+04    +2.626036e+04        0     17   9.6e+01       0.4%      7.62
Explored 485 nodes in 7.79s.
Absolute Gap -5.595838e+00 Objective 2.6374000000000022e+04 Lower Bound 2.6379595837897017e+04
Optimal solution found.
Solution objective: 26374.000000 , relative_mip_gap 0.000212 solution_bound 26379.595838 presolve_time 4.275866 total_solve_time 7.854454 max constraint violation 0.000000 max int violation 0.000000 max var bounds violation 0.000000 nodes 485 simplex_iterations 40126

^^ this was obtained from a source build on main.

Steps/Code to reproduce bug

I installed cuopt in a python virtual environment as follows

uv venv
uv pip install   --extra-index-url=https://pypi.nvidia.com   cuopt-server-cu13==26.02.* cuopt-sh-client==26.02.*

and then executed the following command

/.venv/bin/cuopt_cli air05.mps

I also encountered this issue after building cuopt from source from the main branch.

Expected behavior

The dual (lower) bound should not exceed the primal (upper) bound.

Environment details (please complete the following information):

• Environment location: DGX Spark desktop with GB10 GPU, 20-core CPU, 128GB unified memory, running aarch64 linux
• Method of cuOpt install:
  • pip, see steps above.
  • also encountered when building from source using Conda; see instructions in CONTRIBUTING.md file

Additional context

MPS file (uploaded as a .txt because GitHub does not support .mps files):
air05.txt
Also available here: https://github.com/jump-dev/cuOpt.jl/blob/main/test/datasets/air05.mps

Log files: all the logs below were obtained by running the following command:

./.venv/bin/cuopt_cli  air05.mps > air05.X.log

I ran this 5 times to exhibit the non-deterministic nature and range of the behavior.

air05.1.log
air05.2.log
air05.3.log
air05.4.log
air05.5.log

[rgsl888prabhu]

@chris-maes for viz

[mtanneau]

This behavior (negative gap) persists even after disabling all cuts, which suggests that it's not caused by some cuts being invalid.

It also disappears when setting parameter --mip-determinism-mode to 1, which suggests that non-deterministic lower bound computation may be to blame. My gut feeling is that the final lower bound computation in non-deterministic mode may be invalid. Maybe the B&B tree at that point contains nodes whose lower bound is invalid but weren't pruned soon enough.

Here is an exhaustive B&B log (logging is forced at every single node), focusing on the end of the B&B log.
Note that the lower bound displayed is always valid... except at the last row.

Setting CUDA_MODULE_LOADING to EAGER
Setting parameter absolute_gap_tolerance to 0.000000e+00
Setting parameter mip_determinism_mode to 0
Setting parameter mip_relative_gap to 0.000000e+00
Setting parameter presolve to 0
Setting parameter relative_gap_tolerance to 0.000000e+00
Setting parameter solution_file to air05.sol
Reading file air05.mps
cuOpt version: 26.4.0, git hash: b3bb21e4, host arch: aarch64, device archs: 121a-real
CPU: Unknown, threads (physical/logical): 1/20, RAM: 95.22 GiB
CUDA 12.9, device: NVIDIA GB10 (ID 0), VRAM: 119.70 GiB
CUDA device UUID: 43bce240-d7d6-65e5-ca7a-e351bab5de7a

Solving a problem with 426 constraints, 7195 variables (7195 integers), and 52121 nonzeros
Problem scaling:
Objective coefficents range:          [4e+01, 3e+03]
Constraint matrix coefficients range: [1e+00, 1e+00]
Constraint rhs / bounds range:        [1e+00, 1e+00]
Variable bounds range:                [0e+00, 1e+00]

Presolve is disabled, skipping
Objective offset 0.000000 scaling_factor 1.000000
Model fingerprint: 0xe47c7f7a

Solving LP root relaxation in concurrent mode
Skipping column scaling
Dual Simplex Phase 1
Dual feasible solution found.
Dual Simplex Phase 2
 Iter     Objective           Num Inf.  Sum Inf.     Perturb  Time
    0 +0.0000000000000000e+00     426 4.26000000e+02 0.00e+00 0.25
    1 +1.0500000000000000e+02     422 4.22000000e+02 0.00e+00 0.25
 1000 +2.1459514092423400e+04     215 1.41565021e+04 0.00e+00 0.34


Root relaxation solution found in 1591 iterations and 0.20s by Dual Simplex
Root relaxation objective +2.58776093e+04


 | Explored | Unexplored |    Objective    |     Bound     | IntInf | Depth | Iter/Node |   Gap    |  Time  |
           0            0             +inf    +2.589036e+04      233      0   1.7e+03        -        0.72
Gomory    cuts : 1
MIR       cuts : 0
Knapsack  cuts : 0
Strong CG cuts : 59
Cut pool size  : 398
Size with cuts : 438 constraints, 7633 variables, -670458076 nonzeros
Strong branching using 19 threads and 233 fractional variables
H                            +5.326200e+04    +2.589036e+04                                51.4%      0.89
H                            +5.167100e+04    +2.589036e+04                                49.9%      0.90
H                            +5.131600e+04    +2.589036e+04                                49.5%      0.90
H                            +5.075900e+04    +2.589036e+04                                49.0%      0.90
H                            +5.048100e+04    +2.589036e+04                                48.7%      0.90
H                            +5.022700e+04    +2.589036e+04                                48.5%      0.90
H                            +4.982200e+04    +2.589036e+04                                48.0%      0.90
H                            +4.936100e+04    +2.589036e+04                                47.5%      0.91
H                            +4.771900e+04    +2.589036e+04                                45.7%      0.91
H                            +4.757300e+04    +2.589036e+04                                45.6%      0.91
Strong branching completed in 0.93s
Exploring the B&B tree using 19 threads

 | Explored | Unexplored |    Objective    |     Bound     | IntInf | Depth | Iter/Node |   Gap    |  Time  |
           1            1    +4.757300e+04    +2.589036e+04      233      1   1.8e+03      45.6%      1.70
           2            0    +4.757300e+04    +2.589036e+04      233      1   1.0e+03      45.6%      1.87
           3            1    +4.757300e+04    +2.589036e+04      229      2   7.0e+02      45.6%      2.64
           4            0    +4.757300e+04    +2.589036e+04      229      2   5.6e+02      45.6%      2.90
H                            +4.545500e+04    +2.589036e+04                                43.0%      3.04
H                            +4.449400e+04    +2.589036e+04                                41.8%      3.05
H                            +4.438900e+04    +2.589036e+04                                41.7%      3.06
H                            +4.416500e+04    +2.589036e+04                                41.4%      3.06
H                            +4.408400e+04    +2.589036e+04                                41.3%      3.10
H                            +4.395600e+04    +2.589036e+04                                41.1%      3.11
H                            +4.386800e+04    +2.589036e+04                                41.0%      3.12
           5            1    +4.386800e+04    +2.591995e+04      216      2   4.7e+02      40.9%      3.22
           6            2    +4.386800e+04    +2.591995e+04      230      3   4.0e+02      40.9%      4.15
           7            3    +4.386800e+04    +2.591995e+04      229      3   3.8e+02      40.9%      4.53
           8            4    +4.386800e+04    +2.591995e+04      194      4   3.9e+02      40.9%      4.74
           9            5    +4.386800e+04    +2.591995e+04      190      5   3.7e+02      40.9%      4.80
          10            6    +4.386800e+04    +2.591995e+04      174      6   3.4e+02      40.9%      4.85
          11            7    +4.386800e+04    +2.591995e+04      193      7   3.2e+02      40.9%      4.93
          12            8    +4.386800e+04    +2.591995e+04      193      7   3.0e+02      40.9%      4.96
          13           11    +4.386800e+04    +2.592062e+04      217      3   2.8e+02      40.9%      5.02
          14           10    +4.386800e+04    +2.592062e+04      217      3   2.7e+02      40.9%      5.08
          15           11    +4.386800e+04    +2.592062e+04      217      3   2.7e+02      40.9%      5.08
          16           14    +4.386800e+04    +2.592062e+04      217      3   2.6e+02      40.9%      5.11
          17           15    +4.386800e+04    +2.592062e+04      217      3   2.5e+02      40.9%      5.14
          18           16    +4.386800e+04    +2.592062e+04      217      3   2.5e+02      40.9%      5.16
          19           17    +4.386800e+04    +2.592062e+04      217      3   2.4e+02      40.9%      5.21
          20           18    +4.386800e+04    +2.592062e+04      217      3   2.4e+02      40.9%      5.22
          21           19    +4.386800e+04    +2.592062e+04      217      3   2.3e+02      40.9%      5.23
          22           20    +4.386800e+04    +2.592062e+04      217      3   2.3e+02      40.9%      5.26
          23           21    +4.386800e+04    +2.592062e+04      217      3   2.2e+02      40.9%      5.28
B         49           47    +2.764200e+04    +2.592431e+04        0     19   1.8e+02       6.2%      5.50
          49           47    +2.764200e+04    +2.592431e+04      231      4   1.8e+02       6.2%      5.50
          50           48    +2.764200e+04    +2.592431e+04      217      3   1.8e+02       6.2%      5.52
          51           49    +2.764200e+04    +2.592431e+04      217      3   1.7e+02       6.2%      5.53
          52           50    +2.764200e+04    +2.592431e+04      217      3   1.8e+02       6.2%      5.53
          53           51    +2.764200e+04    +2.592431e+04      217      3   1.8e+02       6.2%      5.54
          54           52    +2.764200e+04    +2.592431e+04      217      3   1.8e+02       6.2%      5.55
          55           51    +2.764200e+04    +2.592431e+04      217      3   1.8e+02       6.2%      5.55
          56           54    +2.764200e+04    +2.592431e+04      217      3   1.8e+02       6.2%      5.56
          57           55    +2.764200e+04    +2.592431e+04      217      3   1.8e+02       6.2%      5.57
          58           56    +2.764200e+04    +2.592431e+04      217      3   1.8e+02       6.2%      5.58
          59           57    +2.764200e+04    +2.592431e+04      217      3   1.8e+02       6.2%      5.58
          60           60    +2.764200e+04    +2.592431e+04      217      3   1.8e+02       6.2%      5.60
          61           61    +2.764200e+04    +2.592431e+04      217      3   1.7e+02       6.2%      5.60
          62           62    +2.764200e+04    +2.592431e+04      217      3   1.7e+02       6.2%      5.60
          63           63    +2.764200e+04    +2.596177e+04      217      3   1.7e+02       6.1%      5.61
          64           64    +2.764200e+04    +2.596177e+04      217      3   1.7e+02       6.1%      5.61
          65           65    +2.764200e+04    +2.596177e+04      217      3   1.7e+02       6.1%      5.62
          66           66    +2.764200e+04    +2.596177e+04      217      3   1.7e+02       6.1%      5.62
          67           67    +2.764200e+04    +2.596177e+04      217      3   1.7e+02       6.1%      5.63
          68           68    +2.764200e+04    +2.596177e+04      217      3   1.7e+02       6.1%      5.63
          70           70    +2.764200e+04    +2.596177e+04      217      3   1.7e+02       6.1%      5.64
D         70           70    +2.654200e+04    +2.596177e+04        0     21   1.7e+02       2.2%      5.64
B         89           73    +2.644500e+04    +2.596177e+04        0     21   1.5e+02       1.8%      5.71
B         90           72    +2.643900e+04    +2.596177e+04        0     21   1.5e+02       1.8%      5.72
B        220          148    +2.640200e+04    +2.603324e+04        0     12   1.3e+02       1.4%      6.42
D        351          156    +2.637400e+04    +2.620424e+04        0     12   1.3e+02       0.6%      7.22
         551           63    +2.637400e+04    +2.635743e+04      199     16   1.1e+02       0.1%      7.73
         552           62    +2.637400e+04    +2.635743e+04      199     16   1.1e+02       0.1%      7.73
         554           62    +2.637400e+04    +2.635743e+04      199     16   1.1e+02       0.1%      7.73
         556           60    +2.637400e+04    +2.635743e+04      175     14   1.1e+02       0.1%      7.73
         557           59    +2.637400e+04    +2.635743e+04      114     10   1.1e+02       0.1%      7.73
         559           57    +2.637400e+04    +2.635743e+04      154     14   1.1e+02       0.1%      7.73
         560           56    +2.637400e+04    +2.635743e+04      189     12   1.1e+02       0.1%      7.74
         561           55    +2.637400e+04    +2.635743e+04      153     19   1.1e+02       0.1%      7.74
         562           54    +2.637400e+04    +2.635743e+04      143     20   1.1e+02       0.1%      7.74
         564           52    +2.637400e+04    +2.635743e+04      184     17   1.1e+02       0.1%      7.74
         567           51    +2.637400e+04    +2.635743e+04        7     16   1.1e+02       0.1%      7.74
         569           49    +2.637400e+04    +2.635743e+04      166     18   1.1e+02       0.1%      7.74
         571           49    +2.637400e+04    +2.635900e+04      189     14   1.1e+02       0.1%      7.74
         572           48    +2.637400e+04    +2.635900e+04       54     18   1.1e+02       0.1%      7.75
         573           47    +2.637400e+04    +2.635900e+04      161     17   1.1e+02       0.1%      7.75
         574           48    +2.637400e+04    +2.636451e+04        9     17   1.1e+02       0.0%      7.76
         575           47    +2.637400e+04    +2.637100e+04       34     20   1.0e+02       0.0%      7.76
         576           46    +2.637400e+04    +2.637100e+04      204      5   1.0e+02       0.0%      7.76
         577           45    +2.637400e+04    +2.707359e+04      193      7   1.0e+02       2.7%      7.76
Explored 577 nodes in 7.76s.
Absolute Gap -7.324463e+02 Objective 2.6374000000000007e+04 Lower Bound 2.7106446335990051e+04
Optimal solution found.
Writing solution to file air05.sol

[mtanneau]

[EDIT]: never mind, the behavior I'm pointing out below is just diving trees being created and explored.

---

Here is what I could dig out so far (assuming this is related). After activating the graphviz tree printing, I noticed some node IDs are repeated throughout the tree (I'm attaching a full log below).

Snippets from that log:

• The lower bound returned at the end appears to be the lower bound at Node12
• However, Node12 shows up multiple times in the log (a total of 50 times!), and appears to be created 37 times 🤯

Node10 [label="lower bound 2.6869720434455823e+04"]
Node10 -> Node11 [label="x3256 <= 0.000000e+00"]
Node10 -> Node12 [label="x3256 >= 1.000000e+00"]
...
Node12 [label="lower bound 2.7117371243046906e+04"]
Node12 -> Node83 [label="x2979 <= 0.000000e+00"]
Node12 -> Node84 [label="x2979 >= 1.000000e+00"]
...
Node9 -> Node12 [label="x5717 >= 1.000000e+00"]  // Node12 created again!?
..
Node9 -> Node12 [label="x4198 >= 1.000000e+00"]  // Node12 created again again!?
...
Explored 595 nodes in 8.21s.
Absolute Gap -7.433712e+02 Objective 2.6374000000000004e+04 Lower Bound 2.7117371243046906e+04

I traced this behavior back to this code

cuopt/cpp/src/branch_and_bound/mip_node.hpp

Line 327 in f91f9cc

void branch(mip_node_t<i_t, f_t>* parent_node,

where node IDs are obtained by incrementing a (presumably thread-safe) counter num_nodes

cuopt/cpp/src/branch_and_bound/mip_node.hpp

Line 335 in f91f9cc

i_t id = num_nodes.fetch_add(2);

namely

cuopt/cpp/src/utilities/omp_helpers.hpp

Lines 107 to 116 in f91f9cc

	T fetch_add(T inc)
	{
	T old;
	#pragma omp atomic capture
	{
	old = val;
	val += inc;
	}
	return old;
	}

I then ran an extra check and confirmed that every thread appears to basically have its own num_nodes.
I also saw the same thread sometimes appears to re-initialize the num_nodes to zero.

---

Full log I'm referring above: air05.tree.log

[chris-maes]

Thanks for reporting. I was able to reproduce the issue. I put up #890 which should fix the issue. Feel free to verify it yourself. Please reopen if there are still issues.

Note that the negative nonzeros printing will be fixed once #856 is merged.