← Back
Home › Systems › Numerical and mathematical computing

lp-mip-solver

LP / MIP solver

HiGHS, Gurobi

SystemTechniques · 9Primitives · 12 lp-mip-solver Work-stealing dequeconcurrency · medium: Per-worker deque: the owner pushes and pops at the bottom without contention, idle workers steal from the top; the core of Rayon, Tokio and Go.›Fill-reducing orderingnumerics · medium: Permute a sparse symmetric matrix before Cholesky/LU so the factor has few new nonzeros; minimum degree, nested dissection and RCM trade quality, speed and parallelism.›Sparse direct solvernumerics · medium: Solve sparse Ax = b exactly by reordering, symbolic analysis, numeric LLᵀ/LU and triangular solves; fill-in, not flops per entry, decides the cost.›Cutting planesoptimization · medium: Valid inequalities added to an LP relaxation to cut off its fractional optimum without removing any integer point; the engine of branch-and-cut MIP solvers.›Interior-point method (primal-dual,…optimization · medium: Follows the central path with Newton steps on the perturbed KKT system, one sparse Cholesky per iteration; Mehrotra's predictor-corrector makes it fast.›Mixed-integer programming (branch a…optimization · medium: Solves LPs with integer variables by solving the LP relaxation, branching on a fractional variable, and pruning subtrees whose LP bound cannot beat the incumbent.›Presolve reductionsoptimization · medium: Cheap, provably safe reductions run before the solver (fix variables, drop rows, tighten bounds and coefficients) so LP and MIP solves start from a smaller, tighter model.›d-ary heapdata-structures · low: Array heap with d children per node (d = 4 typical): half the binary heap's depth, siblings in one cache line, faster priority queues.›Sparse matrices (CSR)numerics · low: Compressed sparse row stores only nonzeros as row pointers, column indices and values; SpMV streams them once, so it is memory-bandwidth bound.›LU and Cholesky factorizationnumerics · low: Factor A = PLU (any square matrix, partial pivoting) or A = LLᵀ (SPD) once in O(n³), then solve each right-hand side in O(n²).›Floating-point errornumerics · low: How IEEE 754 rounding error accumulates and how to contain it: compensated (Kahan/Neumaier) and pairwise summation, error-free transformations with FMA, ULP comparisons.›Simplex methodoptimization · low: Solves linear programs by walking along the edges of the feasible polytope from vertex to vertex, one basis swap (pivot) at a time; the workhorse behind MIP solvers.›Epoch-based reclamationconcurrency · low: Threads announce a global epoch while touching shared lock-free data; garbage retired in epoch e is freed once the epoch reaches e + 2.›Memory orderingconcurrency · low: What Relaxed, Acquire, Release and SeqCst atomics actually guarantee, what they cost on x86 and ARM, and which one each pattern needs.›Newton root findingnumerics · low: Linearize at the guess and jump to the tangent root; quadratic convergence near a simple root, made robust by brackets (1D) or line search.›Fast hash functionsdata-structures · low: Non-cryptographic hashes built from 64×64→128-bit multiplies and xor-shifts; pick by key size, trust level and whether the hash is persisted.›Interval arithmeticnumerics · low: Rigorous bounds with outward rounding; root isolation and robust geometric testsGPU compute shadersml-training · low: The vendor-neutral GPU launch model of Metal, Vulkan and WebGPU: a grid of workgroups, shared memory, barriers and subgroups, driven by recorded command buffers.›PRNGs (PCG, xoshiro)numerics · low: Small, fast, statistically strong non-cryptographic generators: PCG32 and xoshiro256**, with seeding, parallel streams and unbiased ranges.›+ 2 more techniques

Similar systems

Share the most building blocks with this one.

convex-optimizer 50 %circuit-sim 28 %nonlinear-optimizer 25 %power-flow-sim 25 %eigensolver 24 %