Constraints: The Limits the Best Answer Must Respect

A constraint is a sentence that sorts every possible plan into allowed and not allowed. A constraint never says which allowed plan is better; ranking the allowed plans is a different job. At the Amaltas workshop three constraints do the sorting, and at the best plan two of them are fully used while the third still has two rolls of cloth left over. Only the fully used ones are holding the answer back.

Two things sit underneath that. The first is the Amaltas workshop itself, an invented workshop that makes two things and nothing else, the plain crate and the lined crate, and runs each day against three limits on what it has to work with. The second is something most people know without ever having been taught it: a line drawn across a chart has two sides, and a sentence that says at most twenty is exactly such a line.

What does a constraint actually do, and what does it refuse to do?

A constraint takes every plan that could conceivably be written down and drops each one into a pile. There are two piles. Allowed, and not allowed. Sorting into those two piles is the entire job, and a constraint does nothing else whatsoever. In particular it holds no view at all about which of the allowed plans is the good one, and expecting it to hold one is the single most expensive misunderstanding in this whole subject.

Take it out of the workshop for a moment. A household decides that the electricity bill has to stay under Rs 2,000/- a month. Run last year through the rule and it sorts twelve months in about four seconds: these eight are acceptable, those four are not. Now turn round and ask the same rule which of the eight acceptable months was the good month. The rule has absolutely nothing to say. The rule was never built to rank the months, and no amount of staring at it will make it answer.

The reason this costs money rather than merely being untidy is that people ask rules to rank all the time without noticing. Somebody who wants the best day at the Amaltas workshop and asks instead for the plan that uses every board has swapped a measure of what is better for a rule about what is allowed, and will get back a plan that is perfectly legal and quietly poor. Ranking plans against each other is a separate thing with a separate name, and that ranking is covered elsewhere.

What are the three forms a constraint can take?

There are three, and those three are all of them. At most, at least, and exactly. Each one draws a line and keeps one side of it, and the only thing that changes from form to form is the shape of the side that is kept.

At most is the form the Amaltas workshop uses for all three of its daily limits: 20 boards arrive each morning, so the rule is at most 20 boards a day. The allowed side is everything on the low side of the line, including the line itself. At least runs the other way. Neither crate count can fall below zero: at least 0 plain crates and at least 0 lined crates. Exactly pins a quantity to a single value. Suppose a buyer places a standing orderA repeating arrangement to supply or take a fixed quantity at fixed intervals, without anybody placing a fresh order each time. for exactly 4 lined crates a day, no more and no fewer. The allowed side is no longer a region at all. The allowed side has collapsed to a single line of plans, every one of them making exactly four lined crates and differing only in how many plain crates go with them.

All three sort in exactly the same way, and only the shape of what survives is different. The exactly form looks like a special animal and is not one, and that is worth holding on to. An exactly rule is two rules wearing one coat: at least four and at most four, both at once. Written as two lines, it behaves like every other pair of lines on the chart.

What are the Amaltas workshop's three limits, written as arithmetic?

The workshop has two decision variablesThe quantities actually being chosen, as against the ones handed over. Here there are two of them and nothing else in the problem is open to being set.: how many plain crates to make today, and how many lined crates. Everything else about the day is handed to it. Call those two counts the two things being chosen, and the three daily limits go down like this.

Boards. Each plain crate uses a single board and each lined one uses two of them, against 20 boards that arrive every morning. So the rule is the plain crates plus twice the lined crates, at most 20. Bench hours. A plain crate occupies a bench for two hours and a lined crate for one, and 22 bench hours exist, being three benches at eight hours apiece minus the two hours each day that go on setting up. So the rule is twice the plain crates plus the lined crates, at most 22. Cloth. Cloth goes into the lined crate alone, a roll per crate, out of 8 rolls delivered daily. So the rule is the lined crates, at most 8, and the plain crate count never appears in it.

The number sitting in front of each crate count is not decoration; it is how much of that thing one crate of that kind eats. That number is the rule's coefficientThe number multiplying a quantity in a written relationship. The coefficient is the rate at which that quantity uses up whatever the line is measuring. for that crate, and reading it as anything else is how the two gets attached to the wrong crate. The plain crate's two sits in the bench hours rule because a plain crate takes two hours. The lined crate's two sits in the boards rule because a lined crate takes two boards. The bench hours two and the boards two are different numbers meaning different things.

Each of those three sentences is a line on the two crate axes, with one side allowed and one side not. Draw all three and the plans that survive all three at once are the ones that are actually available to the workshop. The whole collection of survivors has a name, the feasible setThe usual name for the whole collection of allowed plans taken together. The set itself is covered separately., and what it looks like and how it behaves is covered separately. Each rule contributes one line and one allowed side, and the region gets smaller with every line added and never larger.

Which of the three rules is the best allowed plan pressed against?

The best allowed plan at the Amaltas workshop is 8 plain crates and 6 lined crates a day, worth Rs 5,100/- a day in contributionWhat is left from selling something once the costs that rise and fall with making it have been taken off. Contribution is settled elsewhere and simply used here.. The best plan was settled separately and is taken as given here. Which of the three rules is actually responsible for it has not been settled, and the way to find out is to work each rule at that plan and see what is left over.

Boards: 8 plain crates take 8 boards and 6 lined crates take 12, for 20 against a limit of 20. Nothing left. Bench hours: 8 plain crates take 16 hours and 6 lined crates take 6, for 22 against a limit of 22. Nothing left. Cloth: 6 lined crates take 6 rolls against a limit of 8. Two rolls left, untouched when the benches stop for the night. Boards and bench hours are binding, and cloth has slack of two rolls.

Binding and slack are the two words to carry forward, and both repay a slow reading. A binding rule is one the answer is pressed hard against, with nothing to spare. A slack rule is one the answer never came near. The difference is plain in a household without any arithmetic: a household that spends right up to its rent every single month and never once gets close to the limit on its phone data has one binding rule and one slack one, and it knows perfectly well which is which without being told. Rent decides what the month looks like. The data limit decides nothing.

What happens when the rule that does not bind is taken away?

Delete the cloth rule from the list entirely. Not raise it, not relax it, take it out. The workshop is now allowed to make as many lined crates as the other two rules permit, with no ceiling of eight anywhere. Solve it again from scratch and the best allowed plan is 8 plain crates and 6 lined crates, worth Rs 5,100/- a day. The answer has not moved by one crate or one rupee.

The unchanged answer is not a coincidence and not a quirk of these particular numbers: the answer was never touching the cloth rule, so the cloth rule was never doing anything to the answer. Look at what actually changed. The region did change shape. The flat top edge at eight rolls disappeared and a new corner opened up at 10 lined crates and no plain ones. Plans that were forbidden are now allowed. But every one of the newly allowed plans is worse than the one that was already winning, and the winner itself sat well inside the old ceiling, so nothing that mattered moved.

What happens when the rule that does bind is taken away?

Now the same treatment for bench hours. The rule is deleted, boards and cloth are left alone, and the problem is solved again. The answer jumps to 20 plain crates and no lined crates at all, worth Rs 6,000/- a day. The new answer is a different plan, a different mix, and Rs 900/- a day more than the answer the workshop started with. One rule out of three, and the whole shape of the day changed.

Then look at what that plan asks for. Twenty plain crates at two bench hours each need 40 bench hours. The Amaltas workshop has 22, and 18 of the hours that plan depends on do not exist. So there are two lessons here and the second one is the one that catches people: a binding rule is doing all the work, and a rule taken out of the arithmetic has not been taken out of the workshop.

That second lesson is worth saying without any workshop in it. A modelA written down version of a situation, made only of numbers and rules, small enough for a machine to work on. A model is never the situation itself. is a written down version of a situation, and it is never the situation. Delete a line from it and the line stops constraining the arithmetic; the benches, the hours and the people are all exactly where they were. The Rs 6,000/- is a perfectly correct answer to a question about a workshop that has nearly twice the bench time this one has. The Rs 6,000/- is not an opportunity and not a target. The figure belongs to somebody else's workshop.

Can a rule be written down and do nothing at all?

A rule can be written down and do nothing at all, and telling that kind apart from a slack rule is worth more than it sounds. Add a fourth rule to the Amaltas workshop: no more than 15 plain crates a day. Solve again. The answer is 8 plain crates and 6 lined crates, Rs 5,100/- a day, exactly as before. Nothing moved.

The reason is that the region never gets anywhere near 15 plain crates. A plain crate takes two bench hours and only 22 hours exist, so 11 plain crates is the most the workshop can make in a day even if it makes nothing else at all. Every allowed plan has 11 plain crates or fewer. A ceiling at 15 is four whole crates clear of the furthest the region ever reaches, in every direction, under every combination of the other rules.

So here is the distinction that matters: a slack rule could bind if the answer moved, and a rule sitting outside the region entirely could not bind under any circumstances. Both are quiet, and only one of them is harmless. Watch the cloth rule prove it. Suppose the board supply rose to 23 a day. The best allowed plan becomes 7 plain crates and 8 lined crates, worth Rs 5,700/- a day, and every one of the eight rolls of cloth is now used. The rule that had two rolls spare has become binding, without anybody touching it. The cap at 15 plain crates, meanwhile, would still be doing precisely nothing. One was live and waiting. The other is furniture.

Which rules did nobody at the Amaltas workshop write down?

Two of them, and both are the kind of thing that would earn a strange look if said out loud in the workshop. Neither crate count can fall below zero. And crates come in whole numbers. Nobody writes those down because nobody in the building could imagine needing to.

Now test the written list, the three rules exactly as typed, on two plans. First, minus 5 plain crates and minus 3 lined crates. Boards: that comes to minus 11 against a limit of 20, comfortably inside. Bench hours: minus 13 against 22, inside. Cloth: minus 3 against 8, inside. Second, eight and a half plain crates with 5 lined crates. Boards: 18 and a half against 20, inside. Bench hours: exactly 22, right on the line and therefore allowed. Cloth: 5 against 8, inside. Every written rule calls both of those plans allowed, and neither of them is a plan any workshop on earth could carry out.

Hand that list to a solverA program that is handed a written list of rules and a measure of what is better, and hands back the plan that scores best. How one works is covered separately. and it will sort exactly as it was told to. Nothing in it knows that a crate is a thing that can be picked up. Pure luck saves the Amaltas workshop today. The best allowed plan happens to come out at 8 and 6, both whole and both above zero, so neither missing rule changes the answer. A missing rule that does not move today's answer leaves nothing on the report to show that the list is wrong, and that is what makes the two unwritten rules dangerous rather than reassuring. The rules a person finds too obvious to say are exactly the rules that get left out, and they surface in what the list allows long before they surface in what the answer says.

What do the three limits and the three experiments look like on one table?

Everything above sits on one four column table, and the whole of it is worth seeing at once. The columns are the rule, the arithmetic it becomes, what the best allowed plan of 8 plain crates and 6 lined crates uses, and what is left over.

Now run the three experiments off that same table, changing one thing at a time and solving the whole problem again from scratch each time rather than adjusting the old answer.

Three experiments and one of them moved anything. The one that moved the answer is the one with nothing left over in the fourth column of the first table, and it could have been picked out before any of them were run. That is the practical value of the word binding: it says in advance which rules are worth arguing about.

How to read somebody else's constraint list

Constraint lists arrive written by other people far more often than anybody writes one themselves, and they arrive without commentary. Five questions carry a reader through a row, and they are the same five every time. What is this rule measuring? In what units? Is it an at most, an at least or an exactly? Is it a physical fact, a promise made to somebody, or a preference that somebody once expressed? And does it bind at the answer?

The fourth question, the kind, is the one people skip and it is the one that says what can actually be changed. A physical fact needs money or time to move. A promise made to a buyer needs a conversation with that buyer. A preference needs somebody to admit out loud that it was a preference. Preferences came in as rules and nobody has questioned them since, so most of the surprising slack in a real list turns out to be hiding there.

Two patterns are worth reacting to: a list where nothing binds is a list that is not doing anything, and a list where everything binds is usually a list with a mistake in it. If nothing binds, either the limits were written far more generously than the situation deserves, or the answer is not where it is thought to be and something outside the list is holding it. A list where every single rule binds exactly, with nothing to spare anywhere, deserves suspicion: real limits rarely all run out at the same instant, and a list like that often turns out to have been written backwards from an answer somebody already had. Two rules binding out of three is an ordinary and healthy pattern, and two out of three is what the Amaltas workshop shows.