seedmip

A reckoner seed: mip's branch and bound, an integer problem and its answer as dicts — machines/seeds/seedmip.shoddy

Summary

seedmip bridges mip, the machine for problems whose answers must come out whole. It registers MIPPROBLEM, MIPSOLVE and MIPFIXED, plus MPSMIP and MPSMIPLOAD for a file whose columns are marked whole. All five speak the dict shapes seedsimplex already established. That is why this seed includes that one rather than restating what a problem looks like. On a keyboard with two spellings of "linear program", MIPFIXED's answer would not go into LPSOLVE. That round trip is the whole point of MIPFIXED.

Why It's Useful

A linear program — a problem of finding the cheapest plan under limits, where any amount may be fractional — will happily answer 1.6 lorries, 0.37 of a depot, or two and a half bales. None of those is a plan anybody can carry out. The moment a decision is yes-or-no, or a thing is sold in units, the answer has to be whole. And as the bales example the mill ships shows, the whole answer is often not the fractional one rounded — sometimes it is not even close. MIPSOLVE does the search that finds it. It also reports what the search cost in nodes and pivots (subproblems tried, and solver steps within them), so a session can see when it is getting expensive.

No shadow prices, and why that is the useful answer

LPSOLVE hands back dualprices and reduced — the "shadow prices" that say what one more unit of each limit would be worth. They are among the most valuable things it produces. MIPSOLVE hands back neither, and the omission is deliberate rather than unfinished. The duals of whichever node happened to finish last are the sensitivities of that node's linear program, not of your integer problem. An integer problem has no linear-programming duals at all. Reporting them would be a confident answer to a question nobody asked.

What is well defined: the sensitivity of everything else, given the decisions the search made. MIPFIXED pins every integer where the search left it — two one-number rows apiece — and hands back an ordinary problem. LPSOLVE reads it like any other, and its prices mean something. The refusal is a door, not a dead end.

Nothing here aborts

Three things under this seed can abort. mip aborts on an Ints entry naming a variable that does not exist. MipFixed aborts when handed a solution that never found an optimum to pin anything at. The simplex under both aborts on a problem whose matrix does not match its costs and right-hand side. This seed asks all three questions before anything is called, so each becomes a refusal with the stack still on the screen. The MPS words borrow seedsimplex's total validator for the same purpose, told that integer columns are something these two can be handed.

A long search is not an abort, and it is not capped here either. Branch and bound — the search that tries whole answers case by case — solves a linear program per node and may want many of them. The machine stops at a hundred thousand and answers MAXNODES. Wiring a smaller cap in at the keyboard would make this word answer something other than what mip answers, and that is the one thing a bridge must not do. LPSOLVE carries the same risk and the same non-answer to it.

User's Guide

Bales of fibre, which you cannot buy half of: at least ten tonnes, from six-tonne bales costing 5 and four-tonne bales costing 4.

> { 5 4 } 1 2 { 6 4 } MAT { 10 } LPPROBLEM
x: { ( "costs" { 5 4 } ) ( "a" 1x2 { { 6 4 } } ) ( "rhs" { 10 } ) }
> DUP LPSOLVE "cost" DGET
x: 8.333333333
> { 1 2 } MIPPROBLEM DUP MIPSOLVE
x: { ( "status" "OPTIMAL" ) ( "x" { 1 1 } ) ( "cost" 9 )  ... 2 more }

The relaxation — the same problem with the whole-number rule dropped — buys one and two thirds of the cheaper-per-tonne bale for 8.3333. The whole answer is one of each, for 9. That is more than the relaxation, as it always is. And it is not what rounding the relaxation up would have given you.

Then the prices, once the decisions are settled:

> MIPFIXED LPSOLVE "dualprices" DGET
x: { 0.8333333333 0.6666666667 ... }

An MPS file whose columns are marked goes straight in. And if you reach for the plain words by mistake, they say so:

> "mills/simplex-from-mps/files/bales.mps" MPSMIPLOAD MIPSOLVE "cost" DGET
x: 9
> "mills/simplex-from-mps/files/bales.mps" MPSLOAD
?: MPS: THIS FILE MARKS COLUMNS INTEGER — MPSMIP AND MPSMIPLOAD READ THAT, AND EVERY VARIABLE HERE IS CONTINUOUS

And what the rest of the refusals look like:

?: MIPPROBLEM: AN INTEGER VARIABLE IS NAMED THAT DOES NOT EXIST — THERE ARE 2
?: MIPFIXED: THIS SOLUTION IS INFEASIBLE, SO THERE IS NO OPTIMUM TO PIN THE INTEGERS AT
?: MIPSOLVE: NOT AN INTEGER PROBLEM — BUILD ONE WITH MIPPROBLEM

Word Reference

Word	Description
MIPPROBLEM ( problem ints -- mipproblem )	A linear program whose named variables have to come out whole. ints is a LIST of variable positions, counting from 1; an empty one is just the linear program again.
MIPSOLVE ( mipproblem -- solution )	The best whole answer, by branch and bound. status is OPTIMAL, INFEASIBLE, UNBOUNDED-OR-INFEASIBLE, MAXITER or MAXNODES; nodes and iterations say what the search cost. No shadow prices — an integer problem has none. Use MIPFIXED for the ones it does have.
MIPFIXED ( mipproblem solution -- problem )	The linear program left when every integer is pinned where the search left it, as a pair of rows apiece. LPSOLVE it and its shadow prices are the sensitivity of everything else, given those decisions. Refuses a solution that never reached an optimum.
MPSMIP ( text -- mipproblem )	MPS text as an integer problem: the program, plus whichever columns the file marked whole with an INTORG marker or a BV bound. A file that marks none is simply a problem with nothing to branch on.
MPSMIPLOAD ( path -- mipproblem )	Read an MPS file and parse it as an integer problem, the guarded way throughout.

Who Uses It

	User	How
	halifax	The calculator's integer-programming words, under their own WORDS heading.
	sparky	Sparky folds it too, so a model calling `eval` reaches the same words halifax puts at a prompt.

A mill claims this seed by folding RckSeedMip over its reckoner state, which 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.
	mip	The domain this seed bridges: `MipProblem`, `MipOptimize`, `MipSolution` and `MipFixed`.
	mps	`ParseMpsMip`, once the borrowed validator has found nothing wrong with the text.
	reckoner	`RckReg` and the argument readers every registered word is built from.
	seedsimplex	The problem dict itself — `LpProblemCell`, `LpFind`, `LpListNum` — and `LpMpsCheckedMode`, the total MPS validator, so both seeds agree on what a problem is and on which files are readable.
	seq	`All` checks the integer list against the variables that exist.
	simplex	`SpProblem`, which is what a MipProblem is built around.
	sparse	`SpFromMat` and `SpToMat`, the crossings between the keyboard's dense MATRIX and the form the solver walks.