The Machines · Runtime stack

seedsimplex

A reckoner seed: simplex's linear programming, a problem and its solution as dicts — machines/seeds/seedsimplex.shoddy

Summary

seedsimplex bridges simplex into the calculator, giving it LPPROBLEM and LPSOLVE. Per R4.16, a design rule, there is no PROBLEM or SOLUTION cell at the keyboard. Both are dicts — lists of name-and-value pairs, the same LIST-of-PAIR shape seeddict already established. So DGET "status" answers a solution's status, and DGET "x" its variables. This seed never has to name a word for either. LPPROBLEM checks the costs and the right-hand side against the matrix's own shape before building anything. Optimize is total — it always answers — over a well-formed problem. A mismatched one is exactly the malformed input this seed should refuse rather than hand onward.

Why It's Useful

Optimize is total over a well-formed problem: there is no Error anywhere in simplex.shoddy. So the only thing that can go wrong is the problem itself. That is exactly what LPPROBLEM refuses to build: costs that do not match the matrix's columns, or a right-hand side that does not match its rows. Everything past that point answers, whatever the numbers are. That is why a status of UNBOUNDED or INFEASIBLE is a value on the stack — the calculator's working pile — rather than the end of the session.

Reading an MPS file

An MPS file is the standard text format a linear program travels in. It is how a problem actually arrives — from a modelling tool, a textbook, a colleague. A session that can only build a problem by typing its matrix out by hand cannot read the file anybody would hand it. MPSLOAD and its four companions bridge mps. They answer the same problem dict LPSOLVE reads.

This one needed a different kind of guarding from every other bridged word in the tree. Elsewhere a word is made safe by asking the machine's own question first: FINIRR checks the bracket FinIrr would abort on, and ENGINTEGRATE checks the n EngIntegrate would abort on. mps cannot be guarded that way. An earlier pass recorded exactly that as the reason to leave it out. Its dozen aborts are scattered through a fold over the lines — a loop that walks the file line by line — so there is no one question to ask beforehand that answers "will this parse".

So the seed builds the missing counterpart. MpsWhy is a total reader — one that always answers, never aborts. It walks the same lines, in the same sections, applying the same rules. It answers the first thing wrong as prose, or nothing at all. Only then is ParseMps called, on text now known to parse.

That is a second scanner, and the drift is the cost. If mps grows a section, this validator has to learn it too. Otherwise a file the parser now accepts is refused here. Two things hold them together. First, the tokenizer — the code that splits a line into fields — is not copied: Fields is mps's own word, called here. Second, every branch of the validator names the mps line it mirrors. It is still a cost. The alternative was a word that ends a calculator session on a malformed file.

It also catches two faults mps does not have a check for at all. A ROWS line of one field is read past the end of by the parser. And Val is strtod: it answers 0 for anything it cannot read. So a COLUMNS or RHS field of prose parses silently as a zero coefficient — a different linear program, solved confidently. Here every numeric field is checked with IsNumeric, which is the question Val does not ask.

User's Guide

Here is the supplement mix — minimize 5X + 7Y subject to 2X + Y ≥ 8 and X + 2Y ≥ 10. It is read off disk from mills/simplex-from-mps/files/mix.mps and solved, then asked what its columns were called:

> "mills/simplex-from-mps/files/mix.mps" MPSLOAD
x: { ( "costs" { 5 7 } ) ( "a" 2x2 { { 2 1 } { 1 2 } } ) ( "rhs" { 8 10 } ) }
> LPSOLVE "cost" DGET
x: 38
> "mills/simplex-from-mps/files/mix.mps" MPSLOAD LPSOLVE "x" DGET
x: { 2 4 }

A malformed file gets a reason, in place of an ended session:

?: MPS: BAD ROW SENSE Z — A ROW IS N, G, L OR E
?: MPS: A COLUMNS LINE HAS oops WHERE A NUMBER SHOULD BE
?: MPS: A MI BOUND LETS A VARIABLE GO NEGATIVE, AND EVERY VARIABLE HERE IS ZERO OR ABOVE
?: MPS: THIS FILE MARKS COLUMNS INTEGER — MPSMIP AND MPSMIPLOAD READ THAT, AND EVERY VARIABLE HERE IS CONTINUOUS
?: MPS: THERE IS NO OBJECTIVE (N) ROW

What the second scanner cost, once

The paragraph above calls drift the price of a second scanner, and the price came due. mps learned to read a BOUNDS section as the rows a bound actually is. This validator had not. For a while the keyboard refused files the machine underneath could answer perfectly well. It knows them now: LO, UP, FX, BV and PL. MI, FR and a negative UP are still refused, because they let a variable go negative. The validator also remembers the column names as it goes. BndRows aborts on a bound naming a column COLUMNS never declared, and that is a question you cannot ask without having listened.

Word Reference

Word	Description
LPPROBLEM ( costs a rhs -- problem )	A linear program: minimize costs . x s.t. a x >= rhs, x >= 0. Refuses if costs or rhs do not match a's shape.
LPSOLVE ( problem -- solution )	The optimum. status is OPTIMAL, UNBOUNDED, INFEASIBLE or MAXITER.
MPSPARSE ( text -- problem )	MPS text as a problem, normalised to a x >= rhs. Refuses, naming the first line at fault, rather than reading a file it does not fully understand.
MPSPARSEZERO ( text -- problem )	The same, forcing x >= 0 on every variable so a BOUNDS section is skipped instead of read as rows.
MPSLOAD ( path -- problem )	Read an MPS file and parse it, the guarded way throughout.
MPSLOADZERO ( path -- problem )	The same, forcing x >= 0 on every variable.
MPSNAMES ( text -- dict )	What the problem's columns and rows were called: a dict with vars and cons. An E row appears as its NAME+ and NAME- pair, matching how it was split, and a bound as NAME.LO or NAME.UP. Reads the file the same way MPSPARSE does, so the labels always line up with the rows they label.

Who Uses It

	User	How
	halifax	The calculator's linear-programming words: LPPROBLEM and LPSOLVE, and the five that read an MPS file into one.
	seedmip	The problem dict and the MPS validator both. An integer problem is built around an ordinary one, so MIPFIXED's answer goes straight into LPSOLVE. That only works because there is one spelling of "problem", and this seed owns it.
	sparky	Sparky folds it too, so a model calling eval reaches the same words halifax puts at a prompt.

A mill — a complete Shoddy program — claims this seed by folding RckSeedSimplex over its reckoner state. That is all halifax does.

The Machines It Uses

	Machine	Why
	cuttle	The Cell type every bridged word reads its arguments from and answers into.
	matrix	The Matrix cell a problem's constraint matrix already is.
	mps	ParseMps itself, once the seed's own validator has found nothing wrong with the text — and Fields, so the validator tokenizes a line exactly as the parser does.
	reckoner	RckReg and the argument readers every registered word is built from.
	seq	List plumbing under the Problem/Solution dict converters.
	simplex	The domain this seed bridges: Problem, Optimize, Solution.
	str	Split, StartsWith and Upper: the validator walks the same sections and the same line shapes.