wrong dual bound on miplib2017's neos-5107597-kakapo

[svigerske]

On https://miplib.zib.de/WebData/instances/neos-5107597-kakapo.mps.gz, Cbc stable/2.10 and releases/2.10.12 start with a dual bound much above the optimal value ("best possible 113976"), and then terminate with the first feasible solution found, e.g., with objective function value 69876.
An optimal value should be 3645.

Welcome to the CBC MILP Solver 
Version: 2.10.12 
Build Date: Mar  4 2026 

command line - bin/cbc kakapo.mps (default strategy 1)
At line 1 NAME          mipfeas   FREE
At line 2 ROWS
At line 6502 COLUMNS
At line 16262 RHS
At line 19512 BOUNDS
At line 22489 ENDATA
Problem mipfeas has 6498 rows, 3114 columns and 19392 elements
Coin0008I mipfeas read with 0 errors
Continuous objective value is 0 - 0.19 seconds
Cgl0004I processed model has 6441 rows, 3057 columns (2976 integer (2976 of which binary)) and 19278 elements
Cbc0038I Initial state - 1473 integers unsatisfied sum - 30.2193
Cbc0038I Pass   1: (0.92 seconds) suminf.   17.58263 (1508) obj. 14139 iterations 717
Cbc0038I Pass   2: (0.93 seconds) suminf.   16.89075 (1489) obj. 14022 iterations 38
Cbc0038I Pass   3: (0.93 seconds) suminf.   16.49850 (1474) obj. 13887 iterations 30
Cbc0038I Pass   4: (0.94 seconds) suminf.   16.01800 (1460) obj. 13644 iterations 38
Cbc0038I Pass   5: (0.95 seconds) suminf.   15.32288 (1441) obj. 13518 iterations 52
Cbc0038I Pass   6: (0.96 seconds) suminf.   15.06850 (1432) obj. 13464 iterations 30
Cbc0038I Pass   7: (0.97 seconds) suminf.   14.59838 (1414) obj. 13374 iterations 49
Cbc0038I Pass   8: (0.97 seconds) suminf.   14.30563 (1400) obj. 13356 iterations 43
Cbc0038I Pass   9: (0.98 seconds) suminf.   13.78750 (1381) obj. 13212 iterations 44
Cbc0038I Pass  10: (0.99 seconds) suminf.   13.10188 (1349) obj. 13167 iterations 55
Cbc0038I Pass  11: (1.00 seconds) suminf.   12.47425 (1326) obj. 13131 iterations 59
Cbc0038I Pass  12: (1.01 seconds) suminf.   12.14863 (1310) obj. 13230 iterations 50
Cbc0038I Pass  13: (1.02 seconds) suminf.   11.72363 (1291) obj. 12492 iterations 57
Cbc0038I Pass  14: (1.03 seconds) suminf.   11.17525 (1267) obj. 12294 iterations 59
Cbc0038I Pass  15: (1.04 seconds) suminf.   10.63513 (1236) obj. 11961 iterations 63
Cbc0038I Pass  16: (1.05 seconds) suminf.   10.04738 (1211) obj. 11610 iterations 65
Cbc0038I Pass  17: (1.05 seconds) suminf.    9.69175 (1187) obj. 11439 iterations 48
Cbc0038I Pass  18: (1.07 seconds) suminf.    9.24438 (1165) obj. 11349 iterations 66
Cbc0038I Pass  19: (1.07 seconds) suminf.    8.98013 (1149) obj. 11448 iterations 34
Cbc0038I Pass  20: (1.08 seconds) suminf.    8.56425 (1131) obj. 11646 iterations 57
Cbc0038I Pass  21: (1.09 seconds) suminf.    8.09825 (1106) obj. 11610 iterations 71
Cbc0038I Pass  22: (1.10 seconds) suminf.    7.88088 (1090) obj. 11565 iterations 30
Cbc0038I Pass  23: (1.11 seconds) suminf.    7.65213 (1079) obj. 11646 iterations 34
Cbc0038I Pass  24: (1.12 seconds) suminf.    7.21125 (1050) obj. 11655 iterations 55
Cbc0038I Pass  25: (1.12 seconds) suminf.    6.95400 (1031) obj. 11745 iterations 49
Cbc0038I Pass  26: (1.13 seconds) suminf.    6.58000 (1005) obj. 11763 iterations 48
Cbc0038I Pass  27: (1.14 seconds) suminf.    6.27375 (983) obj. 11826 iterations 41
Cbc0038I Pass  28: (1.15 seconds) suminf.    5.96388 (963) obj. 11844 iterations 42
Cbc0038I Pass  29: (1.15 seconds) suminf.    5.73775 (945) obj. 11853 iterations 33
Cbc0038I Pass  30: (1.16 seconds) suminf.    5.47038 (921) obj. 11826 iterations 40
Cbc0038I No solution found this major pass
Cbc0038I Before mini branch and bound, 1135 integers at bound fixed and 7 continuous
Cbc0038I Mini branch and bound did not improve solution (1.37 seconds)
Cbc0038I Full problem 6442 rows 3057 columns, reduced to 6307 rows 2967 columns - too large
Cbc0038I After 1.51 seconds - Feasibility pump exiting - took 0.69 seconds
Cbc0031I 714 added rows had average density of 6.8935574
Cbc0013I At root node, 714 cuts changed objective from 0 to 113976 in 10 passes
Cbc0014I Cut generator 0 (Probing) - 6 row cuts average 4.2 elements, 0 column cuts (178 active)  in 4.850 seconds - new frequency is -100
Cbc0014I Cut generator 1 (Gomory) - 3288 row cuts average 10.6 elements, 0 column cuts (0 active)  in 0.212 seconds - new frequency is 1
Cbc0014I Cut generator 2 (Knapsack) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.003 seconds - new frequency is -100
Cbc0014I Cut generator 3 (Clique) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.022 seconds - new frequency is -100
Cbc0014I Cut generator 4 (MixedIntegerRounding2) - 872 row cuts average 2.5 elements, 0 column cuts (0 active)  in 0.027 seconds - new frequency is 1
Cbc0014I Cut generator 5 (FlowCover) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.021 seconds - new frequency is -100
Cbc0014I Cut generator 6 (TwoMirCuts) - 3732 row cuts average 9.0 elements, 0 column cuts (0 active)  in 0.399 seconds - new frequency is 1
Cbc0010I After 0 nodes, 1 on tree, 1e+50 best solution, best possible 113976 (10.34 seconds)
Cbc0010I After 100 nodes, 73 on tree, 1e+50 best solution, best possible 113976 (29.39 seconds)
Cbc0010I After 200 nodes, 102 on tree, 1e+50 best solution, best possible 113976 (37.17 seconds)
Cbc0010I After 300 nodes, 200 on tree, 1e+50 best solution, best possible 113976 (40.93 seconds)
Cbc0010I After 400 nodes, 285 on tree, 1e+50 best solution, best possible 113976 (45.03 seconds)
Cbc0010I After 500 nodes, 376 on tree, 1e+50 best solution, best possible 113976 (47.66 seconds)
Cbc0010I After 600 nodes, 466 on tree, 1e+50 best solution, best possible 113976 (50.77 seconds)
Cbc0010I After 700 nodes, 547 on tree, 1e+50 best solution, best possible 113976 (53.35 seconds)
Cbc0010I After 800 nodes, 644 on tree, 1e+50 best solution, best possible 113976 (55.09 seconds)
Cbc0012I Integer solution of 69876 found by rounding after 54384 iterations and 848 nodes (55.49 seconds)
Cbc0001I Search completed - best objective 69876, took 54384 iterations and 848 nodes (55.60 seconds)
Cbc0032I Strong branching done 10860 times (103449 iterations), fathomed 5 nodes and fixed 640 variables
Cbc0035I Maximum depth 703, 0 variables fixed on reduced cost
Cuts at root node changed objective from 0 to 113976
Probing was tried 10 times and created 6 cuts of which 178 were active after adding rounds of cuts (4.850 seconds)
Gomory was tried 827 times and created 7377 cuts of which 0 were active after adding rounds of cuts (1.989 seconds)
Knapsack was tried 10 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.003 seconds)
Clique was tried 10 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.022 seconds)
MixedIntegerRounding2 was tried 827 times and created 1160 cuts of which 0 were active after adding rounds of cuts (1.893 seconds)
FlowCover was tried 10 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.021 seconds)
TwoMirCuts was tried 827 times and created 4019 cuts of which 0 were active after adding rounds of cuts (1.876 seconds)
ZeroHalf was tried 1 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
ImplicationCuts was tried 19 times and created 8 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)

Result - Optimal solution found

Objective value:                69876.00000000
Enumerated nodes:               848
Total iterations:               54384
Time (CPU seconds):             55.75
Time (Wallclock seconds):       58.38

Total time (CPU seconds):       55.75   (Wallclock seconds):       58.38

With branch master (and corresponding for CoinUtils, Clp, Osi, Cgl), this doesn't seem to happen. Cbc finds a very conservative dual bound of 1 and then has difficulty bringing it up:

...
Cbc0010I After 6220 nodes, 1694 on tree, 13698 best solution, best possible 1.0151057 (998.72 seconds)
Cbc0010I After 6226 nodes, 1693 on tree, 13698 best solution, best possible 1.0151057 (999.46 seconds)
Cbc0010I After 6241 nodes, 1698 on tree, 13698 best solution, best possible 1.0151057 (1000.17 seconds)
Cbc0010I After 6249 nodes, 1702 on tree, 13698 best solution, best possible 1.0151057 (1000.92 seconds)
Cbc0010I After 6259 nodes, 1705 on tree, 13698 best solution, best possible 1.0151057 (1001.66 seconds)
^CCbc0027I Exiting on user event
Cbc0005I Partial search - best objective 13698 (best possible 1.0151057), took 645237 iterations and 6272 nodes (1002.32 seconds)
Cbc0032I Strong branching done 49872 times (582702 iterations), fathomed 84 nodes and fixed 10098 variables
Cbc0035I Maximum depth 436, 95 variables fixed on reduced cost

Maybe a bugfix on master for one of the projects was forgotten to be cherry-picked into the corresponding latest stable branches?

[Whatsonyourmind]

The symptom — dual bound starting at 113,976 when the optimal is 3,645 — indicates the LP relaxation bound is being computed incorrectly or the root node processing is corrupting the bound.

A few diagnostics that could narrow this down:

1. Check the LP relaxation value directly. Solve just the continuous relaxation (no branching) and verify the objective:

cbc kakapo.mps -solve -quit

The log shows "Continuous objective value is 0" which looks correct (the LP relaxation is 0). But then the initial dual bound jumps to 113,976 after the first round of cuts. This suggests a cutting plane is generating an invalid cut that incorrectly tightens the relaxation.

2. Disable specific cut generators to isolate the culprit. Try:

cbc kakapo.mps -cutoff 100000 -probingCuts off -solve
cbc kakapo.mps -cutoff 100000 -gomory off -solve
cbc kakapo.mps -cutoff 100000 -knapsack off -solve
cbc kakapo.mps -cutoff 100000 -clique off -solve
cbc kakapo.mps -cutoff 100000 -flow off -solve
cbc kakapo.mps -cutoff 100000 -mixed off -solve

If one of these produces a correct bound, that cut generator is producing invalid cuts for this model structure.

3. The model characteristics matter. neos-5107597-kakapo has 6,498 rows, 3,114 columns (2,976 binary), and the coefficient range likely includes both very small and very large values. This is the regime where numerical issues in cut generation are most common — the intersection of a cutting hyperplane with a near-degenerate polytope face can produce a violated cut due to floating-point rounding in the Simplex basis.

4. Try with -primalT 1e-8 -dualT 1e-8 to tighten tolerances. If the dual bound improves, the issue is numerical precision in the LP solver under the default tolerances.

This pattern (LP relaxation correct at root, dual bound corrupted after cuts) is a known failure mode in MIP solvers when a problem has wide coefficient ranges. HiGHS 1.10+ handles this more robustly if you want to cross-validate the result.