← All Cracked Math projects
PM-A08NOT STARTEDADVANCEDMATHPYTHONIMPACT ★★★☆☆

An interior-point LP solver vs the whole Netlib suite

Mehrotra's predictor-corrector, your own Cholesky, and 95 degenerate real-world LPs that try to break it.

EST.32 h
REWARD+400 XP
AFTERNetlib LP test problems + 1

ML-ARENA BENCHMARKS

PROOF: BENCH
METRICINDUSTRYMINE
Number of Netlib problems solved to 1e-6 relative objective error; median IPM iterations
GOAL · >= 80 of the ~95 Netlib problems solved to 1e-6; median iteration count within 1.5x of HiGHS IPM
HiGHS via scipy.optimize.linprog(method='highs-ipm') · measured locally; optimal values from the Netlib lp/data readme—
no results yet
YOUR RESULTS

Your recorded results appear here.

Brief

A linear program (LP) minimises a linear cost subject to linear constraints. An interior-point method (IPM) solves it by moving through the inside of the feasible region rather than along its edges. Write an MPS parser (MPS is the standard text file format for LPs). Write a presolve that simplifies the problem first: remove empty rows, singletons (rows with only one variable) and fixed variables, and split each free variable into two non-negative ones. Implement a Mehrotra predictor-corrector primal-dual interior-point method: each iteration takes a predicted step, then a correcting step, and updates the problem and its dual together. Solve its normal equations with your own regularised Cholesky (adding a tiny value to the diagonal) that survives near-singularity. Run it on the full Netlib LP collection (a classic set of hard real-world LPs) and check results against the optimal values in Netlib's readme.

VICTORY CONDITIONS

  1. >= 80 of the ~95 Netlib problems solved to 1e-6; median iteration count within 1.5x of HiGHS IPM (Number of Netlib problems solved to 1e-6 relative objective error; median IPM iterations).
  2. A public repository with a README that shows your result and how to reproduce it.

Terms in plain words

Linear program (LP)
An optimisation problem with a linear objective and linear equality and inequality constraints.
Interior-point method
A solver that follows a smooth path through the inside of the feasible region toward the optimum, using Newton steps.
Primal-dual
Solving the original problem and its dual (a companion problem that bounds the optimum) at the same time, which gives a built-in optimality check.
Mehrotra predictor-corrector
An IPM step rule that first predicts a direction, then corrects it for curvature, which cuts the number of iterations.
Presolve
Simplifying an LP before solving it by removing redundant rows, fixed variables and other easy cases.
Degenerate LP
An LP where several constraints are tight at once or redundant, which makes the linear systems nearly singular.

Why it rates ★★★☆☆

An IPM that survives Netlib's degenerate problems (ones with redundant or tied constraints that confuse solvers) is genuine optimisation craft, though tangential to modern ML.