Resource Allocation with Maximize and Minimize

Resource Allocation with Maximize and Minimize

Every week somebody has to decide how many of each thing to make, buy, ship or schedule, with only so many hours, so much material and so much money. The maximize and minimize blocks let you write such a problem down the way you would say it out loud: what you want the most of, what you get to decide, and what you are short of. Sheerpower then works out the best plan. The answer is exact, not an approximation. This page shows how to write the blocks. If you are curious about the arithmetic behind them, it is on the Array Math page in section 8, "Solving Equations" (Array Math Functions, Index Lists & Slices, Solve(), Sort(), and More). That page also shows how to solve the same problem when the numbers are already stored in arrays.

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 of work; a stool uses 2 boards and 6 hours. This week the shop has 29 boards and 36 hours. How many of each should it build to earn the most?

The block has three parts and a closing line, in the order a person would say them.

The goal is the first line. It says maximize (make this as big as possible) or minimize (make it as small as possible), then a name for the result, then how the result is worked out. Here the result is called profit, and it is 35 for every bench plus 15 for every stool.

The unknowns are listed on the where line. These are the numbers Sheerpower gets to choose: how many benches, how many stools. Any other name that appears in the block is an ordinary variable or constant that you have already set.

The limits come after subject to, one per line. Each line says how much of something a plan may use. The word before the colon (boards:, hours:) is a label you choose, and the text after ! is a comment; both are optional. Sheerpower's messages call these lines constraints.

A label does one more thing. After the block runs, it is a variable holding how much of that limit was left over. Here boards is 0, so every board was used and boards are what holds this shop back; hours is 14, so time is not the problem. For an "at least" line the label holds how far past the requirement the plan went, and for an "exactly" line it is always 0. Because a label becomes a variable, it needs a name of its own: not the name of an unknown or of the goal, and not the same as another label.

end maximize closes the block. When it has run, benches, stools and profit are ordinary variables holding the answer, and you can print them or use them in any way you like.

An unknown is never negative. The block looks for the best plan among those where every unknown is zero or more, because you cannot build minus two stools. If something really can go either way, such as a net transfer or a change in stock, write it as two unknowns and take one from the other (added - removed). Each of the two is zero or more.

The shape of a block.

The goal line comes first (more goals may follow it, as section 5 shows), then the where line or lines, then subject to and at least one limit. Putting a then or where line after subject to is an error the compiler reports. Each limit is written on one line, with no continuation onto the next. where and subject to are both required. Blank lines and comment lines may go anywhere inside the block.

2. Whole or Decimal

The where line said are whole, and that is why the answer is 5 and 2 rather than something with a fraction. Change it to are decimal and the block answers for a world where you could build part of a bench:

That plan earns a little more, and it is useless to a woodshop. You might think the fix is to round it off, but rounding to 4 benches and 5 stools needs 30 boards, and there are only 29. Rounding down to 3 and 4 is possible but earns only 165. Even the best nearby plan, 4 and 4, earns 200. The real best plan in whole units is 5 benches and 2 stools. That is about one bench more than the fraction plan and nearly three stools fewer, and no amount of rounding would have found it.

Sheerpower finds it by a search. It first works out the fraction plan. Then it takes one of the unknowns and tries the two whole numbers on either side of its fraction, solving the problem again for each. It keeps doing this, and whenever a line of search cannot possibly beat the best whole plan found so far, that line is dropped. Every plan along the way is worked out exactly, so the final answer is the true best, not a good guess.

Which to choose. Say whole for things you count: benches, shifts, crates, people. Say decimal for things you measure: kilograms in a blend, litres through a pipe, hours of a machine, dollars in a fund. A measured amount really can have a best value of 3.2. Decimal is also much faster to solve. Whole numbers need the search above, and the search can grow steeply as the number of unknowns grows. (A big problem of either kind is better written in the array form, section 8 below.)

A problem can mix the two. Take a different shop, with its own numbers. It has 700 in cash for materials this week. A bench's materials cost 120 and a litre of finish costs 30, both paid from that cash. Once a bench is sold and its materials are paid back, the bench earns 80, and each litre of finish that went on it earns a further 10. A bench takes at most 2.5 litres. The budget line caps the cash spent, and the goal counts what each item earns after its materials:

The names are grouped with commas, and each group ends in are whole or are decimal. The wording never changes, so a group of one still reads finish are decimal. You may also write several where lines. Only the whole unknowns go through the search; the decimal ones simply take whatever value works out best.

3. Writing the Limits

A limit line has something on the left, one of <= (at most), >= (at least) or = (exactly), and something on the right. The numbers that multiply the unknowns do not have to be typed in: they can be named constants, variables, or fields read from a cluster, as long as they do not depend on the unknowns. The goal may also include a fixed amount, such as an overhead, and it comes out in the result:

The demand line changes the plan. The old plan of 5 and 2 makes only seven pieces, so the block settles on 4 and 4, the best plan that makes eight.

Write "at least" with >= and "exactly" with =. There is no < or >. For a counted thing, "fewer than 5" is simply <= 4; for a measured thing, "strictly less than" has no best value to find, since something can always creep a little closer to the line. Unknowns may appear on both sides of a limit, inside parentheses, divided by a number, or with a minus sign.

There is one rule about what a line may contain. Each unknown may be multiplied by a plain number and the results added up, and that is all. You cannot multiply two unknowns together, square one, or put one inside a function. The mathematical word for lines like this is linear, which is the word the messages use. Break the rule and the compiler stops, naming the block, the line (by its label if it has one) and the offending part:

A label only names its line in messages like this one. It does not change the plan.

Rules for the names. An unknown is a plain variable name. It may end in a type mark, so benches% holds the answer as an integer. It cannot be an array element or a cluster field. The name does not need to exist before the block; if it does, the block overwrites its value with the answer. Any name in the block that is not on a where line is treated as a number you already know, so it must already have a value. If it does not, you get the same "unassigned variable" error as anywhere else.

4. 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 gives 2 points and costs 12. No more than 4 day shifts and 6 night shifts can be staffed. What is the cheapest way to reach 17?

minimize is the same block, but the goal is made as small as possible, and it ends with end minimize. A minimize block nearly always needs an "at least" line or an "exactly" line. Without one, the cheapest plan is to do nothing at all. The one exception is a thing that saves money the more of it you do; if nothing limits it, the cost can fall forever and there is no answer (section 7).

5. Two Goals: the Machine Shop

A machine shop makes brackets and hinges. A bracket earns 20 and uses 2 machine-hours and 1 kg of steel; a hinge earns 30 and uses 3 machine-hours and 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, and among the most profitable plans, the one that uses the least steel.

Two goals usually cannot both be met at once, but they can be put in order. First find the best profit. Then, looking only at plans that earn that profit, find the least steel. You write the goals in that order with then, and the limits they share are written once:

Here is how it works. The first goal is solved. Its best value is then added to the block as one more limit, so that no later plan may do worse on it. The second goal is solved with that extra limit in place, and so on down the list. Every goal's name gets its value.

In this shop both products earn 10 per machine-hour, so every plan that uses all 60 hours earns 600, and there are several such plans. The second goal picks between them. Among those plans, the steel used works out to 30 kg plus half a kilogram for every hinge, so the least steel means the fewest hinges, and the standing order fixes that at 4. Adding a goal's best value as a limit can only narrow the choices; it never widens them, and sometimes it does not narrow them at all. Here the profit limit says nothing that the machine-hours limit had not already said.

A third then ranks below the second, and so on. A block may have at most as many goals as it has unknowns; the compiler checks this. The block is closed by the keyword of its first goal, which is why this one ends with end maximize although its second goal is a minimize. A later goal can always be met, because the plan found for the earlier goal already satisfies the new limit. It can, however, have no smallest or largest value if nothing limits it (section 7).

When a goal has several equally good plans, as the first goal here does, Sheerpower returns one of them. The same program returns the same plan every time, but which of the equal plans it picks is not something to rely on. If the choice matters, add a second goal with then to say what you prefer.

The same two goals can be written as two blocks. The first block finds the profit; the second block treats that profit as a limit it must not fall below. Any name in a block that is not an unknown is just a number to it, so a variable set by an earlier block works fine:

The two-block form is worth knowing when the second problem differs from the first in more than its goal. A block changes only its own goal name and its unknowns, so profit keeps the value the first block gave it.

Carrying a plan exactly. The keep line in the second block only works because the first block's answer is exact. That is true even when the answer has a fraction in it. The decimal woodshop plan in section 2 is really the fractions 51/13 benches and 2700/13 profit, and Sheerpower keeps them as those fractions (fraction$(benches) shows 51/13). Check that plan against its own limits and it uses exactly 29 boards, and a second block sees exactly the limit it was found under. The digits you see printed are rounded for display; the value stored is not. Exactness gives out only where it always does in Sheerpower: when a fraction's bottom number passes 4,294,967,295, or when a rounded decimal is mixed into the arithmetic (Internals: REAL and String Data Types).

6. What One More Board Is Worth

A plan answers "how many". The next question is always "what should I change". The labels answer half of it: a limit with room to spare is not holding the shop back. For the limits that are used up, Sheerpower can also say how much the goal would improve if that limit were loosened by one unit. When every unknown is decimal, each label gets a second variable, the label with _worth on the end:

Read it this way. If one more board turned up, the best plan would earn 6.92 more; a board is nearly a fifth of a bench. An extra hour is worth only 19 cents, because hours are barely in the way. So the manager who can buy boards or hire hours knows which to do, and what a board is worth paying for. The last line is a check that always holds for a decimal plan: every unit of every limit, times what it is worth, adds up to the goal exactly. Sheerpower keeps these values as exact fractions too (fraction$(boards_worth) is 90/13).

The sign follows the goal. In a maximize block loosening an "at most" line can only help, so its worth is zero or more. In a minimize block loosening it can only lower the cost, so the worth is zero or less, and for an "at least" line the worth says how much the cost rises when the requirement rises by one:

A point of coverage costs 6, half a night shift, because that is where the next point would come from. Allowing one more day shift saves 8: it brings 3 points for 10 instead of a night and a half for 18. The night cap has room to spare, so it is worth nothing. A limit with slack is always worth 0.

Whole numbers have no such figure. If any unknown is whole, the block does not create the _worth variables, and using one is the ordinary "unassigned variable" error when the program compiles. That is on purpose. With whole units, one more board may change nothing at all until there are enough boards for another bench, so no single number tells the truth. Run the block twice with the limit changed and compare the goals. In a block with then goals, the worth is measured against the first goal.

7. When There Is No Plan

Two things can go wrong, and each raises an exception you can catch (see Exception Handling). INFEASIBLE means no plan fits all the limits. With whole unknowns it also means no whole-number plan fits, even though a plan with fractions would. UNBOUNDED means the goal can keep growing forever because some limit was left out. The message says which it is. Here a fraction plan exists (a and b adding up to 1.5) but no whole-number plan does:

The message names maximize(), the function that a block turns into behind the scenes. After either exception, the unknowns and the goal name keep whatever values they had before, because a block stores an answer only once it has one. Here a, b and made are brand new, so they hold 0, as any new variable does. With then goals this happens goal by goal. If the second goal is the one that fails, the first goal's plan and value are already stored; only the failing goal's name is left untouched.

8. The Array Form, for Problems That Arrive as Data

A block is for a problem small enough to write out by hand. Sometimes the products are rows in a cluster and the resources are columns in a table, and there are no names to type. Then the same solver is available as a function that takes arrays: one list of what each unknown earns, one grid with a row for each limit and a column for each unknown, and one list of the limits. Here is the woodshop again in that form:

minimize(c, a, b) is the matching function. whole: true makes every unknown a whole number. To make only some of them whole, pass an array of 1s and 0s instead, one per unknown:

Leave the option out and the plan may have fractions. In this form every limit must be an "at most" row: an "at least" row is written with all its numbers negated, and an "exactly" row as two rows, one each way. There is no array form for ranked goals; write the two-block pattern from section 5 by hand, adding the first answer as an extra row. The Array Math page (section 8, Problem 4) covers this form in full, including why the answers are exact, the size rule described below, and the exact: false option for very large problems. A block is turned into this call behind the scenes, so everything said there applies to blocks as well.

The worth of each limit (section 6) has an array form too: marginal(c, a, b) gives one value per row, for making c as large as possible; add minimum: true when the goal is to make it as small as possible. It takes the same exact: option as maximize(), and it has no whole: option, for the reason section 6 gives.

9. Limits on Size

How big a block can be. The exact arithmetic is used as long as the number of unknowns plus the number of limits is 128 or fewer. A block knows its size while it is being compiled, so a bigger block is reported as a compile error. The message gives the count (an "exactly" line counts as two, and each then goal adds one) and points you to the array form, where exact: false solves the same problem with ordinary rounded computer arithmetic, which is much faster on big problems. A block does not have an exact: option of its own yet.

How long the whole-number search may run. The search for whole numbers can grow steeply when there are many whole unknowns. It is allowed to solve up to 100,000 versions of the problem. Past that it stops and raises NUM_OUTOFRANGE rather than running on, and it gives no partial answer.

10. What This Is Not

Finding every exact combination. "Which stamps make exactly 47 cents?" has no goal to make big or small and no supply to run out of. It asks for whole numbers that hit a total exactly, and every answer counts, not just one best one. That is a different tool, diophantine(), Problem 5 on the Array Math page. The two meet in the middle: a block with an "exactly" line and whole unknowns finds the best of the exact answers, while diophantine() describes all of them.

Curved goals. If a goal or a limit multiplies two unknowns together, or squares one, it breaks the rule in section 3, and the compiler says so. Some such problems can be rewritten to fit the rule by choosing different unknowns; the rest need a different method altogether.