There’s no denying the growing movement within the Python community to prefer Rust over C for writing performance-sensitive extension modules. Leading the way there’s polars, a fast multi-threaded DataFrame library I’ve discussed in an earlier post, ruff which runs about 100x faster than the predominant (and painfully sluggish) flake8 linter, and even pydantic is preparing a 2.0 release with a pydantic-core backend written entirely in Rust. To add to this already-impressive corpus of projects, I am proud to annouce the release of dantzig, a Rust-powered linear programming library for Python!
Linear Programming
If you are unfamilar with linear programming, allow me to share a quick example to demonstrate its power. Suppose you are the manager of a retail store and over the next three time periods you need to order inventory from your supplier to satisfy demand.
- A priori, you know how much demand there will be each time period (an unrealistic assumption to be sure, but our model can be extended to accommodate uncertain demand) denoted by \(d_t\) for \(t \in \{1, 2, 3\}\).
- The supplier charges a different per-unit price \(p_t\) in each time period
- You face inventory holding costs \(h_t\) for any inventory carried over from period \(t\) to period \(t + 1\).
- In each time period, you decide how much inventory to order, given by \(x_t\), and then sell to your customers.
Naturally, you seek a policy that minimizes total cost. This problem can be formulated as a linear program:
\[\begin{align*} \min_x \quad & \sum_{t = 1}^3 p_t x_t + \sum_{t = 1}^3 h_t z_t \\ \text{s.t.} \quad & x_1 \geq d_1 \\ & x_2 + z_1 \geq d_2 \\ & x_3 + z_2 \geq d_3 \\ & z_1 = x_1 - d_1 \\ & z_2 = x_2 + z_1 - d_2 \\ & z_3 = x_3 + z_2 - d_3 \\ & x_t \geq 0 \\ & z_t \geq 0 \end{align*}\]where \(z_t\) is an auxiliary variable that represents the amount of inventory you carry from period \(t\) to period \(t + 1\). Notice that the constraints require that demand is fully satisfied, and we never have negative orders or inventory.
Solving with Dantzig
This problem is easily solved with dantzig.
import dantzig as dz
p = [0.5, 3.5, 5.0]
h = [1.0, 5.5, 1.5]
d = [50, 75, 100]
d_1, d_2, d_3 = d
x_1 = dz.Variable.nonneg()
x_2 = dz.Variable.nonneg()
x_3 = dz.Variable.nonneg()
x = [x_1, x_2, x_3]
z_1 = dz.Var.nn() # A succinct alias for `dz.Variable.nonneg()`
z_2 = dz.Var.nn()
z_3 = dz.Var.nn()
z = [z_1, z_2, z_3]
purchase_cost = sum(p_t * x_t for p_t, x_t in zip(p, x))
inventory_holding_cost = sum(h_t * z_t for h_t, z_t in zip(h, z))
total_cost = purchase_cost + inventory_holding_cost
problem = dz.Minimize(total_cost).subject_to(
[
x_1 >= d_1,
x_2 + z_1 >= d_2,
x_3 + z_2 >= d_3,
z_1 == x_1 - d_1,
z_2 == x_2 + z_1 - d_2,
z_3 == x_3 + z_2 - d_3,
]
)
soln = problem.solve()
assert soln.objective_value == 637.5
assert soln[x_1] == 125.0
assert soln[x_2] == 0.0
assert soln[x_3] == 100.0
It turns out the optimal solution is to only order in periods one and three!
Dantzig Features
The Dantzig API is designed to be both expressive and terse, saving you keystrokes without sacrificing clarity. Beyond that, Dantzig supports
- Both minimization and maximization problems
- Arbitrarily restricted variables, including completely unrestricted free variables
==,<=, and>=constraints- SIMD-accelerated linear algebra operations
- Modern Python type-checking
Dantzig is still beta software. If you identify a problem, please open a bug report. As they say, a bug found is a bug fixed!