The Mills · Optimization

simplex-from-mps

An LP solver from an MPS file — mills/simplex-from-mps

Summary

simplex-from-mps is the smallest mill and the most industrial: a command-line solver for linear programming — the mathematics of finding the best possible answer (biggest profit, lowest cost) under a set of limits. Hand it an MPS file, a plain-text problem format explained below, and it does the whole job. It loads the model with the mps machine and optimizes with the simplex machine. Then it reports the works: the status, the objective value (the number being maximised or minimised), the nonzero variables, and the sensitivity analysis — how the answer would move if the problem moved. That analysis has two parts. Shadow prices say what one more unit of each limit would be worth, per normalised constraint row (an equality row appears as its +/− pair). Reduced costs say, per variable, how far each unused variable is from being worth using. The -z (or --zero-lower) switch forces a zero lower bound — x ≥ 0 — on every variable, skipping a BOUNDS section instead of reading it as rows.

If the file marks any of its columns as whole numbers, the mill notices. It answers by branch and bound instead — a search that splits the problem on each whole-number choice and discards branches that cannot win — using the mip machine. It reports the relaxation's answer (the same problem with the whole-number rule dropped), the integer one, and how many nodes and pivots the search took. Shadow prices for an integer answer are not the integer problem's own. No integer problem has them: the linear-programming dual, the mathematics behind shadow prices, does not survive the whole-number rule. So the mill pins every integer where the search left it and reports the shadow prices of the LP that remains. That question does have an answer.

The Format and the Problem

MPS is the FORTRAN punch card that refused to die. (FORTRAN is one of the earliest programming languages; a punch card is the stiff paper card that programs and data were once typed onto.) It is the input format of IBM's Mathematical Programming System for the System/360, from the 1960s: fixed sections (ROWS, COLUMNS, RHS, BOUNDS), one coefficient per line, names in fixed columns. Half a century later it is still the shared language of linear programming. Every serious solver reads it, and the classic test problems circulate in it. The bundled files/blend.mps is one of those classics: the BLEND oil-refinery blending problem from Bruce Murtagh's Advanced Linear Programming. files/mix.mps is a smaller worked example to read first. files/bales.mps is the integer one: three variables, an answer worked out by hand in its own header, and a relaxation that recommends buying a fraction of a bale and taking a job lot that turns out not to be worth having.

Running It

From mills/simplex-from-mps/ — the wrapper is ./build.sh, or ./build.ps1 on Windows:

./build.sh build              # weave the program into bin/ (plain ./build.sh works too)
./build.sh run files/blend.mps
./build.sh clean              # remove built binaries

Like demographics, this mill is woven: once built it is a self-contained command-line program that runs with no toolchain —

dotnet bin/simplex-mps.dll files/blend.mps
dotnet bin/simplex-mps.dll files/mix.mps -z
dotnet bin/simplex-mps.dll files/bales.mps

The FILE argument is required; the run aborts without one.

How It's Built

Short as it is, this mill is mostly a demonstration of how much the machines already do. mps parses the file into a model. It hands that to simplex or, if the file wants whole numbers, to mip. What remains here is the reporting: filtering the solution down to its nonzero entries and printing shadow prices and reduced costs against their row and column names. It's the pattern to copy when you want a Shoddy program that behaves like a classic Unix tool — arguments in, report out, woven once to a .dll and run anywhere .NET runs.

The file is read once, whichever kind it turns out to be. An MPS file with no integer columns parses perfectly well to a MipProblem that simply has nothing to branch on. So the mill asks for that, looks at whether the integer list is empty, and picks its reporter. It never has to parse once to find out and again to do the work.

It is also the only single-source-file mill, and that's not an accident. The other mills split so that their pure model can be tested apart from their I/O — their input and output. Here the pure model, parsing and solving, lives entirely in the machines, and the machines carry their own tests. What's left is all reporting, and there's nothing to split.

The Machines It Uses

	Machine	Why
	mps	Parses the ROWS / COLUMNS / RHS / BOUNDS sections into a model. It normalises the rows, turns a bound into a row of its own, and hands it all back with names attached — plus the -z zero-lower-bound behaviour.
	simplex	SpOptimize solves what the file describes: the solution status and objective, and the sensitivity numbers — shadow prices and reduced costs — the report prints.
	mip	For a file with integer columns: MipOptimize for the answer and its node and pivot counts, then MipFixed for the sensitivity that is honestly available once the whole numbers are settled.
	sparse	The form the constraints stay in from file to solver — sparse storage keeps only the nonzero numbers. SpNnz is what lets the report say how many numbers a problem actually holds against how many cells it would have taken.
	str	StartsWith reads the command-line flags, and Join builds the little MPS text the test suite checks the BOUNDS translation against.
	seq	Contains spots -z among the arguments, and Flatten builds the labels for the pinning rows MipFixed adds.
	matrix	The dense Matrix — every cell stored, zeros included — that a plain Problem carries. The test suite names it so it can check that the sparse road and the dense one arrive at the same place.