Module lp 

Linear programming: the simplex method, interior point methods, duality, and the classical models that reduce to a linear program.

This module sits alongside the continuous optimisers in the parent module rather than replacing them. Those search a smooth objective by following gradients or shrinking a simplex, and stop at a local optimum. A linear program has no local optima to stop at: the objective is linear and the feasible region is a convex polyhedron, so any local optimum is global and at least one optimum sits at a vertex. That is the whole reason the subject exists as a separate discipline, and why an exact answer is available where a nonlinear problem admits only an approximation.

Two solvers are provided because they fail in different ways. The simplex method walks vertex to vertex along the boundary, and terminates in an exactly optimal basis, but its worst case is exponential and it can cycle in the presence of degeneracy – handled here by Bland’s rule, which guarantees termination at the cost of speed. The interior point method approaches the optimum through the middle of the region, takes a number of iterations that barely grows with problem size, and never lands exactly on a vertex. Running both on the same problem and comparing is the cheapest real check available on either.

Duality is the organising idea. Every linear program has a dual whose optimal value equals its own, and whose optimal solution is the vector of rates at which the primal objective responds to relaxing each constraint. Those rates – shadow prices – are usually worth more than the solution itself, since they say which constraint to attack. The convention used here is stated once and adhered to throughout:

duals[i] is the derivative of the reported objective with respect to b[i].

That definition is what makes the sensitivity ranges mean something, and it is what the tests check: perturbing a right-hand side within its range changes the objective by exactly duals[i] times the perturbation.

Structs

LpProblem

A linear program.

Enums

Cmp

The sense of a constraint row.

LpResult

What a solver concluded.

Functions

chebyshev_center

The Chebyshev centre of the polyhedron {x : a_i . x <= b_i}: the point furthest from every face, and that distance.

diet_problem

Stigler’s diet problem: the cheapest combination of foods meeting every nutritional minimum.

dual_simplex

The dual simplex method, started from a given basis.

interior_point

Solves a linear program by a primal-dual path-following interior point method.

l1_regression_lp

Least-absolute-deviations regression, solved as a linear program.

linf_regression_lp

Chebyshev (minimax) regression, solved as a linear program.

lp_dual

The dual linear program.

lp_from_str

Parses a linear program from text.

production_planning

A production plan: how much of each product to make to maximise profit under resource limits.

sensitivity_ranges

Ranges over which the optimal basis survives, as (objective coefficient ranges, right-hand side ranges).

simplex

Solves a linear program by the two-phase simplex method.

transportation_problem

The transportation problem: ship from sources to sinks at least cost.

two_player_zero_sum_lp

Solves a two-player zero-sum game, returning (row strategy, column strategy, value).