Optimisation: Finding the Best Answer Under Constraints

Optimisation means choosing the values of a few decisions so that one stated quantity comes out as large, or as small, as it can. Every stated rule has to hold at the same time. Three things go on paper: what may be decided, what counts as better, and what is allowed. If one of them is left unwritten, the answer is a guess. The invented Amaltas workshop's best allowed plan is eight plain crates and six lined crates a day.

Almost nothing is needed to start. Counting, a little division, and the ordinary human belief that one way of spending a day can be worth more than another. None of it needs calculus, matrix algebra or finance. One word trips people more often than any other, and that word is contribution. A reader who can add a column of figures and tell whether twenty one is more than twenty is equipped.

What three things does an optimisation problem need written down?

Start somewhere ordinary. A stall outside one office building fries samosas and vadas. The oil, the flour and the potatoes arrive in fixed quantities each morning, one fryer can only do so much before the lunch rush ends, and the two items do not earn the same amount. So the stall has a genuine question every single morning: how many of each? And it almost certainly answers that question in its head, from habit, without writing anything down.

An optimisation problem is that same question with three specific things committed to paper: what may be decided, what counts as better, and what is allowed. Miss any one of them and there is nothing to solve, only something to argue about. Write all three and the question stops being a matter of judgement and becomes a matter of arithmetic. Arithmetic is much easier to check and much harder to fudge.

The three are worth taking one at a time. The first is the list of quantities somebody is free to set. Not everything about the day is open to choice, and the things that are not belong in the third list rather than the first. The second is the single number to be pushed as high as it will go, or as low, if the number is something like waste or time. The objective has to be one number. Two numbers is two problems. The third is the list of statements that any answer must satisfy to count as an answer at all, and it is the one people leave in their heads. The limits feel obvious to whoever is standing in the workshop and completely invisible to anybody else, including a solverSoftware that hunts for the best allowed answer once a problem has been typed into it. What a solver does, and the several ways it can be confidently wrong, are covered separately..

Notice the thing all three have in common. Every one of them is written by a person. None of them is discovered in the data, measured off the shop floor or handed down by anybody. Somebody decides that the number worth pushing up is the day's contribution rather than the number of crates or the number of happy customers, and that decision is an act of judgement sitting underneath a stack of arithmetic that looks entirely objective. Every later disagreement about an optimisation result turns on that judgement, so keep hold of it.

What is the Amaltas workshop actually allowed to decide?

The Amaltas workshop carries every worked figure below, and it makes two things and nothing else: a plain crate and a lined crate. There is no third product waiting in the wings, no side business, and no question of changing what it makes. The only question is how many of each, today.

So the whole plan for a day is two numbers, and a quantity somebody is free to set like that is called a decision variable. They are the plain crate count and the lined crate count. Eight and six is a plan. Eleven and nothing is a plan. Nothing and nothing is a plan too, and a poor one, but it is on the list. Anything that can be said about the workshop's day is a statement about those two numbers.

Why two? Because two is what makes this drawable. Two numbers are a point on a chart: run the plain count across and the lined count up, and every conceivable plan is one dot in that picture. Three decisions would need a room and a model built inside it. A place making forty things has forty decisions and nothing to look at whatsoever. The arithmetic is identical in all three cases. Only the ability to look at it changes. A teaching case is built with two and not forty for precisely that reason.

Be careful about one confusion here. Nothing at this stage trips more people. The boards, the hours and the cloth are not decisions. The workshop does not choose how many boards arrive. They arrive. The workshop chooses how to spend them, and a decision variable holds exactly that choice.

What counts as better, and how does that become one number?

Treatments of this subject usually begin, at about this point, to assume some knowledge of finance. One term does all the work, and it can be built from nothing but arithmetic.

When the Amaltas workshop makes and sells one plain crate, money comes in. Against that, some things were bought specifically because that crate was made: the boards that went into it, the glue, the nails. Take the second away from the first and what is left is the crate's contribution. Contribution is what one crate leaves behind after the things bought for that crate have been paid for, and it is emphatically not profit. A plain crate leaves Rs 300/-. A lined crate leaves Rs 450/-.

Why is it not profit? Because the workshop also pays for things that arrive whether the day is busy or idle. The rent does not care how many crates were made. The wages do not either. Nor does the standing orderA repeating purchase that goes out on its own every morning unless somebody cancels it. The order arrives and is paid for whether the day turns out busy or quiet. of twenty boards, which turns up daily at Rs 120/- a board and costs Rs 2,400/- whether it is used or not. Add Rs 1,900/- of rent and wages and there is Rs 4,300/- a day sitting outside the plan altogether. The rent, the wages and the standing order are not the plan's business, and that is exactly why they stay out of the number the plan is judged on.

The two contribution rates give the second of the three things. The day's contribution is Rs 300/- times the plain crate count plus Rs 450/- times the lined crate count, and the whole exercise is to make that number as large as it will go. One number, built by multiplying and adding, no judgement left in it once the two rates are fixed.

And here is the sentence to keep: once the Rs 4,300/- that does not move has been paid, a day earning Rs 5,100/- of contribution is worth Rs 800/-. Both figures are true, they describe the same day, and they differ by a factor of more than six. Somebody who quotes the first while meaning the second has not made a small error.

What is allowed, and where do those limits come from?

Now the third list, and every entry on it is a plain physical fact about the day rather than a policy or a preference.

Twenty boards arrive each morning. A plain crate takes one board and a lined crate takes two, so the boards used are the plain count plus twice the lined count, and that total cannot pass twenty. Next, the benches. Three benches run eight hours each, giving twenty four, less two hours a day held back for setting up, leaving twenty two bench hoursOne hour of one workbench with somebody standing at it. Two benches busy for one hour spend two bench hours, so the measure counts time and workspace together.. A plain crate takes two of them and a lined crate takes one, so twice the plain count plus the lined count cannot pass twenty two. Third, the lining. Only the lined crate uses cloth, one rollA single length of lining fabric, bought whole and used whole. Half a roll cannot be ordered, so the day's supply arrives as a count rather than as a measurement. each, and eight rolls arrive, so the lined count cannot pass eight.

Then there is a fourth rule that nobody ever writes down and every answer has to obey: neither count can fall below zero. It sounds too obvious to state. The rule is not too obvious to state, and the reason is worth understanding now rather than later. Arithmetic has no idea that a crate is a physical object. Minus three plain crates satisfies the board limit beautifully, frees up six bench hours and would let the workshop report a larger number, and only a human being knows it is nonsense. Every rule that lives in a person's head instead of being written down is a rule the arithmetic is free to break.

What does the whole set of allowed plans look like?

Three things are now on paper. Two decisions, one number to push up, three limits plus the unwritten fourth. The answer will be one of these plans and nothing else, so it is worth looking at what is on the table before anything is solved.

Count only whole cratesFinished crates rather than part-built ones. Whole units keep a plan made of things a customer could take away at the end of the day., since half a crate is not something a customer takes away, and go one row at a time up the lined crate count. With no lined crates at all, the benches allow eleven plain, so the plans run from nothing to eleven: twelve of them. With one lined crate, eleven. With two, eleven again. Then ten, ten, nine, nine, and as the cloth and the boards start biting together, seven and finally five. Eighty four plans satisfy all three limits at once, and the best plan is one of those eighty four.

Draw the same thing without restricting yourself to whole numbers and each limit becomes a line, with everything on one side of it allowed and everything on the other side out. Stack the three lines together with the two zero limits and what survives is a five sided region. Specialists call an allowed plan a feasibleThe word specialists use for allowed. A plan is feasible when it breaks none of the rules, whether or not it is any good, and the shape of the set they form is covered separately. one, and the region in its own right, its shape and what can go wrong with it, is taken up separately later. For now just look at it. Seeing the answer sit on a corner explains more than any amount of description.

How is the best plan found, and where does it sit?

The edges of that region are worth a second look. Contribution climbs steadily in one direction across the picture, and a quantity that climbs steadily across a flat-sided shape reaches its largest value at one of the shape's corners. So the corners are where to look. But which corners, exactly? Not the ones the eye picks off the drawing. A drawing at this scale can be off by half a crate and nobody would see it.

Here is how they are actually obtained. Each limit, held at its maximum, is a boundary lineThe line where a limit is used right up to the last unit. Stand on it and nothing is left; step past it and the limit has been broken.. There are five of them: boards, bench hours, cloth, and the two lines where each crate count sits at zero. Take every pair of those five, work out where the pair crosses, and test that crossing against all the rules. Ten pairs. One of them, the cloth line and the line where the lined count is zero, never crosses at all because the two are parallel. Four of the remaining nine give crossings that break some other rule and are thrown out. Five crossings survive, and they are the region's five corners: nothing and nothing, eleven and nothing, eight and six, four and eight, and nothing and eight.

Now put the contribution rate against each. Nothing and nothing earns Rs 0/-. Eleven plain and no lined earns Rs 3,300/-. Eight plain and six lined earns Rs 5,100/-. Four plain and eight lined earns Rs 4,800/-. No plain and eight lined earns Rs 3,600/-. Eight plain crates and six lined crates wins, and it wins outright by Rs 300/- a day rather than tying with anything. That is a comparison of five computed numbers, not an opinion, and anybody can redo it in a minute.

What does the winning plan use up, and what does it leave?

Take the answer apart. Eight plain and six lined uses eight boards for the plain crates and twelve for the lined, twenty of twenty. The same plan uses sixteen bench hours for the plain crates and six for the lined, twenty two of twenty two. And it uses six rolls of cloth out of eight, leaving two sitting on the shelf at the end of the day.

The two spare rolls are not waste and not an oversight. Slack is information, and it is the most practically useful fact on offer here. A limit that still has something left over at the answer is not the limit holding the answer back. Money spent relaxing it buys nothing at all. Offer the workshop cheaper cloth, faster cloth, a second cloth supplier, twice the cloth: the answer stays at eight and six and the day stays at Rs 5,100/-, because cloth was never what stopped it. Boards and bench hours are what stopped it, and those two are where any improvement has to come from.

The household version of this is familiar to everybody. A person says they would cook more if only they had a better knife, and the truth is that they have forty minutes and a better knife saves two of them. The knife is the cloth. The forty minutes is the bench hours. Almost every improvement effort that fails, fails because somebody relaxed a limit that had slack in it.

What does one whole day look like, written out in full?

Everything above, gathered into one place. The three limits as arithmetic, the objective as arithmetic, the five corners with what each of them consumes, and the answer read straight off the table.

Read the columns as sentences and the whole problem is there. Boards used is the plain count plus twice the lined count, capped at twenty. Hours used is twice the plain count plus the lined count, capped at twenty two. Cloth used is the lined count, capped at eight. Contribution is Rs 300/- times plain plus Rs 450/- times lined, and it is the column being maximised. Row C is the largest entry in that last column, so row C is the answer.

What goes wrong when nobody writes the objective down?

What should be asked before accepting an answer that calls itself the best one?