# Branch and bound report (M5)

Generated by `bench/report-mip.ps1` from commit `bb784ce`.

- Toolchain: `moon 0.1.20260920 (914d7da 2026-09-20) ~\.moon-latest\bin\moon.exe | moonc v0.10.14+7d59c7ec9 (2026-09-18) ~\.moon-latest\bin\moonc.exe | moonrun 0.1.20260920 (914d7da 2026-09-20) ~\.moon-latest\bin\moonrun.exe |  | Feature flags enabled: rr_moon_mod,rr_moon_pkg`
- Instances: MIPLIB 2017 (<https://miplib.zib.de>), fetched by `bench/fetch-instances.ps1`; the list is `bench/data/instances/manifest.txt`.
- Mode: integer models solved by branch and bound, row limit 300, node budget 300, relaxation iteration cap 5000, every relaxation verified, root cuts at the library default.
- The script writes nothing unless the run exited zero, covered every manifest entry, had no refused certificate, and every reported point passed the row, bound and integrality checks against the model.

## Summary

| metric | value |
| --- | --- |
| instances in manifest | 32 |
| proven optimal (tree exhausted or every open bound closed) | 3 |
| stopped at the node budget | 12 |
| skipped (row count over the limit) | 17 |
| other outcomes | 0 |
| relaxations verified by `verify` | 3770 |
| cuts added and verified by `verify_cut` | 325 |
| reported points checked against the model | 12 |

Only `optimal` claims an answer. A run that stopped at the budget reports the
incumbent it found together with the bound still open - the two numbers a caller
needs to decide whether to keep going - and a run whose relaxation came back
unbounded says so rather than calling the integer model unbounded, because an
improving ray of the relaxation carries no integrality of its own.

The `verify` column is the number of node relaxations the independent checker
accepted; with verification on it equals the node count unless a relaxation reached
no verdict, which is exactly the work the budget left undone. That happens two ways:
the iteration cap, and a relaxation whose optimal basis cannot be written down as a
certificate at all. The second is a category rather than one measurement: before it
emits a certificate the kernel checks the multiplier sign convention the checker reads
it in and the duality gap those multipliers prove against the objective the point has,
and a basis it cannot state a proof for is reported as a numerical failure. Both are
open work rather than a refused claim: a run with no
proof to offer has not made a claim the checker could refuse, and the tree is not
exhausted, so the run ends at a limit instead of stopping the search.

The deficit has two sources and the `note` column names the first: a node popped
from the queue whose relaxation reaches no verdict. Its region is still unexplored,
so the bound the run reports is taken over the queue *and* over the keys of those
nodes - a key is the parent's relaxation objective, which bounds every point below
it, and a run that counted only the queue would report a bound it had not
established. The second source leaves nothing open: a step of the primal heuristic
that reaches no verdict spends a relaxation without finding a point, and the node
it walked from had answered, so the children it branches into still carry that
answer.

The node count is every relaxation the run solved, which includes the ones the
primal heuristic spends walking a fractional node down to a whole point and the ones
spent re-solving the root after a round of cuts: they are relaxations of restricted
models, solved and verified by the same path a node's is, and they come out of the
same budget. An empty `objective` column means the run never stood on a whole point,
which the `note` column says in words.

The `cuts` column counts inequalities added to the model the tree is built on. Each
one was rounded from a row of the root's tableau and then re-derived from the witness
that row is by `verify_cut`, which refuses a cut whose derivation does not reproduce
it; a refusal stops the run rather than being skipped, because an invalid cut removes
integer points from every node below it and no other check in the project can see
that. A round of cuts is kept only when the root's re-solve returns a verdict and does
not come back worse, so a round that costs more pivots than it saves is discarded

## Instances

| instance | vars | cons | integer vars | result | objective | bound | gap | nodes | verified | cuts | point check | note |
| --- | ---: | ---: | ---: | --- | ---: | ---: | ---: | ---: | ---: | ---: | --- | --- |
| flugpl | 18 | 18 | 11 | node-limit |  | 1177564.5000004936 | 1e+300 | 300 | 300 | 18 |  | relaxation budget of 300 reached with 151 tree node(s) still open; no integer point found yet |
| blend2 | 353 | 274 | 264 | node-limit |  | 7.139367545067016 | 1e+300 | 300 | 300 | 16 |  | relaxation budget of 300 reached with 73 tree node(s) still open; no integer point found yet |
| cap6000 | 6000 | 2176 | 6000 | skipped |  |  |  |  |  |  |  | rows=2176 > 300 |
| danoint | 521 | 664 | 56 | skipped |  |  |  |  |  |  |  | rows=664 > 300 |
| dcmulti | 548 | 290 | 75 | node-limit | 188706.00000021877 | 187541.36447590124 | 1164.6355243175349 | 300 | 300 | 20 | worst row violation 3.0050043966438745e-11, worst bound violation 1.9539925233402373e-14, worst integrality violation 1.184999999999996e-12 (feasible and whole) | relaxation budget of 300 reached with 281 tree node(s) still open |
| dsbmip | 1886 | 1233 | 192 | skipped |  |  |  |  |  |  |  | rows=1233 > 300 |
| fiber | 1298 | 363 | 1254 | skipped |  |  |  |  |  |  |  | rows=363 > 300 |
| gt2 | 188 | 29 | 188 | node-limit |  | 20232.49374813412 | 1e+300 | 300 | 300 | 30 |  | relaxation budget of 300 reached with 148 tree node(s) still open; no integer point found yet |
| khb05250 | 1350 | 101 | 24 | optimal | 106940226.00012392 |  |  | 107 | 107 | 39 | worst row violation 1.4779384777258774e-9, worst bound violation 0, worst integrality violation 0 (feasible and whole) |  |
| markshare1 | 62 | 6 | 50 | node-limit | 257.000000000293 | 0 | 257.000000000293 | 300 | 300 | 15 | worst row violation 4.436082881444898e-14, worst bound violation 0, worst integrality violation 0 (feasible and whole) | relaxation budget of 300 reached with 202 tree node(s) still open |
| markshare2 | 74 | 7 | 60 | node-limit | 192.00000000369937 | 0 | 192.00000000369937 | 300 | 300 | 17 | worst row violation 2.171144225113287e-13, worst bound violation 0, worst integrality violation 0 (feasible and whole) | relaxation budget of 300 reached with 198 tree node(s) still open |
| misc07 | 260 | 212 | 259 | node-limit | 3159.9999999968986 | 1634.1071428582152 | 1525.8928571386834 | 300 | 300 | 20 | worst row violation 6.170980961939492e-11, worst bound violation 1.7027490528647034e-12, worst integrality violation 2.327482090189338e-11 (feasible and whole) | relaxation budget of 300 reached with 266 tree node(s) still open |
| mitre | 10724 | 2054 | 10724 | skipped |  |  |  |  |  |  |  | rows=2054 > 300 |
| mod010 | 2655 | 146 | 2655 | optimal | 6548 |  |  | 31 | 31 | 20 | worst row violation 0, worst bound violation 0, worst integrality violation 0 (feasible and whole) |  |
| mod011 | 10958 | 4497 | 96 | skipped |  |  |  |  |  |  |  | rows=4497 > 300 |
| noswot | 128 | 182 | 100 | node-limit | -35.000000000009315 | -43.00000000004755 | 8.000000000038234 | 300 | 299 | 10 | worst row violation 2.735589532668902e-12, worst bound violation 0, worst integrality violation 2.517541730640005e-12 (feasible and whole) | relaxation budget of 300 reached with 198 tree node(s) still open |
| p0201 | 201 | 133 | 201 | node-limit | 7975 | 7555.000006642165 | 419.9999933578347 | 300 | 300 | 20 | worst row violation 0, worst bound violation 0, worst integrality violation 0 (feasible and whole) | relaxation budget of 300 reached with 283 tree node(s) still open |
| pk1 | 86 | 45 | 55 | node-limit | 18.000000000027132 | 1.004193262207216e-12 | 18.000000000026127 | 300 | 300 | 20 | worst row violation 1.7367769071547444e-14, worst bound violation 0, worst integrality violation 0 (feasible and whole) | relaxation budget of 300 reached with 249 tree node(s) still open |
| qiu | 840 | 1192 | 48 | skipped |  |  |  |  |  |  |  | rows=1192 > 300 |
| rout | 556 | 291 | 315 | node-limit | 1998.180000005329 | 995.9585131088302 | 1002.2214868964988 | 300 | 300 | 20 | worst row violation 1.637198743920898e-11, worst bound violation 0, worst integrality violation 0 (feasible and whole) | relaxation budget of 300 reached with 275 tree node(s) still open |
| 22433 | 429 | 198 | 231 | optimal | 21477.000000017408 |  |  | 33 | 33 | 20 | worst row violation 1.896660606312659e-11, worst bound violation 0, worst integrality violation 0 (feasible and whole) |  |
| 30n20b8 | 18380 | 576 | 18380 | skipped |  |  |  |  |  |  |  | rows=576 > 300 |
| 50v-10 | 2013 | 233 | 1647 | node-limit | 9132.509983330965 | 3078.326287764402 | 6054.183695566563 | 300 | 300 | 40 | worst row violation 2.5579538487298175e-12, worst bound violation 0, worst integrality violation 0 (feasible and whole) | relaxation budget of 300 reached with 297 tree node(s) still open |
| aflow40b | 2728 | 1442 | 1364 | skipped |  |  |  |  |  |  |  | rows=1442 > 300 |
| 2club200v15p5scn | 200 | 17013 | 200 | skipped |  |  |  |  |  |  |  | rows=17013 > 300 |
| bc1 | 1751 | 1913 | 252 | skipped |  |  |  |  |  |  |  | rows=1913 > 300 |
| bienst1 | 505 | 576 | 28 | skipped |  |  |  |  |  |  |  | rows=576 > 300 |
| bienst2 | 505 | 576 | 35 | skipped |  |  |  |  |  |  |  | rows=576 > 300 |
| blp-ar98 | 16021 | 1128 | 15806 | skipped |  |  |  |  |  |  |  | rows=1128 > 300 |
| core2536-691 | 15293 | 2539 | 15284 | skipped |  |  |  |  |  |  |  | rows=2539 > 300 |
| dano3_3 | 13873 | 3202 | 69 | skipped |  |  |  |  |  |  |  | rows=3202 > 300 |
| fast0507 | 63009 | 507 | 63009 | skipped |  |  |  |  |  |  |  | rows=507 > 300 |