|
Resource Allocation with Maximize and Minimize |
Resource Allocation with Maximize and Minimize
Every week somebody decides how many of each thing to make, buy, ship
or schedule from a limited stock of hours, material and money. The
maximize and minimize blocks state such a
problem the way it is told — a goal, the things being decided,
the limits — and hand back the best plan, exactly. This page is
about writing those blocks. The arithmetic behind them, the exact
simplex, is on the Array Math page (Array Math Functions, Index Lists & Slices, Solve(), Sort(), and More, section 8),
which also holds the array form of the same call for problems that
arrive as data.
1. The Woodshop: a Goal, the Unknowns, the Limits
A woodshop makes benches and stools. A bench earns 35, a stool 15. A bench uses 5 oak boards and 2 hours; a stool 2 boards and 6 hours. This week there are 29 boards and 36 hours. How many of each should be built?
Three parts and a closing line, in the order a person would say them. The goal
is the first line: maximize (or minimize), the
variable that will hold the best value, and the expression to make as
large as possible. The unknowns are listed in the
where line: these are the quantities the block chooses, and
every other name in an expression is an ordinary variable or constant.
The constraints follow subject to, one per
line, each with an optional label and an optional comment.
end maximize closes it. Afterwards benches,
stools and profit are plain variables holding
the answer.
The unknowns are never negative: the block looks for the best plan
among those where every unknown is zero or more, which is what a
quantity of things means. A quantity that can go either way — a
net transfer, a change in stock — is written as two unknowns,
one subtracted from the other (added - removed), each of
them zero or more.
The names. An unknown is a plain scalar name; a sigil
is allowed (benches% holds the answer as an integer), an
array element or a cluster field is not. It need not exist beforehand,
and if it does its value is overwritten by the answer. A name in an
expression that is not in any where line is an ordinary
variable read as a coefficient, so it must already hold a value: an
unassigned one gives the same compile error as anywhere else. There is
no default: a quantity the block should choose must be named in
where. A new unknown holds 0 until a plan is found, as any
new variable does.
The shape of a block.
The goal lines come first, then the where line (or lines),
then subject to and at least one constraint; a
then or where line after subject to
is a compile error. A constraint is one line, with no continuation onto
the next. where and subject to are both
required. Blank lines and comment lines may sit anywhere inside.
2. Whole or Decimal
The where line said are whole, and that is
why the answer is 5 and 2. Change it to are decimal and
the block answers for a world where a bench can be built in part:
That fractional plan is the higher number, and it is the wrong answer for a woodshop. Rounding it to 4 and 5 needs 30 boards, and there are 29; truncating to 3 and 4 is possible but earns only 165, and even the best nearby whole plan, 4 and 4, earns 200. The whole-unit best is 5 benches and 2 stools — about one bench more than the fractional plan and nearly three stools fewer, a plan no rounding reaches. The block finds it by branch and bound: the fractional plan is solved, the quantity furthest from a whole number is split into two cases — here the stools, 4.69 being further from a whole than 3.92, so stools at most 4 or at least 5 — each case is solved again, and a case that cannot beat the best whole plan so far is dropped. Every plan along the way is exact, so the answer is the true optimum. The search is capped at 100,000 linear programs; past that it raises rather than running on.
Which to choose. Say whole for things
that are counted — benches, shifts, crates, people — and
decimal for things that are measured — kilograms in a
blend, litres through a pipe, hours of a machine, dollars in a fund.
A measured quantity's best value really can be 3.2, and the decimal
search is also far cheaper: the simplex is quick even for hundreds of
unknowns — though a block that large needs the array form with
exact: false, section 8 — while the whole-unit search
can grow steeply with their number. A problem can mix the two. A
different shop, with its own numbers: each bench earns a net 80, and
each litre of finish put on it earns a further net 10, at most 2.5
litres per bench. Materials are paid up front — 120 a bench, 30 a
litre — from a weekly budget of 700. The budget row caps the
spending; the goal counts the net earnings:
Groups are separated by commas, each group ending in are whole
or are decimal; the wording is fixed, so a single name still
reads finish are decimal. Several where lines
are fine too. Only the whole unknowns are branched on; the decimal ones
take whatever value is best given them.
3. How Exact the Answer Is
A decimal plan whose vertex
is a fraction comes back as that fraction: fraction$(benches)
is 51/13 and fraction$(profit) is
2700/13, so re-checking the plan against its own rows gives
exactly 29 boards, and a plan carried into a second block, the pattern
section 6 shows, meets the limit it was found under. Printed, a
fraction shows sixteen decimal places, which is the display of an exact
value, not a rounded store. Exactness ends only where it always does in
Sheerpower: a fraction whose denominator passes a million, or
arithmetic with a non-whole decimal beside it, becomes a sixteen-place
decimal (see Exact Fractions: the RATIONAL Mode).
4. Writing the Constraints
A constraint is a linear expression, one of <=,
>= or =, and another linear expression. A
coefficient may be any expression free of the unknowns — a named
constant, a variable, a cluster field — and the goal may carry a
constant term, which comes out in its variable:
The demand row changes the plan: 5 and 2 make seven pieces, so the block settles on 4 and 4, the best plan that makes eight.
A "greater than" requirement is written as itself, and a row
that must balance exactly uses =; there is no
< or >: for a measured quantity a plan
that must stay strictly under a limit has no best member, and for a
counted one < 5 is written <= 4.
Unknowns may appear on both sides, in parentheses, divided by a number,
or negated. The one rule is that every expression is linear
in the unknowns: an unknown may be added, subtracted, multiplied or
divided by an unknown-free number. A product of two unknowns, a
power, or a function of an unknown is a compile error that names the
block, the constraint (by its label when it has one) and the term:
A label names its row in messages like that one; it does not change the plan. Blank lines and comment lines inside the block are skipped.
5. Minimize: the Least Cost That Still Covers the Need
A schedule needs 17 coverage points this week. A day shift gives 3 points and costs 10, a night shift 2 points for 12; no more than 4 day shifts and 6 night shifts can be staffed.
minimize is the same block with the goal made as small as
possible, closed by end minimize. When every cost is
positive a minimum needs at least one >= row or an
= row, or the cheapest plan is to do nothing; a negative
cost on an unknown with no limit makes the goal unbounded instead.
6. Two Goals: the Machine Shop
A machine shop makes brackets (profit 20, 2 machine-hours, 1 kg of steel) and hinges (profit 30, 3 machine-hours, 2 kg of steel). This week there are 60 machine-hours and 50 kg of steel, and a standing order requires at least 4 hinges. Steel is on back-order, so the manager wants the most profitable plan that uses the least steel.
Two goals cannot be optimized at once, but they can be ranked: the
best profit first, then, among the plans that earn it, the least
steel. Written with then, the goals come in rank order
and the constraints they share follow once:
Each goal is solved among the plans that meet the goals before it:
after a goal is solved, it is pinned at its optimum as one more
constraint, exactly, and the next goal is solved with that pin in
place. Every goal's variable is set. Here both products earn 10 per
machine-hour, so every plan that uses all 60 hours makes 600 and
there are several of them; the second goal settles it, because the
steel used is 30 plus half the hinges and the order fixes the fewest
hinges at 4. A third then ranks below the second, and so
on, up to one goal per unknown: each pin fixes one more direction of
the plan, and after as many pins as unknowns nothing is left to
choose. The first goal's keyword closes the block, which is why this
one ends with end maximize although its second goal
minimizes. A later goal can never be infeasible, since the plan found
for the earlier goal already meets the pin, but it can be unbounded if
nothing limits it.
When a goal has several best plans, as the first one here does, one
of them comes back; the same program gives the same plan every time,
but which of the ties it is not something to build on — rank a
second goal with then if the choice matters.
The same ranking can be written as two blocks, with the first goal's variable used as a floor in the second — any expression free of the unknowns is a constant to a block, a variable included:
That form is worth knowing when the second problem differs from the
first in more than its goal. Note that a block writes only its own
goal variable and the unknowns, so profit keeps the value
the first block gave it.
7. When There Is No Plan
Two exceptions, both catchable (see Exception Handling):
INFEASIBLE when no quantities satisfy every constraint
— and, under whole, when no whole-number plan does
even though a decimal one would — and UNBOUNDED
when the goal can grow without limit because a limit is missing. The
message says which case it is. Here a decimal plan exists (a and b
summing to 1.5) but no whole one:
The message names the function a block compiles into, maximize().
After either exception the unknowns and the goal variable keep the
values they had — here a, b and
made are new, so they hold 0 — because a block stores
a goal's answer only once that goal's plan is found. With
then that is goal by goal: if
the second goal is the one that fails, the first goal's plan and its
variable are already stored, and only the failing goal's variable is
untouched.
Two more limits raise. When unknowns plus constraints exceed 128, a
block raises EXACTCHOICE; the count is taken after the
block's expansion, so an = row counts as two and each
then goal adds one. A block has no exact:
option yet, so a problem that large is written in the array form
below with exact: false. And a whole-unit search that
passes 100,000 linear programs raises NUM_OUTOFRANGE.
8. The Array Form, for Problems That Arrive as Data
A block is written for a problem small enough to write down. When the products are rows of a cluster and the resources columns of a table, there are no names to write, and the same solver is a function taking arrays: the goal's coefficients as a vector, the constraints as a matrix with one row per limit and one column per unknown, and the limits as a vector. The woodshop again:
whole: true holds every unknown whole, an array of 0s and
1s (whole: is_whole, where is_whole is that
array) holds only some, and without the option
the plan is decimal. A "greater than" row is written with
negated coefficients and a negated limit, and an exact row as two rows.
The Array Math page, section 8, Problem 4, covers this form in full:
why the answer is exact, the size rule when unknowns plus constraints
exceed 128, and exact: false for the
double-precision kernel. A block compiles into this call — a
>= row as a negated row, an = row as two,
and each then goal as a further call with the finished
goal pinned as one more row — so everything said there holds for
blocks too.
9. What This Is Not
Every exact combination. "Which stamps make exactly 47
cents?" has no goal and no limit; it asks for whole numbers that
meet an equation exactly, and every such answer counts. That is
diophantine(), Problem 5 on the Array Math page. The two
meet in the middle: a block with an
= row and whole unknowns finds the best of the
exact answers, while diophantine() describes all of them.
Curved goals. A goal or a constraint that multiplies two unknowns, or squares one, is not linear, and the block says so at compile time. Some such problems become linear with a change of variables; the rest need a different method.
The value of one more board. A fractional plan also carries the price of relaxing each limit by one unit, the dual value; the solver does not report it yet. Until it does, run the block twice with the limit changed and compare the goals. For a whole-unit plan there is no such price in the usual sense, so running it twice is the method there, not a stopgap.
