A variable restricted to 0 or 1 is a yes-or-no decision, and the connectives of logic become linear inequalities on such variables. The point of the lesson is not the list of encodings but the check: an inequality is compared with the condition on every assignment, and a wrong encoding is refuted by a row rather than argued about.
Core ideas
The encodings are a short list and they are not the hard part. The hard part is that an encoding is a claim about every assignment, and claims like that are settled by evidence rather than by plausibility.
y_A = 1 means “project A is chosen” and y_A = 0 means it is not. There is no y_A = 0.6, and the first thing to write next to any binary is the sentence it stands for. Half of all wrong encodings are wrong because the author never fixed which way round 1 meant.
“If A then B” is y_A − y_B ≤ 0, which reads: A may not be chosen unless B is. Swap the two letters and you have the converse, which permits A without B — the one case the condition forbids. The inequality is short enough that nothing in its appearance tells you which of the two you have written.
There are 2ⁿ assignments and the encoding must agree with the condition on every one of them. With three binaries that is eight rows, which can be read in a few seconds, and the converse of “if A then B” disagrees on four of them. A reader who has seen the row y_A = 1, y_B = 0 does not write the converse again.
The material
The five conditions almost every practical model is built from, and the eight-row check that certifies each one.
A binary variable is a variable restricted to the set {0, 1}. It carries a decision: 1 for the thing happening and 0 for it not happening. A model with binaries and nothing else is a binary or 0/1 programme; a model with binaries and continuous variables together is a mixed integer programme.
A linear inequality on binaries encodes a condition when, for every assignment of 0 and 1 to the variables, the inequality holds exactly when the condition holds. One assignment on which the two disagree refutes the encoding, and one is all it takes.
That definition is why the lab evaluates your inequality on every assignment beside the truth table of the condition. Discrete Mathematics builds those tables in “Logical Connectives” and “Truth Tables”, and the check here is the same object with one extra column: what the inequality evaluates to, and whether it holds.
The condition forbids one combination and permits the other three: y_A = 1, y_B = 0 is out, and (0,0), (0,1), (1,1) are in. The inequality y_A − y_B ≤ 0 agrees on all eight assignments of three binaries. The converse y_B − y_A ≤ 0 disagrees on four of them, and the first the lab reports is y_A y_B y_C = 1 0 1: the condition fails there and the inequality holds, so the converse permits exactly the case the condition was written to forbid.
The ≤ 1 against = 1 pair is worth one more sentence, because the two conditions differ on a single assignment and it is the empty one. “At most one” permits choosing nothing; “exactly one” does not. The lab refutes y_A + y_B + y_C ≤ 1 as an encoding of “exactly one” on the row 0 0 0, and on that row alone.
The condition “both A and B” describes one assignment, and the expression y_A · y_B is not linear, so it has no place in a linear model at all. Nothing is lost: y_A + y_B ≥ 2 holds on 1 1 and fails on the other three combinations, which is exactly the condition. y_A + y_B ≥ 1 is the encoding readers reach for instead, and it is refuted on four rows — the first being 1 0 1, where one project is chosen and the inequality is satisfied.
Checking costs 2ⁿ rows, so it is affordable for a handful of binaries and not for fifty. That is not a limitation of the method: the encodings being checked are local — two or three variables at a time — and a model with fifty binaries is built from rows that each involve a few. Verify the row, then use it.
The habit generalises past the point where a truth table fits. In the two lessons after next, the condition is about continuous quantities and the check is a pair of re-solves rather than eight rows, but the discipline is identical: fix the binary at each value, look at what the model then says, and confirm it is what you meant.
Interactive
An encoding is checked on every assignment, and a wrong one is refuted by a row
Method
The first two steps are prose and the last two are evidence. Skipping either pair is how a wrong row ships.
In a sentence, on the page. “y_A = 1 when the extension is built.” An encoding cannot be checked against a condition until both are written down in the same words.
“We may not build the extension unless the yard is resurfaced.” Which combinations are forbidden is now readable, and it is the only thing the inequality has to reproduce.
Usually a sum of the binaries against a constant. Write the relation and the right-hand side deliberately: ≥ 1, ≤ 1 and = 1 are three different conditions, and ≤ 2 differs from ≤ 3 on exactly one assignment.
Two columns, 2ⁿ rows, and a third column saying whether they agree. This is the step that turns an opinion into a fact, and it is the whole reason the lab exists.
When an encoding fails, write down the assignment that killed it next to the encoding that survived. y_A = 1, y_B = 0 is worth more than the rule it corrects, because it is what you will remember.
A capital budget with four candidate projects. Each condition is stated, encoded, and then checked on the assignments its variables range over.
Condition 4 is the reason the converse must be recognised rather than merely avoided. y_B − y_A ≤ 0 is a perfectly good inequality; it encodes “if B then A”. Writing both directions encodes equivalence, and that is sometimes the condition. What is never right is writing one and believing it says the other.
Condition 2 shows how thin the margin can be. ≤ 2 and ≤ 3 differ on one assignment out of eight, and with ≤ 3 the row is satisfied by every assignment there is — a constraint that constrains nothing, which is a harder defect to notice than an infeasible model.
For a faded rehearsal, encode “if either depot is funded then the access road is” and check it. The supplied first move is that this is two implications rather than one, so it is y₃ − y₂ ≤ 0 together with y₄ − y₂ ≤ 0. Decide before opening the quiz whether the single row y₃ + y₄ − 2y₂ ≤ 0 encodes the same condition, and name the assignment that settles it.
You should be able to translate if-then, at-least-one, at-most-k, exactly-one and both into inequalities on binaries, verify each on every assignment of its variables, and name the row that would refute the encoding a reader reaches for instead — y_A = 1, y_B = 0 for the converse, and 0 0 0 for “at most one” standing in for “exactly one”.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.