Constraint Violation: When the Solution Breaks a Rule

A constraint violation is a plan that sits outside the allowed set on at least one rule. The kind a solver hands back beats every allowed plan on the objective, and it beats them for one reason: it is spending something the workshop has not got. At the Amaltas workshop a plan two boards over reports Rs 5,400/- a day and delivers Rs 4,800/-.

Underneath that answer sits one uncomfortable fact about arithmetic. A rule removes plans from consideration, and every plan it removes is a plan that scored something. Push one rule slightly out of the way and candidates get added while none are taken away, so the score that can be reached goes up, never down. So a plan that breaks a limit is not an odd exception that happens to look good. A rule breaking plan looks good by construction, and the better it looks, the more of the limit it has quietly borrowed. The Amaltas workshop is an invented joinery shop that makes two things, the plain crate and the lined crate, and its best allowed plan is eight plain crates and six lined crates a day, worth Rs 5,100/- of contributionWhat one unit adds to the day once the spending that rises with it is taken off. Contribution is not profit. The spending that stays flat is still waiting to be paid.. Everything below is measured against that figure.

What is a constraint violation, and what is it not?

First, what it is. A violation is a measurement of distance: the plan on one side, the rule on the other, and the gap between them worked out. At the Amaltas workshop, a plan calling for twenty two boardsA flat length of sawn timber. A board is the raw material a crate side gets cut from, and the workshop counts boards one by one as they arrive at the door. against the twenty that arrive is over by two boards. The violation is two boards. A constraint violation is a number, not a verdict, and the number comes first.

Now what it is not. A violation is not the sentence "this plan is unacceptable", and it is not the sentence "it is only two boards, the workshop will manage". Both of those are decisions, and both of them arrive far too early. Consider what happens when somebody skips straight to one. Call the plan unacceptable and nobody bothers working out how far over it went. The answer no longer changes anything. The moment it is called fine, nobody works it out either, for exactly the same reason. Either judgement, arrived at first, destroys the measurement that should have come before it. So many teams cannot say how far over their last accepted plan actually was. The figure was never needed, so it was never taken.

Here is the everyday version. A lift carries eight people and nine get in. Somebody who says at once that nine is dangerous and somebody who says at once that nine is obviously fine have both stopped thinking about the same thing. The lift is over by one person, or 12.50 per cent over its stated load. Any sensible conversation runs on that one figure, and both of them threw it away before the doors closed.

How is the distance over a limit measured?

Two figures, and both are wanted every time. The first is the breach in the rule's own units: two boards. The second is the breach as a share of the limit: two divided by twenty, or 10.00 per cent. The two figures answer different questions, so neither replaces the other. A planner needs both answers. The units figure shows whether the breach can be fixed, and the share figure shows whether it is a real breach or a nudge from roundingCutting a number back to fewer figures. Rounding nudges the value slightly, so a very small difference between two numbers can be nothing more than the nudge..

The units figure comes first. Boards are objects that either exist in the yard or do not, so two boards is something a person can act on. Somebody can go and look. A breach reported only as a percentage does not travel that way: 10.00 per cent over says nothing about whether the shortfall is two boards, two hundred boards or two lorries, and nobody can walk into the yard and look for 10.00 per cent of anything.

Then the share. Its job is to catch the breaches that are not really breaches. A plan reading twenty point zero zero zero zero zero one boards is over by one millionth of a board. As a share of the limit the breach is 0.000005 per cent. Nobody is short of timber. One millionth of a board is a number that fell out of the arithmetic. The share figure makes the arithmetic obvious at a glance, where the units figure alone would still read as a breach. The same test on the Amaltas case returns 10.00 per cent. No arithmetic slip produces a gap that size. So the two figures together sort the artefacts from the real ones, and either one on its own leaves the question open.

What does the Amaltas workshop's rule breaking plan look like?

The plan is six plain crates and eight lined crates. Score it against the three daily rules one at a time, and do not stop at the first one that fails. Which rules hold is as much of the story as which one breaks. Boards: one board goes into a plain crate and two into a lined one, so six plus sixteen is twenty two, against the twenty that arrive. Over by two. Bench hoursOne hour of one work bench with somebody standing at it. Three benches at eight hours apiece come to twenty four before anything is held back for setting up.: two hours go into a plain crate and one into a lined one, so twelve plus eight is twenty, against twenty two available. Inside, with two hours of slackThe part of a limit nobody used. Two rolls of cloth still sitting on the shelf at closing time is two rolls of slack.. ClothA single roll of lining fabric. Only the lined crate uses any, and it uses exactly one, so eight lined crates need eight rolls.: only the lined crate uses any, one roll each, so eight rolls against the eight that arrive. Exactly at the line.

Exactly one rule breaks and two hold, and that is the only reason the harm here can be traced to a single thing. A rule breaking plan of this kind is unusual rather than typical, and the reason is worth knowing. At the best allowed plan both the boards and the bench hours are used to the last unit, so almost any move that raises the day's contribution pushes on both at once. Sweep every plan made of whole cratesA crate is either built or it is not. Half a crate cannot be sold, so the counts here never carry a fraction. that beats Rs 5,100/- while going over by no more than two units in total and precisely two of them appear: seven plain with seven lined, over by one board and worth Rs 5,250/-, and six plain with eight lined, over by two boards and worth Rs 5,400/-. Widen the allowance to five units in total and ten plans qualify, six of which break two rules at once. A plan breaking two rules cannot show where the damage came from, so the case worked through here is the best of the clean pair.

Notice the cloth line especially. Eight rolls used against eight rolls delivered is not a breach. At the limit is inside the limit, and a rule that says at most eight is satisfied by exactly eight. A plan sitting flush against three limits at once feels like it must be cheating somewhere, and feeling is not measurement.

Why does the rule breaking plan look better?

Because it is worth more, on paper, than anything the workshop is allowed to do. Six plain crates at Rs 300/- is Rs 1,800/-, eight lined crates at Rs 450/- is Rs 3,600/-, and the plan reports Rs 5,400/- for the day against the Rs 5,100/- of the best allowed plan. The gap is Rs 300/-, or 5.88 per cent better. Anybody comparing the two lines in a report picks the bigger one, and they are not being careless. Rs 5,400/- really is the bigger number.

So where did the Rs 300/- come from? Trace it as a swap. A swap is exactly what it is. Start at eight plain and six lined and walk to six plain and eight lined: two plain crates are given up and two lined crates are taken on. Giving up two plain crates costs Rs 600/- of contribution. Taking on two lined crates brings in Rs 900/-. The difference is the Rs 300/-. Now look at the swap's effect on the day's materials. Two plain crates released two boards and four bench hours; two lined crates want four boards and two bench hours. Net, the swap hands back two bench hours the workshop had and asks for two boards the workshop has not got. The improvement is the value of the thing the plan is pretending to have.

The borrowing is the whole engine, and it works the same way everywhere. A household budget that balances only because next month's salary was counted twice balances beautifully. A delivery schedule that fits only because the van is assumed to be in two places at four in the afternoon fits. Nothing has been invented in the arithmetic; a resource has simply been counted that was never delivered, and every rupee of the improvement traces back to it. Where a plan looks better than the best allowed one and the borrowing is not yet visible, something was borrowed all the same. The search is not finished.

What does that plan actually deliver at the end of the day?

Now the day itself. The report never shows the day itself. Twenty boards arrive, not twenty two. A lined crate is worth Rs 450/- against a plain crate's Rs 300/-, so the lined crates get made first. No sensible workshop starts with the cheaper item. Eight lined crates take sixteen boards. Four boards are left. Four boards make four plain crates, not the six the plan asked for. The day closes at four plain crates and eight lined: Rs 1,200/- plus Rs 3,600/-, or Rs 4,800/-.

Now set the three figures beside each other. The plan reported Rs 5,400/-. The best allowed plan was worth Rs 5,100/-. The day delivered Rs 4,800/-. Promised 5.88 per cent better and delivered 5.88 per cent worse, a swing of Rs 600/- a day between the report and the day. And the workshop did not merely fail to gain the Rs 300/-. The workshop spent its cloth and its boards in the wrong order for a plan that could not be completed. The day ended Rs 300/- below where the allowed plan would have left it.

The matching 5.88 per cent on both sides is arithmetic and nothing more, and it is worth naming so that no pattern gets read into it. Both gaps happen to be Rs 300/-, and both are measured against the same Rs 5,100/-. Rs 5,100/- divided by seventeen is exactly Rs 300/-, so any Rs 300/- gap against that base comes out at one seventeenth, or 5.88 per cent. One fraction appears twice, and no law makes a loss mirror the gain that caused it. Under a different plan the two shares stop matching immediately.

What does one broken rule look like written out in full?

The whole case sits in one table below. The top half scores the plan against the three daily rules. The bottom half sets the three money figures against each other. The bottom half only makes sense once a single rule can be seen carrying all of it, so the top half comes first.

And the trace between the two halves, in one line: the eight lined crates take sixteen boards, four boards are left, and four plain crates get made instead of six. One broken rule, and the whole story comes off it.

Why does a solver hand back a plan that breaks a rule?

Two ordinary reasons, and it is worth being clear that neither of them is the software going wrong. The first is tolerance. A solver works in decimals and its arithmetic carries tiny errors, so it is built to accept a plan that misses a rule by a hair rather than throw away a perfectly good answer over the last decimal place. A plan reading twenty point zero zero zero zero zero one boards is over by one millionth of a board, or 0.000005 per cent of the limit. No solver worth using rejects a miss that small. The answer comes back marked as allowed, and strictly speaking it is not.

The second is a rule that was typed wrong. Somebody enters at most twenty two boards where the yard delivers twenty, or enters the limit in the wrong units, or writes the rule the wrong way round. From the solver's side there is no violation at all: the plan fits the rule it was given, perfectly, and the software has nothing to complain about. The breach exists only between the typed rule and the world, a place no solver can see. Neither reason is a fault in the software, and both put the same artefact on the planner's desk: a confident answer whose plan the workshop cannot run.

The practical consequence is worth holding on to. Because neither cause produces an error message, the check cannot live inside the solver. The check has to live with whoever reads the answer. Somebody has to score the returned plan against the limits as they actually are, by hand, at least once. Scoring three rules by hand is a two minute job, and it is the only thing standing between the report and the day.

Does it matter which kind of rule was broken?

The kind of rule broken decides what may be done next, and nothing else matters more. A list of constraints almost never says which kind each rule is. Three kinds turn up, and they look identical written down.

The first is a physical fact. Twenty boards arrive and there is no twenty first. A plan needing twenty two does not get argued with; it simply stops partway through the afternoon, exactly as it did above. The second is a promise. The workshop agreed to hand a customer four crates by Friday, and the boundary lineThe line a rule draws across the plan. Plans on one side of it are allowed and plans on the other side are not, so the line is where a rule becomes a picture. that draws is every bit as real, but breaking it costs a relationship and possibly a penalty rather than stopping the saw. The third is a preference somebody wrote down as a rule: never more than eight lined crates a day. The person who set it up disliked how the cloth cutter behaved on long runs. The preference sits in the list looking exactly like the other two.

Only the third kind is worth arguing with, and a constraint list almost never says which kind each rule is. That is the whole practical content of this block. When a violation lands on the planner's desk, the first question is not how big it is but which kind of limit it crossed, and answering it usually means asking the person who wrote the rule rather than reading the model. A breach of the first kind means change the plan. A breach of the second means someone has to make a call about a relationship, and it belongs to them, not to the solver. A breach of the third means the rule itself is a candidate for revision, and revising it is a legitimate answer rather than cheating.

What is to be done when somebody hands one over?