LP/MIP solver that fits in a browser tab

A solver that knows your problem structure

Commercial solvers (Gurobi, CPLEX) are incredible at general-purpose optimization. But they're proprietary black boxes with enterprise pricing, 100MB+ binaries, license server requirements, and can't run in a browser or on the edge. Open-source alternatives (HiGHS, GLPK) are lighter but still treat every problem as a generic LP/MIP.

Ralph takes a different approach: domain-aware optimization. When you submit a problem, Ralph analyzes its structure. Is it a linear assignment? Route it to the JVC solver (633× faster). Is it a minimum-cost network flow? Route it to the network simplex (5–10× faster). Is it a set-covering problem from fleet optimization? Apply domain-specific cuts. And when the problem doesn't have exploitable structure, Ralph's full dual simplex with presolve and telemetry provides a serious general-purpose solver.

Six algorithms, one API

  ralph_optimize(model)
         │
         ▼
  ┌──────────────┐     ┌─────────────┐
  │  detect.c    │────▶│ LAP?        │──▶ JVC Solver (lap.c)
  │  Analyze     │     │ Network?    │──▶ Network Simplex (netflow.c)
  │  structure   │     │ Set Cover?  │──▶ SCP: presolve + cuts + heuristics
  └──────┬───────┘     └─────────────┘
         │ General LP/MIP
         ▼
  ┌──────────────┐     ┌─────────────┐     ┌─────────────────────────┐
  │  presolve.c  │────▶│ simplex.c   │────▶│ lu.c / lu_sparse.c      │
  │  7 techniques│     │ Primal +    │     │ LU factor, Markowitz    │
  │  multi-round │     │ Dual        │     │ supernode, circuit break │
  └──────────────┘     └──────┬──────┘     └─────────────────────────┘
                              │                          ▲
                              │                   ┌──────┴──────┐
                              │ MIP?              │ governor.c  │
                              ▼                   │ G0 shadow + │
                       ┌──────────────┐           │ G1 control  │
                       │ branch_      │           └─────────────┘
                       │ bound.c      │     ┌─────────────┐
                       │ B&B tree     │────▶│  cuts.c     │
                       └──────┬───────┘     │ Gomory MIC  │
                              │             │ Reach cuts  │
                              │             └─────────────┘
                              │ Decomposable?
                              ▼
                       ┌──────────────┐
                       │ benders.c    │
                       │ Decompose +  │
                       │ Farkas cuts  │
                       └──────────────┘

1. Primal Simplex (General LP)

Full revised simplex implementation with LU factorization and eta file updates. Dantzig and steepest-edge pricing, Harris two-pass ratio test, automatic refactorization governed by a 5-phase policy to prevent numerical drift. Two-phase method with Big-M for infeasibility detection.

2. Dual Simplex

Standalone dual simplex method — 1,869 lines of dedicated implementation, not a wrapper around primal. Bound perturbation for anti-degeneracy, Farkas certificate extraction for provable infeasibility, and warm-start from primal optimal for sensitivity analysis. The dual simplex is the workhorse for branch-and-bound reoptimization where most subproblems differ by a single bound change.

3. Branch-and-Bound (MIP)

LP-based branch-and-bound for mixed-integer programs. Best-first + depth-first node selection. Most-fractional and pseudocost branching variable selection. Gomory mixed-integer cutting planes. Conflict analysis with clause learning for intelligent backtracking. Presolve: 7 techniques across multiple rounds.

4. Jonker-Volgenant-Castanon (Assignment)

Industrial-strength linear assignment solver. Dense, sparse (CSR), and rectangular variants. O(n³) worst case, often O(n²) in practice. k-best solutions via Murty's algorithm. Warm start from previous dual solution (5–7× speedup). Priority and cardinality constraints for unbalanced problems.

5. Network Simplex (MCNF)

Specialized solver for Minimum Cost Network Flow problems. Candidate list pricing, warm start, cost scaling (ε-scaling for degeneracy), and flow decomposition into paths. Auto-detects special cases: shortest path, assignment, transportation.

6. Benders Decomposition

Generic Benders decomposition framework — 1,556 lines of C. Decomposes large problems into a master problem and subproblems, generating optimality and Farkas feasibility cuts. Multi-scenario support for stochastic programming. Designed for fleet-scale problems where the master handles assignment decisions and subproblems handle routing/scheduling feasibility.

Automatic problem detection

When detect_special is enabled, Ralph analyzes LP structure before solving:

Production-grade numerical infrastructure

A simplex solver is only as good as its numerical linear algebra. Ralph's LU factorization pipeline has been engineered for both speed and stability, with three layers of governance ensuring the solver makes the right numerical decisions at every step.

LU Factorization

The revised simplex maintains the basis matrix B in LU-factored form (B = LU). Ralph provides two LU implementations: a dense LU with eta file updates, and a sparse LU with Markowitz pivoting that separates symbolic and numeric phases. The sparse variant includes a circuit breaker that detects excessive growth factor and triggers micro-retry with tighter thresholds before falling back to full refactorization.

• LU Sparse Markowitz — Symbolic/numeric separation, growth factor monitoring, micro-retry with circuit breaker, full-retry fallback
• LU Supernode — Auto-enabled for m > 300. Detects supernodal structure in the elimination tree and processes columns in batches using dense GEMM-like kernels for cache efficiency
• Eta file updates — Instead of refactoring B after each pivot, store the update as an eta matrix. Governed by refactor policy

Basis Governor

The Basis Governor controls when and how to refactorize. Two modes: G0 (shadow) runs alongside the solver collecting telemetry (growth factor, residual norm, pivot quality) without intervening. G1 (control) uses that data to make real-time decisions: when to refactor, when to switch LU strategies, when to tighten tolerances.

Refactor Policy (5 phases)

Rather than a fixed "refactor every 50 pivots" rule, Ralph uses a 5-phase adaptive policy:

• Phase A — Pressure scheduler: triggers refactor based on accumulated numerical pressure, not a fixed counter
• Phase B — Health hysteresis: prevents oscillation between refactor/no-refactor states
• Phase C — Cost dampening: avoids unnecessary refactors when the basis is stable
• Phase D — LU strategy selection: switches between dense and sparse LU based on fill-in predictions
• Phase E — Emergency recovery: detects numerical breakdown and triggers full reset

Presolve (7 techniques)

Multi-round presolve reduces problem size before the simplex begins. 2,757 lines of dedicated infrastructure with a postsolve stack that recovers original-space solutions.

Telemetry

Five dedicated telemetry modules (2,562 lines total) instrument the solver from factorization to solution extraction. Not a debugging afterthought — telemetry is a first-class subsystem that drives the Basis Governor's decisions.

Sensitivity Analysis & Conflict Analysis

Sensitivity analysis (487 lines): RHS ranging, objective coefficient ranging, and variable bound ranging. After an optimal solution is found, determine how much each parameter can change before the basis changes. Uses the dual simplex for efficient reoptimization.

Conflict analysis (698 lines): When the MIP solver proves a subproblem infeasible, conflict analysis builds a conflict graph and learns clauses that prune the branch-and-bound tree. Similar to SAT solver clause learning, adapted for LP-based branching.

External Adapter

When a problem doesn't have exploitable structure and needs a commercial solver, Ralph dispatches through an external adapter layer. Currently supports GLPK via an OOP wrapper with a multi-provider registry designed for Gurobi and CPLEX integration. Same ralph_optimize() API — the backend is transparent.

55 of 84 NETLIB problems solved

NETLIB is the standard benchmark suite for LP solvers. Ralph solves 55 of 84 problems (65%), including all 23 fast-tier problems. The remaining 29 are primarily large sparse problems that require hyper-sparse FTRAN or advanced scaling — engineering work, not algorithmic limitations.

Key performance wins

Specialized solver performance

Where Ralph excels: problems with exploitable structure.

Build, solve, read — three steps

Modular API: ralph_lp.h for LP construction and solving, ralph_mip.h for integer programming extensions. Clean separation so LP-only users don't pull in MIP infrastructure.

// Build model
RalphModel *m = ralph_create();
ralph_set_obj_sense(m, RALPH_MAXIMIZE);

int x = ralph_add_var(m, 0, RALPH_INFINITY, 5.0, RALPH_CONTINUOUS);
int y = ralph_add_var(m, 0, RALPH_INFINITY, 3.0, RALPH_CONTINUOUS);

int idx[] = {x, y};
double vals[] = {2.0, 4.0};
ralph_add_constraint(m, 2, idx, vals, RALPH_LESS_EQUAL, 40.0);

// Solve (auto-selects primal or dual simplex)
ralph_optimize(m);

// Read solution
if (ralph_get_status(m) == RALPH_STATUS_OPTIMAL) {
    double obj = ralph_get_objval(m);
    double sol[2];
    ralph_get_solution(m, sol);
}
ralph_free(m);

Input formats

REST API

$ curl -X POST http://localhost:8084/api/v1/solve \
    -H "Content-Type: text/plain" \
    -d '
max: 5 x + 3 y

subject to
wood:  2 x + 4 y <= 40
labor: 3 x + 2 y <= 24

bounds
x >= 0
y >= 0

end
'

# Response:
# solution status: OPTIMAL
# objective value: 40.000000
# x 8.000000
# y 0.000000

Specialized APIs

double cost[9] = {
    7, 2, 1,
    2, 4, 6,
    5, 3, 1
};
int row_sol[3], col_sol[3];
double total;

ralph_lap_solve(
    3, cost,
    RALPH_LAP_MINIMIZE,
    row_sol, col_sol,
    NULL, NULL, &total);

RalphNetflowProblem p = {
    .num_nodes = 4,
    .num_arcs  = 5,
    .tail   = {0,0,1,1,2},
    .head   = {1,2,2,3,3},
    .cost   = {2,4,1,3,2},
    .cap    = {4,2,3,2,3},
    .supply = {4,0,0,-4}
};
RalphNetflowResult r;
ralph_netflow_solve(
    &p, NULL, &r, NULL);

Module breakdown

Ralph is organized into focused modules, each independently testable. The modular API splits LP and MIP concerns cleanly: ralph_lp.h for continuous optimization, ralph_mip.h for integer programming.

Codebase

Three ways to try Ralph

1. Browser (zero install)

The API documentation page includes a live WASM demo. Type an LP problem, click solve, see results. No server, no install.

2. Build from source

# Clone and build
git clone https://github.com/ottofleet/otto.git
cd otto && make ralph

# Run all tests (762+)
make test-ralph

# Run specialized solver tests
make test-ralph-lap
make test-ralph-netflow
make test-ralph-detect

3. REST API server

# Build and start
make ralph-api
./ralph/api/ralph-solver

# Solve an LP (text/plain format)
curl -X POST http://localhost:8084/api/v1/solve \
  -H "Content-Type: text/plain" \
  -d @problem.lp

# Solve MPS format
curl -X POST http://localhost:8084/api/v1/solve?format=mps \
  -H "Content-Type: text/plain" \
  -d @problem.mps

Common questions

Why build a solver from scratch when Gurobi exists?

Three reasons: (1) Embedding — Gurobi is a 100MB+ binary with license server requirements. Ralph is 63K lines of C that compiles to WASM. (2) Domain cuts — For structured trucking problems (refueling, crew scheduling), domain-specific cutting planes provide competitive advantage that generic solvers can't match. (3) Interface strategy — Ralph provides a clean external adapter that can dispatch to Gurobi/CPLEX/HiGHS when the problem doesn't have exploitable structure.

How does Ralph compare to GLPK?

On general sparse LP: Ralph is still slower per-iteration on the largest problems. On structured problems: Ralph is 86–633× faster (via auto-detection to JVC or network simplex). Ralph has a full dual simplex, presolve, telemetry, Benders decomposition, and sensitivity analysis — features GLPK lacks or implements minimally. Ralph solves 55/84 NETLIB vs GLPK's broader coverage, but the gap is narrowing with each presolve and LU improvement.

Can Ralph solve real MIP problems?

For small structured MIPs (FuelWise: k ≤ 50 binary variables), yes — especially with domain cuts and conflict analysis. For large arbitrary MIPs (1000+ variables), use the external adapter to dispatch to Gurobi/HiGHS. Ralph's MIP infrastructure is correct and improving (conflict analysis, Benders) but commercial solvers have decades of engineering on general-purpose MIP.

What's the dual simplex used for?

Branch-and-bound reoptimization. When B&B changes a single variable bound, the dual simplex reoptimizes from the previous basis in far fewer iterations than resolving from scratch. Also used for sensitivity analysis (how much can a parameter change before the basis changes?) and for extracting Farkas certificates when a problem is provably infeasible.

What are the remaining NETLIB failures?

29 of 84 NETLIB problems fail, primarily large sparse problems (thousands of rows/columns) that need hyper-sparse FTRAN, advanced matrix scaling, or pivot selection strategies not yet implemented. These are engineering problems, not algorithmic limitations. The fast tier (23/23) and medium tier pass reliably.

What's the LAP solver used for?

Vehicle-to-route assignment, driver-to-vehicle matching, facility-to-zone allocation, and any problem that maps to "assign N workers to N jobs at minimum cost." The JVC algorithm solves n=1000 in 10ms with warm start in 1.5ms. k-best solutions via Murty's algorithm for presenting alternatives.

What license?

AGPLv3 with a Trucking Exception. Same terms as all OTTO modules. Trucking fleets using Ralph for their own operations are covered by the exception. SaaS products embedding Ralph need source disclosure or a commercial license.