IGAOS Wayfinder Map: sovereign GPU optimization solver for SIH26119

[Lothnic]

Destination

A locked technical spec plus a submitted idea package by Sep 20, 2026: MVP scope cuts, architecture, language, benchmark protocol, robustness strategy, and go/no-go fallbacks all decided — so building starts with nothing left to choose. SIH-only horizon.

Notes

• Domain: SIH26119 (MRPL) — an indigenous GPU-accelerated optimization solver core (LP/MILP/QP), built from scratch: the PS forbids building upon any existing open-source solver library. Full PS analysis: docs/SIH26119-RESEARCH-REPORT.md; sources: docs/SOURCES.md.
• Standing facts: team of 6 locked (CUDA + linear algebra experience; no prior simplex/B&B implementation). Hardware: local GPUs + a 16 GB remote GPU + Modal credits. Candidate languages: Python & C++ (best wins). Internal hackathon expected ~Sept 2026, exact dates unconfirmed. Idea deadline Sep 20; finale Dec 2026. Internal hackathon ≈Sep 1: barely-working MVP suffices there. Ruling on primitives: RECEIVED (arithmetic libs OK, solver libs forbidden).
• Working conventions: every session consults the grilling and domain-modeling skills; CONTEXT.md is created lazily as terms crystallize (e.g., "from-scratch boundary", "near-optimal", "solver core"). HITL tickets resolve through live conversation with the human; research tickets are worked by subagents alone.
• Claims: assigning a ticket to @Lothnic claims it — open + unassigned + unblocked = takeable frontier.

Decisions so far

• Survey first-order GPU LP methods (PDHG/PDLP) & pin the algorithm sheet: implement restarted adaptive PDHG; GPU KKT-error restart variant pinned (thresholds 0.2/0.8/0.36, ~40-iter checks); v1 defaults fixed (adaptive steps, Ruiz+Pock-Chambolle preconditioning, tol 1e-4); wins only above ~1M-nnz scale — CPU simplex stays the small/medium path; post-check residuals always.
• Pin revised-simplex design: basis updates, pricing, ratio test: bounded-variable dual revised simplex; sparse LU + product-form eta updates, refactorize every 50-100 pivots, dense fallback below m~2000; Devex pricing first; Harris two-pass (delta=1e-7) + bound-flipping ratio test; HiGHS-recipe cost perturbation + geometric-mean power-of-two scaling.
• Benchmark protocol: instances, metrics, pinned baseline, hardware sheet: HiGHS v1.15.1 pinned baseline with fixed flags; Netlib ladder 20 core + 7 stretch; MIPLIB 2017 easy starter subset 16+4 validated against official solufile; rel-gap metrics solved@1e-4 / tight@1e-6, tiered time limits; Mittelmann LPfeas aspirational GPU target; one canonical 10-column result table + hardware-sheet template.
• Select refinery demo case studies (crude-blending LP + pooling QP): Williams refinery LP (time-expanded to 1k-2k vars) + Haverly pooling presented at three honesty levels (LP relax / convex QP overlay / true bilinear NLP); scale ladder BenTal4 to sppc3 (10,567 vars); every pick has free data + reference optimum.
• Define MILP engine scope ladder (B&B → cuts → heuristics): Rung 1 plain B&B (best-bound+dive, presolve-lite); Rung 2 Gomory MI cuts; cut line before branch-and-cut / GPU pump (stretch only).
• Set MVP component scope & stretch goals: all four engines at demo quality with tiers — LP flagship, PDHG showcase, MILP rung-1, ADMM-QP on Haverly-class; kill criteria checked Nov 15 (drop QP → drop GPU story → simplex+B&B floor).
• Numerical robustness strategy: geometric-mean scaling → Harris two-pass (δ=1e−7) → BFRT → cost shifting+perturbation → refinement on residual failure; ladder solved@1e−4/tight@1e−6 everywhere.
• Design sparse linear algebra layer: dual-path — own CSR/CSC+SpMV+triangular kernels always built (sovereignty backbone + small-problem path); cuSPARSE/cuDSS fast paths behind same interface, switched ON only if Rule on the from-scratch boundary for CUDA math libraries #2 ruling permits.
• Go/no-go risk gate criteria: mechanical CONTINUE iff (1) primitives permitted OR Path-B ≤3× HiGHS on mediums, (2) PDHG ≤1e−4 obj-gap on ≥5 instances within 10× HiGHS, (3) ≥14 days before Sep 20. Spike evidence on (2): FAIL at spike maturity — see Spike: minimal PDHG kernel on the remote GPU #11.
• Honest-claims & crossover narrative policy: crossover stated first; small-instance losses upfront; near-optimal = labeled per instance; never claim beating Gurobi/CPLEX; regressions rerun-or-omitted.
• Assign team roles & close skills gaps: execution = Lothnic + agent for now; four teammates onboard via standing template when active.
• Spike: minimal PDHG kernel on the RTX 4060: from-scratch CUDA CP validated vs oracle; afiro/sc50a/adlittle OPT@1e−4 on device; quality gated on cuPDLP-C restart/averaging machinery → ticketed as PDHG v2: adopt cuPDLP-C-grade restarts, adaptivity & averaging #20; gate criterion (2) FAIL at spike maturity, reported verbatim.
• MPS/LP reader + CLI/Python API surface design: locked — public Status/Solution/Options headers, igaos CLI (info/solve) with canonical JSON + reserved --engine flag, MPS reader promoted to src/io from the spike; Python surface solve()/read_mps() documented.
• Pin presolve/postsolve pass list: MVP trio (empty row/col removal, fixed-col substitution, singleton-row tightening) with reduction-log postsolve; on/off objective match ≤1e−9 rel gate on Netlib ladder; one shared path feeding all engines.
• Define B&B Rung-1 engine details: most-fractional branching; best-bound+dive node rule; dual-simplex warm-starts from parent basis; int tol 1e−6, tier limits, incumbent/bound every 1000 nodes; bar = ≥12/20 MIPLIB starter ≤1e−4 gap vs HiGHS.
• PDHG v2 machinery: order locked — KKT-ratio restarts + unweighted avg phases → adaptive steps → drift correction → PID/Halpern if needed; OPT gated on finite duality gap; bar ≥7/8 spike set obj-match ≤1e−3 then >1M-nnz showcase; perf engineering deferred.
• Compose robustness suite: locked as drafted — 15 instances / 6 stress classes incl. infeasible-detection trio + synthetic bound fixture; per-class pass criteria in docs/research/robustness-suite.md.
• Structure idea-submission PPT: 10 slides mapped to rubric weights; demo-video plan; every claim traceable to repo artifacts; owner files via SPOC before Sep 20 (Submission logistics: internal-hackathon dates, SPOC flow, Sep 20 filing #15).
• Rule on the from-scratch boundary: MRPL ruling received — arithmetic libraries permitted, solver-deciding libraries forbidden; Path A (cuSPARSE/cuDSS) switched ON (Design sparse linear algebra layer #8).
• Go/no-go gate check: CONTINUE — criterion 1 PASS (ruling), criterion 3 PASS (~26 days), criterion 2 re-checks after PDHG v2.
• Choose implementation language & repo layout: C++20 + CUDA core (CPU-only fallback) with a thin pybind11 MPS-to-solution API; BLAS-class primitives allowed pending Rule on the from-scratch boundary for CUDA math libraries #2 ruling, optimization libraries banned (policy: docs/DEPENDENCIES.md); monorepo src/{common,linalg,simplex,pdhg,milp,io,api} scaffolded on main; CPU-only CI planned, GPU smoke manual.

Not yet specified

(empty — every patch has graduated into tickets: Pin presolve list #18 · B&R Rung-1 details #19 · PDHG v2 machinery #20 · robustness suite #21 · PPT structure #22)

Out of scope

• Post-SIH productization / startup path
• GUI or modeling environment (the PS explicitly excludes it)
• NLP/MINLP extension work (PS future work)
• Grand-finale demo/pitch decisions (beyond this destination; fresh effort later if wanted)
• Matching Gurobi/CPLEX outright