Back to the on-screen lesson ·
Fixed costs, minimum batches and logical conditions, written with indicator variables and big-M links.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to model a fixed cost with an indicator variable and a big-M link, write at-most, at-least, exactly-one and implication conditions as linear constraints on binaries, choose the smallest usable big-M and say why a larger one slows the search, and tell which requirements a single binary can carry.
You know that a cost which jumps cannot be linear, and you have met the fix in passing. This lesson makes it a technique, with the two constraints that go with it and the number that decides whether the model is usable.
A binary variable takes the value $0$ or $1$. Used as an indicator it stands for a yes-or-no fact — this line is open, this supplier is used — and a big-$M$ constraint such as $x \le My$ ties a quantity to it. $M$ is a constant chosen by the modeller, and choosing it badly is the commonest performance mistake in the subject.
A binary carries one yes-or-no decision. On its own it does nothing; it becomes useful when linear constraints tie it to the quantities.
Fixed costs. Put $fy$ in the objective and $x \le My$ among the constraints. If $y = 0$ then $x = 0$ and no fee is paid; if $y = 1$ the constraint is slack and the fee has been paid.
Either nothing or a real batch. Add $x \ge Ly$ as well, and $x$ is either zero or at least $L$.
Logic. $\sum y_i \le 1$ is 'at most one'; $\sum y_i = 1$ is 'exactly one'; $y_A \le y_B$ is 'if A then B', because it forbids the single combination $y_A = 1$ with $y_B = 0$.
Choosing $M$. Take the smallest value that cannot bind — usually the capacity. A larger $M$ gives the same integer problem and a weaker relaxation, because a fractional $y$ as small as $x/M$ pays almost none of the fee. That makes the bound loose, the pruning poor, and the search long.
Another way: steps
Another way: example
A line with capacity $40$ and a setup fee of $500$: objective gains $-500y$, constraints gain $x \le 40y$. Not $x \le 10000y$, which is correct and much slower.
$M$ is set to a huge round number on the grounds that a bigger number is safer. It is safer for correctness and ruinous for speed, because the relaxation it produces is nearly worthless. The second error is asking a binary to hold a quantity — a variable meaning both 'whether' and 'how much' — which produces a model whose constraints cannot be read.
A supplier will take an order of at least $10$ units, or none at all, up to a capacity of $60$.
Two cases to switch between.
One binary $y$, with $x \le 60y$ forcing $x = 0$ when $y = 0$.
The upper link.
And $x \ge 10y$ forcing $x \ge 10$ when $y = 1$. Two rows, one binary, and the disjunction is expressed.
The lower link.
The condition counts the projects that run, and each binary is $1$ exactly when its project does.
Count the binaries.
So $y_1 + y_2 + y_3 + y_4 \le 2$, with each $y_i$ binary.
A production quantity $x$ is tied to a binary $y$ by the constraint $x \le 70y$. Fill in the bound this puts on $x$ for each value of $y$.
| The largest $x$ allowed | |
|---|---|
| With $y = 0$ | |
| With $y = 1$ |
A model has binaries $y_1$, $y_2$ and $y_3$ for three projects out of $5$ under consideration. Match each condition to the constraint that says it.
| $y_1 + y_2 + y_3 \le 1$ | $y_1 + y_2 + y_3 \ge 2$ | $y_1 + y_2 + y_3 = 1$ | $y_1 \le y_2$ | |
|---|---|---|---|---|
| At most one of the three | ||||
| At least two of the three | ||||
| Exactly one of the three | ||||
| If project 1 runs then project 2 must |
A model has $10$ binary variables. How many combinations of values are there?
Answer:
A line has capacity $48$ and a setup fee of $654$, modelled by $x \le My$ with $y$ binary. What should $M$ be?
A knapsack holds $32$ kilograms. Items weighing $11$ and then $5$ are packed. Complete the capacity remaining after each.
After the first item a kilograms remain, and after the second b.
Select every requirement that a single binary variable, with linear constraints, can express.
This task has no paper form; do it on a device.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A production quantity $x$ is tied to a binary $y$ by the constraint $x \le 82y$. Fill in the bound this puts on $x$ for each value of $y$.
| The largest $x$ allowed | |
|---|---|
| With $y = 0$ | |
| With $y = 1$ |
You can model fixed costs, minimum batches and logical conditions with binary variables and linear links. Say in your own words why a needlessly large big-M makes a correct model slow.
7. Your turn: write 'at most two of the four projects run' with binaries, step 2