v0.1 · pure-Go simplex shipping

Linear programming for Go,
planted from seed.

grove is the PuLP of Go. Model an LP with named variables and operator-style constraints, hand it to a built-in two-phase simplex solver, and read back duals and reduced costs — all with zero CGO and no system libraries.

get grove read the docs $ go get github.com/jakenherman/grove

examples/scheduling/main.go

prob := grove.NewProblem("nurses", grove.Maximize)

day   := prob.NewVar("day",   grove.Continuous, grove.Bounds(0, grove.Inf))
night := prob.NewVar("night", grove.Continuous, grove.Bounds(0, grove.Inf))

prob.SetObjective(grove.Expr{day: 1, night: 1})
prob.AddConstraint("day_min",   grove.Expr{day: 1},                 grove.GTE, 4)
prob.AddConstraint("night_min", grove.Expr{night: 1},               grove.GTE, 2)
prob.AddConstraint("budget",    grove.Expr{day: 1200, night: 1500}, grove.LTE, 18000)

res, _ := prob.Solve()
fmt.Println(res.Status, res.Objective)
// Optimal 14.5

deps

no cgo, no system libraries

install

1 line

go get and you're solving

why grove

Named variables, sparse Expr maps
Two-phase simplex with Bland's rule
Duals, reduced costs, slacks out of the box
MPS & LP file export today; HiGHS in v0.3

the field

Every Go LP library asks you to give something up.

grove doesn't. Here's how it stacks up against the libraries Go developers have been making do with.

library	solver	modeling DSL	pure Go?	license	maintained?
gonum/optimize/lp	simplex, dense matrices	none — pass `c`, `A`, `b` by hand	yes	BSD-3	yes
golp	LP_Solve (cgo)	thin wrapper	no — cgo	LGPL	abandoned 2017
goop	pure Go simplex	operator-style	yes	BSD-3	abandoned 2017
grove	two-phase simplex; HiGHS in v0.3	named-variable map DSL	yes	MIT	active

use cases

Three problems, three runnable models.

Each card maps to a program in examples/. Read the source, then change a number and watch the solution adapt.

scheduling

Shift coverage

Cover 7 days of nurse demand at minimum cost across full-time and part-time shifts. Output includes per-day shadow prices.

go run ./examples/scheduling

infrastructure

VM resource allocation

LP-relaxation of multi-dimensional knapsack. Pack workloads onto a fixed CPU/RAM/disk pool to maximise business value.

go run ./examples/allocation

classics

Stigler diet

The original LP. Hit a daily nutritional target at minimum dollar cost across a basket of foods, with full sensitivity report.

go run ./examples/diet

install

One command, one import.

Go 1.22 or newer. No apt-get, no brew, no LD_LIBRARY_PATH. grove is one Go module with zero cgo dependencies.

go get github.com/jakenherman/grove

import "github.com/jakenherman/grove"

prob := grove.NewProblem("hello", grove.Minimize)
x := prob.NewVar("x", grove.Continuous, grove.Bounds(0, grove.Inf))
prob.SetObjective(grove.Expr{x: 1})
prob.AddConstraint("c", grove.Expr{x: 1}, grove.GTE, 7)
res, _ := prob.Solve()
// res.Value(x) == 7

benchmarks

Fast enough to vanish into your hot path.

v0.1 is a dense-tableau implementation; v0.2 will move to sparse pricing and v0.3 will plug in HiGHS. Numbers below come from go test -bench=. on an Apple M-series; absolute values will vary on your hardware but the shape holds.

Solve time per problem

lower is better · darwin/arm64 · go test -bench=.

Small LP 2 vars · 3 constraints
2 µs

Diet LP 10 vars · 6 constraints

~12 µs

Scheduling LP 14 vars · 9 constraints

~18 µs

Random LP 100 vars · 50 constraints

4.5 ms

Dense pivot cost is O(m·n) per iteration; on the random LP each pivot averages ~70 µs and the solver converges in roughly 60 iterations. Sparse pricing in v0.2 should knock the random benchmark below 1 ms; HiGHS in v0.3 is expected to be 10–30× faster again on bigger sparse models.