The Feasible Set: Every Answer That Is Actually Allowed

The feasible set is every plan that satisfies every rule at once, and nothing else. The set does no ranking, so it holds the worst allowed plan exactly as firmly as the best one. With two decisions it is a region that can be drawn. The Amaltas workshop's region has five corners, an area of 69, and 84 plans made of whole crates inside it.

Three things are already settled. The Amaltas workshop makes two things and nothing else, the plain crate and the lined crate, and its three daily limits of 20 boards, 22 bench hours and 8 rolls of cloth are set out under the constraints themselves. Each rule taken on its own is set out there too. The five corners of the region below have already been found by crossing boundary lines two at a time, and the best of them already compared against the rest. The collection of allowed plans can be treated instead as a single object: a shape to look at, to measure, and then to break in the two ways it can break.

What is the feasible set, in plain words?

The feasible set is every plan that clears every rule at once, and the two words carrying the whole idea are at once. Not most of the rules. Not the important ones. Every rule, simultaneously, by the same single plan. A plan that clears two of the three daily limits at the Amaltas workshop and fails the third is not partly in the set and not nearly in it. The plan is out, and out just as completely as one that fails all three.

Ordinary life runs the same test without giving it a name. A household hunting for a flat to rent has a rule about the rent it can carry, a rule about how far the commute can stretch, and a rule about which floor is liveable with a grandparent in the house. The flats worth going to see are the ones that clear all three. A beautiful flat at the right rent on the fourth floor of a walk up is not a near miss for that household; it is simply not one of the flats they are choosing between. Nobody says the flat is 67 per cent allowed. The flat is off the shortlist, and the shortlist is the feasible set.

Notice the two things a shortlist refuses to do: it does not say the shortlisted flats are equally good, and it does not say which one to take. The shortlist says only that each flat on it clears the rules. The distinction looks small when the rules are about rent and stairs. The distinction becomes the whole subject when the rules are three daily limits and 84 plans sit on the shortlist. The Amaltas workshop stands exactly there.

Why can a problem with two decisions be drawn at all?

A plan at the Amaltas workshop is exactly two numbers, so a plan is a point on a sheet of paper. How many plain crates, and how many lined crates. Nothing else about the day is a decision. Put plain crates along the bottom and lined crates up the side, and every possible plan, allowed or not, is somewhere on that sheet of paper. Eight plain crates and six lined crates is one dot. Twenty plain crates and nothing lined is another dot, further right and sitting on the bottom edge.

Now the rules. Boards run out at twenty a day, and each plain crate swallows one board while each lined crate swallows two. The plans that use exactly twenty boards are the ones where the plain count plus twice the lined count comes to twenty, and marking all of them gives a straight line running from twenty plain and no lined up to no plain and ten lined. Everything on one side of that line uses twenty boards or fewer and is permitted by the board rule. Everything on the other side needs boards that never arrive. One rule is one line, and one side of that line is the allowed side. The same holds for the bench hours rule and the cloth rule. The two quiet rules that neither crate count can drop below zero are simply the two axes.

Laid down together on the same axes, the feasible set is what all the allowed sides have in common. The word set is worth keeping even though the picture looks like a shape: what is being drawn is an intersectionEverything that belongs to several collections at the same time. The plans belonging to all five allowed sides at once, and nothing that belongs to only four of them., five allowed sides overlapping, and the shape is only what that overlap happens to look like.

The picture is a luxury of having exactly two decisions, and it is worth being honest about how quickly that luxury runs out. A workshop making three things has a set that is a solid in three dimensions, awkward but still imaginable. A workshop making forty things has a set living in forty dimensions, and no one has ever looked at one. The set is still there. The set still has corners, still has an inside and an outside, and a solver still walks around it exactly as it walks around this one. At forty dimensions nobody can check the answer by pointing at the paper, and nothing else changes. Learning the arithmetic on a problem small enough to draw is therefore not a toy exercise. The same arithmetic runs where drawing is impossible.

What does the Amaltas workshop's allowed region look like?

The region is five cornered, and its five corners are no crates at all, 11 plain and 0 lined, 8 plain and 6 lined, 4 plain and 8 lined, and 0 plain and 8 lined. Those five were not read off a drawing. The five corners were found by taking the five boundary lines two at a time, solving each pair for the single point at which those two lines cross, and then putting that point back through all three daily limits to see whether it survived. Most crossings did not. The drawing exists so that the survivors can be checked, not because anybody found them by looking.

Walk the edges once, anticlockwise from the origin. From no crates at all, the bottom edge runs right along the axis to 11 plain crates and no lined, and it stops there because 11 plain crates take 22 bench hours and there are exactly 22. From there the bench hours edge climbs left and up to 8 plain and 6 lined, every plan along it using every available hour. At 8 plain and 6 lined the board supply runs out as well, and the boards edge takes over, running up and left to 4 plain and 8 lined. There the cloth runs out, and the cloth edge runs flat left to 0 plain and 8 lined. Then the left edge drops back down the lined crate axis to the origin. Five corners, five edges, and each edge is a rule being obeyed exactly rather than comfortably.

The region covers an area of 69 measured on the two crate axes, so one unit of that area is one plain crate wide by one lined crate tall. The number is not something the Amaltas workshop can spend, and nobody makes 69 of anything. The area is a measure of how much room the rules leave, and it earns its place once one rule starts moving and a single figure is wanted that says whether the room is growing or shrinking.

How many plans does the region actually hold?

The drawn region holds infinitely many points and the Amaltas workshop can choose among exactly 84 of them, and both statements are true at the same time. The region is drawn as a solid patch because that is what the arithmetic of the rules describes: 7.31 plain crates and 4.06 lined crates satisfies every limit perfectly well as a piece of algebra. Half a crate cannot be loaded onto a lorry, so 7.31 plain crates is not a plan. Once the counts have to be a whole crateA crate that is finished and can be loaded. Half a crate is a stack of boards, so a day's plan is always counted in whole numbers., the only plans that survive are the ones sitting on the grid of whole numbers inside the region.

Count them one lined crate row at a time. Row by row is the only way to be sure. With no lined crates at all, the bench hours run out at 11 plain crates, so the plans run from 0 through 11 and that is 12 of them. With one lined crate, the hours allow 10 plain, so 11 plans. With two lined crates the boards allow 16 plain but the hours still allow only 10, so 11 again. Then 10, 10, 9, 9, and at seven lined crates the boards finally bite harder than the hours and leave 7 plans, and at eight lined crates just 5. Twelve, eleven, eleven, ten, ten, nine, nine, seven and five. The nine numbers sum to 84, and 84 is a count rather than an estimate.

The same region, measured four ways

One region, and four different questions that can be put to it. None of the four asks which plan is best.

Does the region know which plan is better?

The region does not know, and that is the single most useful thing to hold on to about a feasible set: it is a container with no opinion. The plan of 8 plain crates and 6 lined sits inside it. So does the plan of no crates at all, a day in which the Amaltas workshop opens, makes nothing and closes. Both clear every rule. The region holds the two of them with exactly the same grip, and drawn without labels it would offer no way whatever of telling them apart.

Put figures on the two and the gap is not subtle. Eight plain crates and six lined bring in Rs 5,100/- of contribution in a day. No crates at all bring in Rs 0/-. Every rupee of that difference arrives from outside the region, from the objectiveThe one quantity a problem is built to drive to its highest value, or its lowest. Choosing the right quantity for that job is covered separately., the separate statement of what counts as better. Delete that statement and the region does not change by a hair. The region still has five corners, still covers 69, still holds 84 buildable plans, and now answers nothing at all.

The everyday version is a shortlist somebody else drew up. A relative sends over eleven wedding halls that all fit the date, the budget and the guest count. The shortlist is genuinely useful and it has done real work: hundreds of halls are not on it. But the shortlist has no view on which hall to book, and reading it as though it did is how households end up taking the first entry. A set drawn beautifully still answers no question on its own, and the beauty of the drawing is not evidence that it does.

What happens to the region when one rule moves?

Move one limit and the region does not simply swell or shrink, it changes how many corners it has, and the count jumps rather than sliding. Hold the boards at 20 and the bench hours at 22, and move only the cloth. Start at no cloth at all. With no cloth there are no lined crates, so every allowed plan lies flat along the plain crate axis between no crates and 11 plain crates. The allowed plans no longer form a region at all: they form a line segment with two ends, an area of 0, and 12 plans made of whole crates on it.

Now let the cloth come in. From one roll of clothLining cloth arrives in rolls, and one roll lines exactly one crate. The plain crate uses none, so this limit only ever speaks about lined crates. up to six, the region is four cornered: the origin, 11 plain crates, a corner where the bench hours edge meets the cloth line, and a corner on the lined crate axis. From seven rolls to nine the cloth line has risen high enough for the boards edge to appear between the bench hours edge and the cloth edge, so the region is five cornered. From ten rolls onward the cloth line has climbed clear of everything else and touches nothing, so the region is four cornered again and stays that way forever.

The odd moment is at exactly six rolls, where the count reads four and not five, and the picture is the reason. At six rolls the cloth line passes through the point 8 plain and 6 lined. So does the board line, because 8 plus twice 6 is 20. So does the bench hours line, because twice 8 plus 6 is 22. Three boundary lines through one point, and the two corners that are separate at seven rolls have landed on top of each other. The visible shape now has four corners. A description smooths this case away and a recomputation catches it, so the three sums are worth checking by hand.

What does it mean when nothing at all is allowed?

A buyerSomebody placing an order with the workshop, at a quantity of its choosing. comes to the Amaltas workshop and asks for at least ten lined crates a day, every day. Written into the modelThe written version of a problem: the quantity being driven up, and every rule the answer must respect. Anything left out of it might as well not be there. that is a fourth rule, and it looks no stranger than the other three. Run the arithmetic and there is no answer. Not a poor answer, not a warning, nothing.

The reason has nothing to do with the arithmetic: ten lined crates need ten rolls of cloth and eight arrive, so no plan on earth satisfies every rule at once. Look at what makes this trap so quiet. Ten lined crates and no plain ones take twenty boards and twenty arrive, so the boards would cope perfectly well. The same plan takes ten hours out of twenty two, so the bench hours would cope easily. Two of the four rules are entirely comfortable with the buyer's order. Only the cloth is short, and it is short by two rolls. One short rule is enough. The set is empty, and an empty set has no best member for the same reason an empty room has no tallest person in it.

Everyday version: a household wants a flat with three bedrooms, under a fifteen minute walk from the station, at a rent it can genuinely carry. Every one of the three is reasonable. In some neighbourhoods no such flat exists, and no amount of searching harder produces one. The correct response is not more searching. The response is to work out which of the three rules has to give, and that is a conversation rather than a calculation.

What does it mean when nothing closes the region?

The opposite failure produces exactly the same silence, and it is caused by a slip so ordinary that most people who write models have made it. Type all three daily limits the wrong way round, at least rather than at most. One careless replacement across a file will do it. Now the board rule says use twenty boards or more. The bench hours rule says spend twenty two hours or more. The cloth rule says use eight rolls or more. Nothing anywhere says stop.

The region that results has an inner edge and no outer one. The region starts around 7 plain crates and 8 lined and runs up and to the right without end. For any plan named there is a bigger one that also clears every rule, so a request for the plan with the largest contribution has no answer: a thousand plain crates and a thousand lined clears all three reversed rules comfortably, and so does ten thousand of each. There is no best plan for the same reason there is no largest whole number.

Hold the two failures side by side. The two are opposites that look identical from the outside. The empty set has nothing in it. The open one has too much. Both leave a blank result, and the message the software prints is usually the only clue as to which of the two it is. The software never settles it. Reading the rules settles it, by asking two questions of them: is there any plan at all that clears every one of these, and is there anything at all that stops the plan growing.

Which three questions come before the best answer?

Anyone who works with a model built by somebody else, whether that is a planner at a workshop, an analyst checking a schedule or a lender reading a covenant packThe bundle of promises a borrower signs up to alongside a loan, such as keeping a ratio above a stated level. Lending agreements are covered separately., gets more out of three questions about the allowed region than out of any amount of staring at the answer. None of the three mentions the quantity the model is trying to make as large as possible, and that is deliberate.

First: is there anything in the region at all? Taking the tightest looking rule and the rule it fights with, and checking by hand that at least one plan clears both, is thirty seconds of arithmetic, and it is what stands between an analyst and the wasted week described below.

Second: is the region closed in the direction the answer wants to go? Every rule that pushes upward has to be met by something pushing down. If the quantity being maximised grows with lined crates, then something has to cap lined crates, and that cap has to be nameable. If it cannot be named, the model has no outer edge in that direction and the answer will be nonsense or absent.

Third: how much of the region is actually reachable? The Amaltas workshop's region holds 84 buildable plans and infinitely many drawn points, and the two need not agree. At some cloth settings the best corner of the drawn region is not a whole crate plan at all: at five rolls it sits at eight and a half plain crates and five lined, worth Rs 4,800/-. The best plan anyone can actually build is eight plain and five lined at Rs 4,650/-. A gap of Rs 150/- a day, appearing purely because a crate cannot be halved. A region that fails any of the three makes the best plan an irrelevant question, whatever the answer would have been.