Skip to content

LESSONS.md

Latest commit

 

History

History
736 lines (554 loc) · 31.9 KB

LESSONS.md

File metadata and controls

736 lines (554 loc) · 31.9 KB
Raw

Performance Optimization Lessons

This document tracks performance optimization attempts for jsLPSolver, what worked, and what didn't.

What Worked

1. Int32Array for Column Tracking (10-15% improvement)

Changed nonZeroColumns from number[] to Int32Array in the pivot function.

  • Better cache locality with typed arrays
  • Pre-allocated with dynamic growth when needed
  • JS engines optimize typed array access
// Before
const nonZeroColumns: number[] = [];

// After
let nonZeroColumns = new Int32Array(1024);

2. Pre-computed Inverse Quotient (5-10% improvement)

In the pivot loop, pre-compute 1/quotient once instead of dividing repeatedly.

// Before
for (let c = 0; c < nNonZeroColumns; c++) {
    matrix[rowOffset + col] -= val / quotient;
}

// After
const invQuotient = 1 / quotient;
for (let c = 0; c < nNonZeroColumns; c++) {
    matrix[rowOffset + col] -= val * invQuotient;
}

Note: Must still use division (not multiplication) for the pivot row normalization itself, or numerical precision issues affect MIP branching.

3. Pivot Row Cache for Large Problems (15-30% improvement on simplex)

Cache normalized pivot row values in a Float64Array before updating other rows:

// Before: read from matrix each time
for (let i = 0; i < nNonZeroColumns; i++) {
    const c = nonZeroColumns[i];
    const v0 = matrix[pivotRowOffset + c]; // Cache miss!
    matrix[rowOffset + c] -= coefficient * v0;
}

// After: read from cached array
for (let i = 0; i < nNonZeroColumns; i++) {
    const c = nonZeroColumns[i];
    const v0 = pivotRowCache[i]; // Sequential access
    matrix[rowOffset + c] -= coefficient * v0;
}

Time breakdown on Vendor Selection (1641x1722 matrix):

  • Before: Initial simplex 761ms, B&C 457ms
  • After: Initial simplex 525-610ms, B&C 315-358ms

Note: Full benchmark variance makes overall impact unclear, but time-breakdown consistently shows improvement.

4. Cached Array References Outside Loops (5-10% improvement)

Cache frequently accessed object properties before hot loops:

// Before
for (let r = 1; r <= lastRow; r++) {
    const varIndex = this.varIndexByRow[r];
    if (this.unrestrictedVars[varIndex]) { ... }
}

// After
const varIndexByRow = this.varIndexByRow;
const unrestrictedVars = this.unrestrictedVars;
for (let r = 1; r <= lastRow; r++) {
    const varIndex = varIndexByRow[r];
    if (unrestrictedVars[varIndex]) { ... }
}

4. Simplified Cost Row Offset

Since costRowIndex is always 0, costRowOffset = costRowIndex * width is always 0. Removed the variable entirely.

5. Hash-Based Cycle Detection (5-8% improvement when enabled)

Replaced O(n²) cycle detection with hash-based O(1) average lookup:

// Before: O(n²) - compare every pair
function checkForCycles(varIndexes: Array<[number, number]>): number[] {
    for (let e1 = 0; e1 < varIndexes.length - 1; e1++) {
        for (let e2 = e1 + 1; e2 < varIndexes.length; e2++) {
            // Compare pairs...
        }
    }
}

// After: O(1) average with Map
class CycleDetector {
    private positions: Map<string, number[]> = new Map();

    add(leaving: number, entering: number): number[] {
        const key = `${leaving}_${entering}`;
        const prevPositions = this.positions.get(key);
        if (prevPositions === undefined) {
            this.positions.set(key, [pos]);
            return [];
        }
        // Only check for cycle when duplicate pair found
    }
}

Vendor Selection timing:

  • With cycle detection (old): ~946ms
  • With cycle detection (new): ~884ms
  • Without cycle detection: ~817ms

Note: Cycle detection still adds ~8% overhead even with O(1) lookup due to Map operations and string key creation. Users can disable via exitOnCycles: false for pure performance.

6. Matrix Over-Allocation During Cuts (marginal improvement)

When growing the matrix for cut constraints, over-allocate by 50% to reduce reallocation frequency:

// Before: exact allocation
const newMatrix = new Float64Array(newSize);

// After: over-allocate
const allocSize = Math.ceil(newSize * 1.5);
const newMatrix = new Float64Array(allocSize);

Reduces memory churn during iterative cut addition in branch-and-cut.

What Made Things Worse

1. Incremental Branch-and-Cut (-43% to -203% slower)

The existing useIncremental: true option was tested and found to be significantly slower:

  • Monster II: 203% slower with incremental
  • Vendor Selection: 43% slower with incremental

The overhead of maintaining incremental state exceeds the benefit of avoiding full re-solves.

2. Dual Simplex for B&C Warm-Starts (18 tests failed)

Attempted to use dual simplex after adding cut constraints in branch-and-cut:

// Attempted but reverted
tableau.addCutConstraints(branchingCuts);
tableau.dualSimplex(); // Instead of tableau.simplex()

Why it failed: When addCutConstraints() modifies the tableau, it changes the basis structure in ways that invalidate the dual feasibility assumption. The cuts aren't simple bound changes - they restructure the problem.

The dual simplex function was kept as a utility for potential future use cases where it's applicable.

3. Removing "Redundant" Zero Checks in Pivot (tests failed)

Attempted to remove nested zero checks that appeared redundant:

// Original (works)
if (row[pivotColumnIndex] !== 0) {
    for (let c = 0; c < nNonZeroColumns; c++) {
        const col = nonZeroColumns[c];
        if (pivotRowCache[col] !== 0) {
            // This check seems redundant
            // ... update
        }
    }
}

// Attempted removal (broke tests)
if (row[pivotColumnIndex] !== 0) {
    for (let c = 0; c < nNonZeroColumns; c++) {
        const col = nonZeroColumns[c];
        // Removed inner check - causes numerical drift
        // ... update
    }
}

Why it failed: Even though nonZeroColumns should only contain non-zero columns, the inner check prevents accumulation of floating-point errors. Removing it causes tiny numerical differences that compound during MIP branching, leading to different (though mathematically valid) solutions that don't match expected test outputs.

4. Using Multiplication Instead of Division for Pivot Row Normalization

// Original (works)
matrix[pivotRowOffset + c] = matrix[pivotRowOffset + c] / quotient;

// Attempted (broke tests)
matrix[pivotRowOffset + c] = matrix[pivotRowOffset + c] * invQuotient;

Why it failed: Same numerical precision issue. The pivot row values must be computed with division to maintain precision. Multiplication by inverse introduces small errors that affect MIP branching decisions.

5. Removing "Redundant" Double Zero Check in Pivot Row Update

// Original (works) - appears redundant but isn't
const pivotColVal = matrix[rowOffset + pivotColumnIndex];
if (!(pivotColVal >= -1e-16 && pivotColVal <= 1e-16)) {
    const coefficient = pivotColVal;
    if (!(coefficient >= -1e-16 && coefficient <= 1e-16)) {
        // Same check!
        // ...update row
    }
}

// Attempted simplification (broke tests)
const coefficient = matrix[rowOffset + pivotColumnIndex];
if (!(coefficient >= -1e-16 && coefficient <= 1e-16)) {
    // ...update row
}

Why it failed: The double check appears redundant since coefficient = pivotColVal, but removing it broke "Fancy Stock Cutting Problem" test. The intermediate assignment to coefficient may serve as a memory barrier or affect JIT optimization in ways that change numerical behavior. Such micro-optimizations are fragile in numerical code.

Mixed Results (Problem-Dependent)

5. Replacing Math.round with Floor-Based Calculation

In getMostFractionalVar() and isIntegral(), replaced Math.abs(value - Math.round(value)) with floor-based distance calculation:

// Before
const fraction = Math.abs(varValue - Math.round(varValue));

// After
const floorVal = Math.floor(varValue);
const fracPart = varValue - floorVal;
const fraction = fracPart <= 0.5 ? fracPart : 1 - fracPart;

Results:

  • Monster II: ~16% faster
  • Vendor Selection: ~8% slower

The improvement depends on problem structure. Math.round vs Math.floor has similar performance in modern JS engines, but the conditional branching pattern may affect different problems differently.

6. Object Pooling in Min-Heap

Added object pooling for HeapEntry objects to reduce GC pressure:

private allocEntry(branch: Branch, seq: number): HeapEntry {
    if (this.poolSize > 0) {
        const entry = this.pool[--this.poolSize];
        entry.branch = branch;
        entry.seq = seq;
        return entry;
    }
    return { branch, seq };
}

Results: Marginal impact. GC in modern V8 is very efficient for short-lived objects. Pooling adds overhead that may not be offset by reduced allocations.

7. Skipping Zero Coefficients in MIR Cuts

Added early-exit for near-zero coefficients in cut generation:

if (coefficient > -precision && coefficient < precision) {
    mat[newRowOffset + colIndex] = 0;
    continue;
}

Results: Mixed. Helps sparse problems, but the additional branch may hurt dense problems.

8. Caching Fractional Volume in MIR Loop

Instead of computing fractional volume twice per iteration:

// Before: computed before AND after applyMIRCuts
const fractionalVolumeBefore = tableau.computeFractionalVolume(true);
tableau.applyMIRCuts();
const fractionalVolumeAfter = tableau.computeFractionalVolume(true);

// After: reuse previous "after" as next "before"
let fractionalVolume = tableau.computeFractionalVolume(true);
while (fractionalVolume > 0) {
    tableau.applyMIRCuts();
    const after = tableau.computeFractionalVolume(true);
    if (after >= 0.9 * fractionalVolume) break;
    fractionalVolume = after;
}

Results: Marginal improvement. The MIR cut loop typically runs only 1-3 iterations.

Investigated But Not Yet Implemented

1. Sparse Matrix Representation

The codebase has sparse-simplex.ts and sparse-matrix.ts for sparse problems. Currently disabled (SPARSE_THRESHOLD = Infinity). The comment notes that a dual-indexed (CSC+CSR) approach would be needed for efficient sparse simplex.

If re-enabled, potential improvements:

  • The setColumn function uses repeated splice() calls in a loop - could be batched
  • getColumn and getRow allocate new arrays - could use object pooling
  • getRow is O(n log m) due to binary search per column - could use row index

2. Partial Pricing

pricingBatchStart and pricingBatchSize exist for partial pricing in phase2. Currently pricingBatchSize = 0 means auto-compute. Could be tuned.

3. Better Variable Selection in Branching

getMostFractionalVar() is used for branching. Alternative strategies exist (getFractionalVarWithLowestCost()) but aren't used by default.

4. Cut Generation Efficiency

MIR cuts are applied iteratively until fractional volume stops improving. The 0.9 threshold could be tuned.

Performance Baseline (After Optimizations)

Problem Before After Change
Small LP (20x10) 0.036 ms 0.035 ms ~same
Medium LP (100x50) 3.223 ms 3.584 ms ~same
Large LP (300x150) 62.753 ms 64.480 ms ~same
Monster Problem (MIP) 4.736 ms 4.677 ms ~same
Monster II (MIP) 150.081 ms 121.0 ms -20%
Vendor Selection (MIP) 827.119 ms 790.0 ms ~-5%

Note: Monster II improvement comes from min-heap object pooling and optionalObjectives caching.

Key Insights

  1. Numerical precision matters more than speed in MIP: Many "obvious" optimizations break integer programming because tiny floating-point differences cascade through branching decisions.

  2. JS typed arrays are fast: Float64Array and Int32Array provide near-native performance. The codebase already uses Float64Array for the main matrix.

  3. Property access has overhead: Caching this.property into local variables before tight loops provides measurable gains.

  4. WASM doesn't always win: Previous attempts at WASM implementations lost to the JS version, likely due to garbage collection overhead at the JS/WASM boundary.

  5. The simplex pivot is the hot path: Most time is spent in the pivot operation. Optimizations there have the highest impact.

  6. MIP performance is problem-dependent: Unlike LP (pure simplex), MIP performance depends heavily on problem structure. An optimization that helps one problem may hurt another due to different branching paths.

  7. Benchmark variance is high: CPU throttling, background processes, and JIT warmup can cause 2x variance in benchmark results. Always compare before/after in quick succession, and run multiple times.

  8. Modern JS engines are smart: V8's GC is highly optimized for short-lived objects. Object pooling may not help and can add overhead. Similarly, Math.round vs Math.floor optimizations may be negligible.

9. Pseudo-Cost Branching in Basic B&C

Attempted to add pseudo-cost branching to the basic branch-and-cut.ts service:

const pseudoCosts: PseudoCosts = createPseudoCosts();
const PSEUDO_COST_WARMUP = 5;

// After warmup, use pseudo-cost instead of most-fractional
const variable =
    iterations > PSEUDO_COST_WARMUP
        ? getPseudoCostBranchingVar(tableau, pseudoCosts)
        : tableau.getMostFractionalVar();

Results: Tests failed because different branching decisions led to different (but valid) solutions. The change was reverted.

Why it matters: The basic service is used when no options are specified, so it must maintain backward compatibility. Users who want pseudo-cost should use branching: "pseudocost" option which routes to the enhanced service.

Benchmark insight: Strategy tests showed that "most-fractional" is actually faster than pseudo-cost for both Monster II (153ms vs 372ms) and Vendor Selection (845ms vs 1150ms). This suggests:

  1. The current pseudo-cost implementation may have overhead issues
  2. These problems happen to favor most-fractional
  3. Pseudo-cost may only help on very large MIP instances

Future Ideas to Explore

  1. Presolve improvements: The presolve phase could eliminate more variables/constraints before solving.

  2. Strong branching: Currently uses simple most-fractional variable selection. Strong branching (try both directions briefly) could prune more nodes.

  3. Cut selection: Not all cuts are equally effective. Selecting the most violated cuts could improve convergence.

  4. Parallel B&C: Web Workers could explore multiple branches in parallel (requires careful state management).

  5. Warm-starting from similar problems: For problems that differ only slightly, reusing basis information could speed up re-optimization.

  6. Devex Pricing: Approximate steepest-edge pricing for simplex. Tried - overhead too high, see section 10.

  7. Improved Pseudo-Cost Implementation: The enhanced service's pseudo-cost uses simplified fraction estimation (always 0.5). Proper tracking of fractionality at branch time could improve its effectiveness.

8. Extended Array Reference Caching (10-25% improvement on MIP)

Applied the "cache array references" pattern more extensively to MIP-related hot paths:

// Before: repeated property access in loops
for (let v = 0; v < nIntegerVars; v++) {
    const row = this.rowByVarIndex[integerVariables[v].index];
    if (Math.abs(value - Math.round(value)) > this.precision) { ... }
}

// After: cache references before loop
const rowByVarIndex = this.rowByVarIndex;
const precision = this.precision;
for (let v = 0; v < nIntegerVars; v++) {
    const row = rowByVarIndex[integerVariables[v].index];
    if (Math.abs(value - Math.round(value)) > precision) { ... }
}

Applied to:

  • isIntegral() - caches rowByVarIndex, precision
  • getMostFractionalVar() - caches rowByVarIndex
  • computeFractionalVolume() - caches variablesPerIndex, varIndexByRow, precision, height
  • addCutConstraints() - caches rhsColumn, rowByVarIndex, colByVarIndex, varIndexByRow, variablesPerIndex
  • addLowerBoundMIRCut() - caches variablesPerIndex, varIndexByCol, precomputes 1 - fractionalPart
  • addUpperBoundMIRCut() - same caching pattern

Results (measured with warmup and 15 iterations):

Problem Before After Change
Vendor Selection ~670ms ~480ms -28%
Monster II ~150ms ~100ms -33%
Large Farm MIP ~50ms ~44ms -12%

9. Fractional Volume Caching in MIR Loop (marginal)

Reuse previous "after" value as next "before" to avoid redundant computeFractionalVolume call:

// Before: compute twice per iteration
while (fractionalVolumeImproved) {
    const before = tableau.computeFractionalVolume(true);
    tableau.applyMIRCuts();
    const after = tableau.computeFractionalVolume(true);
    if (after >= 0.9 * before) break;
}

// After: reuse previous after
let volume = tableau.computeFractionalVolume(true);
while (volume > 0) {
    tableau.applyMIRCuts();
    const after = tableau.computeFractionalVolume(true);
    if (after >= 0.9 * volume) break;
    volume = after;
}

Results: Marginal improvement since the MIR loop typically runs only 1-3 iterations.

10. Devex Pricing Implementation Attempt (FAILED)

Attempted to implement Devex (DEVised steepest Edge Xtension) pricing in phase2:

// In phase2, maintain reference norms for steepest-edge approximation
const devexNorms = new Float64Array(width);
devexNorms.fill(1);

// Pricing: select column with max |reduced_cost|^2 / norm
const score = (reducedCost * reducedCost) / devexNorms[c];

// After pivot: update norms
const ratio_sq = (a_rc * a_rc) / (pivotElement * pivotElement);
devexNorms[c] = Math.max(1, devexNorms[c] + ratio_sq * pivotColNorm);

Results: 42-85% slower across all benchmarks!

Why it failed: The overhead of maintaining and updating Devex norms exceeds any benefit from reduced iterations. Each pivot requires O(width) additional work for norm updates, and the pricing scan has additional division overhead. Modern V8 JIT is very efficient at the simple Dantzig's rule pricing, making sophisticated pricing strategies counterproductive.

Key insight: Devex pricing was designed for problems where iteration count dominates runtime. For JS-based LP solving, the per-iteration overhead matters more. Only consider Devex if benchmarks show > 1000 iterations per problem.

2026-10 Round: Classic Benchmarks, Phase 1 Robustness, Warm-Started B&B

Measured against 25 Netlib LPs and 30 MIPLIB 3 instances (converted from MPS; optima cross-checked with HiGHS), not just the bundled problems, which are mostly too small to show anything.

Phase 1 was a dual simplex only from dual-feasible bases

phase1 picks the most negative row and the entering column by the dual ratio test. From a dual-feasible basis (every B&C node: root optimum + bound rows) that is a real dual simplex. From a cold start it is a heuristic: it cycled forever on netlib share2b/share1b/brandy/boeing2 and falsely reported netlib agg infeasible. Fix: on a cold start, run the fast loop from a saved state; if it stalls or claims infeasibility, restore and run phase1Robust (minimize the sum of infeasibilities, long-step ratio test). Problems the fast loop already solved take the exact same path as before.

Warm-starting B&C nodes (2x-67x on MIPLIB)

Per node the old code restored the root tableau, re-added one row per bound on the path and re-solved. Now:

  1. Plunging: one child is solved in place from its parent's optimum by adding a single row (dual simplex, usually 1-2 pivots).
  2. Parent snapshots: queued siblings may carry a copy of the parent tableau. Whether to take one is decided online by measuring both routes (re-solve cost per path row vs snapshot copy+load+solve): snapshots lose on big shallow problems (Monster_II) and win big on deep ones (stein27).
  3. Node selection: backtrack to the newest sibling, best-bound jump every 100 selections. Pure depth-first was 3x faster on egout but stalled bell3a; pure best-first loses the warm start. SCIP's 0.25 plunge quotient behaved like best-first here.
  4. Objective integrality: when every costed variable is integer with integral cost, prune nodes whose bound rounds up (to the GCD) to the incumbent. Halved nodes on stein27/mod008.

Variability is real

Changing how a node LP is re-solved changes which optimal vertex comes back, which changes branching, which changes node counts by ±30% (p0201: 15k vs 20k nodes) with no algorithmic difference. Compare across many instances, never one. MIP sanity tests now verify objective/feasibility/integrality instead of pinning one of several optimal vectors.

Harris ratio test (perf/harris-ratio)

The phase 2 ratio test skipped rows whose ratio was <= precision. Skipping them overshoots and drives rows negative, after which phase 2 optimizes over an infeasible point: netlib e226 ended "unbounded", and the old SPY option MIPs (test/test-speed in git history) got an LP relaxation of 7.1e9 with a constraint violated by 3.7e12 (true bound 0.893), so B&B never found an incumbent. Fixed with a Harris two-pass test; unrestricted basic variables no longer block; in Bland mode the leaving row also follows Bland's rule (Harris's largest-pivot choice can cycle); the Bland stall exit allows a real budget instead of lastRow pivots (Chvátal's cycling example was being reported optimal). Pass 1 must clamp distances at zero, or a row slightly past its bound makes the step negative and fakes an unbounded ray (lotfi).

Column bounds instead of rows (perf/bounded-simplex)

Upper-bounding technique (Dantzig 1955; Chvátal ch. 8) in tableau form: x = offset + sign * s, 0 <= s <= range, so "nonbasic = 0" still holds and bound changes are substitutions (bounds.ts). Branching cuts and single-variable JSON constraints (incl. binary <= 1) become column bounds.

  • SPY_20151030: 20s (rows) -> 6.1s. MIPLIB p0201 12.7s -> 0.9s.
  • Store bound arrays as dense Float64Arrays: sparse JS arrays written at scattered indices turned rangeOf into 35% of runtime.
  • Anything that captures/restores tableau state must capture bounds too: the dual loop's stall rollback silently restored a matrix inconsistent with the bound arrays (netlib brandy went "infeasible").
  • A presolve size rule counted rows; converting rows to bounds flipped its decision, and a failing toBe(null) made vitest pretty-print a huge object and OOM the worker. Count converted bounds as rows.
  • Tried a dual Harris ratio test for warm starts: 2x slower on SPY and broke Sudoku. Reverted.

Determinism: never decide from the clock

The snapshot-vs-restore choice compared measured milliseconds, so the tree depended on machine load (MIPLIB noswot: 14s on one run, >60s on others). It now compares deterministic work units (pivot count x tableau cells, copies at 0.1 per cell; results are insensitive to that weight between 0.02 and 1). noswot is now 85,903 nodes on every run. A fake clock could not expose the bug in a test (both measurements scale together), so src/tableau/determinism.test.ts asserts structurally that solving without a timeout never reads performance.now or Date.now.

Known remaining issues

  • (Round 3) MIPLIB noswot, qnet1 and vpm2 still time out at 60 s (HiGHS-WASM: noswot 52 s, others 0.4-1.3 s); their root bounds trail HiGHS's (vpm2 11.8 vs 13.0, qnet1 14716 vs 16024).
  • (Round 2) Vendor Selection 347 ms vs v1.0.3's 160 ms (5 lucky nodes).
  • Phase 2's Bland stall exit can still accept a suboptimal LP after its (now generous) budget.
  • Ranged rows (min and max on one constraint) are still two rows; a bounded slack would halve SPY's scenario rows.
  • No primal heuristics: HiGHS solves SPY at the root via a sub-MIP heuristic and reduced-cost fixing (223 -> 21 columns).

2026-10 Round 2: LP Numerics, Branching, Cuts, Presolve (perf/core-mip)

Goal: close the gap to HiGHS compiled to WebAssembly (npm highs). Every change was measured on MIPLIB 3 (30 MIPs, 60 s limit, solutions checked against HiGHS optima), the bundled sanity problems, the SPY option MIP and four youth-soccer rotation models. Node counts and pivots are deterministic, so they are the primary metric; wall time on a laptop that sleeps between bursts is not (see "Benchmarking" below).

Verify node LPs against an independent solver

MIPLIB blend2 returned 13.86 (optimum 7.599) and was "solved" only because better branching finished its tree. Cross-checking each warm-started node LP against a cold re-solve, and both against HiGHS with the node's bounds, found three bugs that a final-answer check never localizes:

  • Dual ratio test without a pivot tolerance. The fast phase 1 took the min-ratio column however tiny its entry; the tableau lost consistency (rows predicted values off by 8e5) and reported infeasible or too-high bounds. Fixed with a Harris two-pass dual test: pass 1 bounds the step over every candidate (excluding small entries from pass 1 is wrong: it lets their reduced costs go positive), pass 2 takes the largest pivot, and pivots below 1e-7 or 1e-6 of the row maximum are avoided when a larger one exists.
  • Tolerances that disagree. Harris lets rows overshoot by its tolerance, so phase 1 must count rows within that tolerance as feasible; it declared infeasibility over -3.8e-8. Harris tolerances went 1e-9 -> 1e-7 (1e-9 left no room to choose a good pivot).
  • No scaling. A row with coefficients up to 7243 hid an improving column under the 1e-8 optimality tolerance (reduced cost 7.7e-9 on a slack that could move 4e5). Rows are now equilibrated by powers of two (exact in floating point).

A useful invariant for this kind of debugging: every tableau row is an identity of the equality system, so it must hold exactly at any point satisfying the constraints (e.g. HiGHS's solution). Checking it before and after each pivot pinpointed the pivot that broke the tableau.

What now pays off (and why earlier attempts "failed")

Earlier rounds rejected Devex, pseudocost branching and removing the pivot's inner zero check because tests pinned one optimal vector and the bundled problems are tiny. The sanity suite now verifies solutions (feasible, integral, optimal objective) instead, and the larger benchmarks show:

  • Devex pricing cut the blend2 root from 2015 to 688 phase-2 pivots once rows were scaled. The weights update from the pivot row the dense tableau already holds.
  • Reliability branching (pseudocosts + strong branching until each candidate has 4 observations per direction): MIPLIB 14 -> 19 solved; egout 65k -> 8.5k nodes. Strong-branching child LPs are capped at 4x the average dive solve (at least 50 pivots); tighter caps lose infeasibility proofs (enigma 10x the nodes), no cap starves big tableaus. Its budget is half the other pivots plus a fixed work allowance (pivots x cells): a flat pivot allowance is free on small tableaus and seconds on big ones.
  • Branch-free pivot updates: zero noise once, when caching the pivot row, and the update loop needs no per-entry test (mas76 11.8 -> 9.8 s, same tree). Recycling snapshot arrays took GC from 9% to 3%.

Cuts, presolve and integrality

  • Root GMI cuts are cheap with a dense tableau (each fractional integer row is a cut). 3 rounds, slack cuts deleted afterwards: shifted geometric mean -18%, vpm1 timeout -> 68 ms, egout 7769 -> 115 nodes. More rounds enlarge every node's tableau (10 rounds lost gt2 entirely).
  • Root presolve (activity bound propagation + Savelsbergh coefficient tightening): fixnet6 and p0548 solved. Implied bounds of continuous variables must stay private to presolve: making 1600 redundant y <= 1 explicit made Vendor Selection 3x slower.
  • Reduced-cost fixing, and keeping the incumbent as a tableau snapshot: re-solving the incumbent's node from the root misses the fixings and returned fractional vertices.
  • Implied integers: a continuous variable bounded only by integer rows (a max-min "floor", a makespan) can be treated as integer. The soccer models went from 3 of 4 timing out to 0.2-2.4 s.
  • Integral objectives by total unimodularity: in facility location the costed variables are continuous but integral once the integers are fixed, so the root bound 1482.33 already means 1483. Used for objective rounding only (never branch on them).

Bundled problems are a separate constraint

The MIPLIB-driven changes made Vendor Selection 29x slower (160 ms -> 4.6 s) before it was noticed: re-run the bundled problems after every change, not only the big sets. Its fixes (private continuous bounds, TU integrality, dropping cuts that leave the rounded bound unchanged, snapshot-first resume) brought it to 347 ms; v1.0.3's 5-node tree was partly luck. Feasibility-only models (no objective) skip strong branching and cuts entirely.

Benchmarking

  • macOS sleeps between bursts even under caffeinate -i with the lid closed: processes showed 45 min elapsed for 50 s of CPU, and wall-clock results were garbage. Check ps -o etime,time when a suite runs long.
  • Node writes stderr to pipes asynchronously: when killing a process by timeout, use fs.writeSync(2, ...) for traces or they are lost.
  • The MPS loader dropped BV bounds (no value field), turning vpm2, misc03, misc07, gesa2 and qnet1 into partial LPs; reference optima must come from an independent solver on the same file.
  • Verify the returned vector, not the reported objective. The previous round's README claimed noswot solved in 76 s at -43 (the MIPLIB-listed optimum). HiGHS proves -41 for this file, and the returned vector recomputes to -19 with rows violated by 14.9: a wrong answer that matched a wrong reference. Every solved instance on this branch is now checked by recomputing feasibility, integrality and objective with HiGHS.

2026-10 Round 3: c-MIR Cuts (perf/cuts-presolve)

HiGHS's root bound after cuts was the gap on the remaining timeouts (fiber 397k vs our 196k; vpm2 13.0 vs 11.1; qnet1 16024 vs 14569). HiGHS is MIT licensed; reading its separators (HighsCutGeneration.cpp, HighsTransformedLp.cpp, HighsPathSeparator.cpp) gave the concrete rules.

What worked

  • c-MIR on the original rows (captured in x-space after root presolve, aggregated along continuous variables) with variable-upper-bound substitution (x = u y - x', the flow-cover step; for negative coefficients x' is relaxed away). mod010 solved.
  • HiGHS's delta list: |a| of every integer away from zero, the gcd of integral coefficients, 1 and max|a| + 1. With only the |a| deltas, integral rows (qnet1) made beta/delta integral and every MIR trivial. With initial complementation (u < 2x*), greedy complement flips, the active norm and a 0.1 cosine parallelism filter: fiber's root 282k -> 377k; verified MIPLIB 24 -> 27; SPY 2.4 -> 0.4 s.
  • Implied integers count as continuous for cuts: detection for branching had hidden fiber's continuous flows from VUB substitution.

What did not (measured, reverted)

  • Lifted knapsack covers (ported from HiGHS, tested valid): preferred over c-MIR (HiGHS's additive rule) or only as a fallback, they cost SPY 0.4 -> 4.1 s and fiber its solve; root bounds moved by +-1%.
  • Tableau c-MIR (B^-1 rows through the c-MIR pipeline, row slacks kept as variables and expanded only in the final cut; expanding them in the row reproduces 0 = 0): at most +1.5 on mod010's bound, weaker than GMI alone.
  • More root rounds, even with non-binding cuts aged out every round: 10 and 20 rounds lost 2-3 instances and SPY. HiGHS's many rounds rely on a cut pool, LP aging and an LP-movement stall rule we do not have.

Testing cuts

A bound-only check (the bound after cuts never passes the optimum) missed a sign error: some wrong cuts are valid-but-weak combinations. Cuts are now checked directly at sampled feasible points (each integer assignment, LPs over the continuous part in six directions); mutations that tighten a cut are caught, mutations that only weaken it are (correctly) not.