linear-program

linear-program is a MoonBit library for writing linear programs and solving them with the two-phase simplex method. Coefficients are generic over the algebraic traits of luna-generic, and the simplex tableau is a mutable matrix from linear-algebra. Every step of the solver is public, so the library also serves to follow the simplex method by hand.

Packages

All public names live in the single package at src, documented as core.

Package	Contents	API	Tutorial	Design
core (src, import path linear-program)	Variables, linear expressions, objectives and constraints (Variable, Poly, Obj_func, Constraint); programs and standard form (Lp, Lp::to_standard); the two-phase simplex solver (Lp::two_stage, Lp::pivot, Lp::simplex_iteration, Lp::phase_1, Lp::phase_2); the tolerance trait ApproximatelyZero.	API	Tutorial	Design

Reading paths

• New to linear programming. Work through the tutorial: it solves a production problem, then a minimisation with >= constraints, then pivots a tableau by hand. Keep the design notes open for the meaning of standard form, reduced costs and the two phases.
• Using the solver. The tutorial quick start and its list of common pitfalls are enough to solve small programs. The API reference states the exact behaviour of every function, including what aborts.
• Contributing. Read the design notes, especially the invariants and the known defects, then the contribution guidelines.

Toolchain and installation

The library requires MoonBit with moonc 0.10 or newer and depends on Luna-Flow/luna-generic 0.3.3 and Luna-Flow/linear-algebra 0.4.7.

Import the package in your moon.pkg:

import {
  "linear-program" @lp,
  "Luna-Flow/linear-algebra/mutable" @la,
}

Before opening a pull request, run moon fmt, moon check --target all, moon info and moon test, or the ready_to_pr.sh script.