“Constraint A or constraint B” cannot be written by writing both, because writing both is the conjunction — and on a sequencing pair the conjunction is infeasible. It is written by relaxing each row with a big-M term that a single binary switches off, so that one value of the binary enforces A and makes B vacuous and the other value does the reverse.
Core ideas
One hard idea: “or” is not something you can write by writing more constraints, because constraints accumulate as “and”.
Constraints in a model are simultaneous. Adding a row never creates a choice; it removes plans. So writing A and writing B asks for both, and on two jobs competing for one machine that asks job one to finish before job two starts and job two to finish before job one starts. Add the two rows and you get 0 ≤ −7.
Relax A by M_A(1 − y) and B by M_B y. At y = 1 the first term vanishes and A binds, while B has M_B added to its right-hand side and nothing in the region can break it. At y = 0 the roles swap. The binary is not a variable in the problem; it is the choice the problem contains.
The relaxation may set y = 3/13. Both rows are then half-relaxed at once, both jobs start at time zero on one machine, and the cost is 0 — below either real branch, which is what a bound looks like. There is no schedule here at all: “job one is three-thirteenths before job two” is not a sentence about machines.
The material
Why the conjunction is infeasible, what each branch is, and what the relaxation says instead.
Two jobs share one machine. Job one takes four hours, job two takes three, and neither can run while the other is on the machine. Let x₁ and x₂ be the start times. Either job one finishes before job two starts, which is x₁ + 4 ≤ x₂, or job two finishes before job one starts, which is x₂ + 3 ≤ x₁. Exactly one of those must hold.
Given two rows A(x) ≤ a and B(x) ≤ b of which at least one must hold, the disjunctive formulation introduces one binary y and writes A(x) ≤ a + M_A(1 − y) together with B(x) ≤ b + M_B y, where each M is large enough to make its own row vacuous over the rest of the feasible region.
Written as ≤ rows, the pair above is x₁ − x₂ ≤ −4 and −x₁ + x₂ ≤ −3. With deadlines putting both start times in [0, 10], the most the first left-hand side can exceed its right-hand side is 10 − 0 − (−4) = 14, so M_A = 14; by the mirror argument M_B = 13. Each constant is the slack its own row needs to become harmless, and not one unit more.
Minimise x₁ + x₂. Fixing y = 1 enforces “job one first” and the model starts the jobs at (0, 4), costing 4. Fixing y = 0 enforces “job two first” and starts them at (3, 0), costing 3. Both are genuine schedules, the second is cheaper, and the integer problem wants the better of exactly these two — which is what the binary means.
Write both original rows together and add them: the left-hand sides cancel to 0 and the right-hand sides give −7, so the model asserts 0 ≤ −7 and is infeasible. That is the diagnosis to recognise, because the symptom is a solver reporting infeasibility on data that is perfectly consistent, and the usual response is to go looking for a typo in the processing times.
Now leave y continuous. The relaxation sets y = 3/13, starts both jobs at time zero, and reports 0. Every row is satisfied: y is large enough to relax the second row by 3 and small enough to relax the first by 4, so both are half-off at once. The value 0 is a perfectly good lower bound on the integer answer of 3. It is not a schedule, and the machine cannot run two jobs at once because a variable took a value between 0 and 1.
The two constants need not be equal and each must be valid for its own row: here 14 and 13. One M used for both, unchecked, is how a disjunction quietly becomes an implication — if the shared value is big enough for one row and too small for the other, then one branch of the “or” is partially enforced even when the binary says it should be off, and the model answers a question with one alternative half-deleted.
The same pair, repeated over every pair of jobs on every machine, is what makes a job shop an integer programme rather than a linear one. That is why “Scheduling” can prove single-machine rules by exchange arguments and still needs this course the moment two jobs contend for one resource: the sequencing decision is a binary, and there is no linear model of it.
The device generalises past two alternatives. Three rows of which exactly one must hold need three binaries summing to 1, each relaxing its own row by M(1 − y_k); and a two-level capacity — either run at the small size or at the large one — is the same pattern with the two rows being the two capacity limits. What does not generalise is guessing the constants: each one is sized against its own row, every time.
Interactive
One binary relaxes one row and enforces the other, and a fractional y describes nothing
Method
The check at the end is two re-solves rather than eight rows, and it is the same discipline.
x₁ − x₂ ≤ −4 and −x₁ + x₂ ≤ −3. Getting both into the same relation first makes the relaxation term easy to place and makes the sign errors visible while they are still cheap.
Then write M_A(1 − y) on that row and M_B y on the other. Writing the convention down is not ceremony: the two rows look alike, and a swapped pair gives a model that solves and means the opposite.
The most that row's left-hand side can exceed its right-hand side anywhere the other constraints allow. Here 14 and 13, from the deadlines. Two rows, two constants, two reasons.
y = 1 should give a schedule with job one first; y = 0 one with job two first. If either branch is infeasible or describes the wrong order, the fault is in the signs or in an M that is too small, and you have just found out which.
A fractional y is the relaxation's bound and it is not a plan. Looking at it once, and naming the impossible schedule it describes, is what stops it being reported later as an answer.
One instance, three formulations: the conjunction, the two fixed branches, and the relaxation. Only the middle one describes a machine.
The 0 ≤ −7 line is the one to memorise, because it is what the model says rather than what the solver says. A solver reports “infeasible” and a reader goes looking for bad data; adding the two rows takes ten seconds and names the real cause, which is that “or” was written as “and”.
The relaxation's y = 3/13 is worth reading arithmetically once. It is the smallest y that relaxes row B by the three hours it needs; and it is small enough that row A is still relaxed by 140/13, comfortably more than the four hours it needs. Both alternatives are switched most of the way off at the same time, which is precisely the plan that does not exist.
For a faded rehearsal, use the lab's second instance — a seven-hour job against a two-hour one, with the short job weighted twice as heavily in the objective. The supplied first move is that the tightest constants are now 19 and 14, from the same deadline argument. Work out both branches before opening the quiz and say which order wins, and by how much.
You should be able to write a disjunctive pair with one binary and two separately sized constants, say what each value of the binary enforces and what it makes vacuous, show in one line why writing both rows is infeasible, and read a fractional binary as a bound with an impossible plan behind it.
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.