Modelling with Binary Variables

A factory either opens a line or it does not. What should a decision variable mean when 0.4 factories is nonsense?

The vocabulary is small. Four or five patterns cover most of what arises, and they compose, so a complicated set of conditions is usually several simple constraints rather than one clever one.

What takes practice is not the patterns but the reading. Deciding that a sentence is an implication, noticing that a cost is only incurred when an activity runs, spotting that two conditions are the same condition stated twice, that is where the work is, and it is why this is a formulation competence rather than an algebraic one.

This unit assumes you know what integrality is and can formulate a linear program.

The canonical text gives the switch reading and the linking pattern. Two things decide whether a binary model solves in reasonable time, and neither is about correctness.

$M$ is a modelling decision, not a formality. $q\le Mx$ is correct for any $M$ at least as large as the largest $q$ the situation permits, and wrong only if it is too small. But solvers begin by relaxing integrality, and under that relaxation a fractional $x=0.001$ already licenses $q\le 0.001M$. A vast $M$ therefore makes the first bound nearly worthless, and the search that follows has almost nothing to prune with. Use the tightest bound the situation actually supports: a depot's capacity, not a round number chosen for safety.

The characteristic error is a missing link, not a wrong coefficient. A model that defines $x_{\text{open}}$ and $q$ without any constraint relating them is feasible, solvable, and silently wrong: nothing stops the solver shipping from a closed depot, and since opening costs money it will never choose to open. The symptom is an optimal value that looks too good and a solution that violates a condition stated in prose but never written down.

Reading each constraint back as English, and asking which combinations it forbids, catches both.

A binary variable satisfies $x\in \{0,1\}$, standing for a yes-or-no decision. Which outcome is $1$ must be stated; the algebra carries no interpretation.

Selection counts. For a set $S$ of options:

Implication. "If $x$ then $y$" is

Setting $x=1$ forces $y=1$; $x=0$ leaves $y$ free. It is directional: it says nothing about what follows from $y$. "Not both" is $x+y\le 1$; "both or neither" is $x=y$.

Linking a decision to a quantity. To permit a continuous $q$ only when $x=1$:

with $M$ an upper bound on $q$. Then $x=0$ forces $q=0$, and $x=1$ imposes only $q\le M$. To require a minimum level when the decision is taken, add $q\ge \ell x$.

Fixed charges. A cost incurred only if an activity runs contributes $fx$ to the objective, with $q\le Mx$ linking them. Without the link a minimising objective sets $x=0$ while $q$ flows freely, and the charge is never paid.

Choosing $M$. Any valid upper bound is logically correct. A loose one weakens the relaxation severely, so use the smallest bound the situation justifies.

Define a binary variable for each yes-or-no decision, and say which outcome is 1. Write the meaning down in words beside the symbol. Most later confusion traces to a variable whose direction was never fixed.

Go through the description one sentence at a time. Each sentence is either a condition to encode, a quantity to bound, or commentary. Classify it before writing algebra; sentences that turn out to be commentary are the ones that produce constraints forbidding nothing.

Name the pattern before writing the constraint. Is this a selection count, an implication, a link between a decision and a quantity, or a fixed charge? The pattern determines the form, and reaching for algebra before naming it is how implications end up written as equalities.

Respect the direction of an implication. "If $x$ then $y$" is $x\le y$. Check by asking which single combination is forbidden: here it is $x=1$ with $y=0$. If the sentence forbids a different combination, the constraint is the wrong way round.

Bound every linking constraint as tightly as the situation allows. Derive $M$ from a capacity, a demand, or a stated maximum rather than choosing a round number. Record where it came from.

Test each constraint by naming something it forbids. Produce one assignment of the variables that the constraint rules out and that the model would otherwise have permitted. A constraint with no such assignment is doing nothing and should be removed or rewritten.

Check the objective for decisions that carry costs. A fixed charge belongs in the objective with its binary variable, and needs a linking constraint to make it payable. A charge without a link is never incurred.

A firm may open depots $A$, $B$, $C$, with binaries $y_A,y_B,y_C$ where $1$ means open. It ships $q_A,q_B,q_C\ge 0$ tonnes from each.

"Open at most two depots."

"If $A$ opens, $B$ must open."

Forbidden: $y_A=1$ with $y_B=0$, and nothing else. Writing $y_A=y_B$ would also forbid opening $B$ alone, which the sentence permits.

"$B$ and $C$ cannot both open."

"Nothing ships from a closed depot; each depot handles at most 500 tonnes."

Here $M=500$ comes from the stated capacity, which is exactly where it should come from.

"An opened depot must ship at least 100 tonnes."

When $y=0$ this reads $q\ge 0$, which is already true; when $y=1$ it imposes the minimum. The two linking constraints together give the sandwich $100y\le q\le 500y$.

Check one combination. $y_A=1,y_B=1,y_C=0$ with $q_A=200$, $q_B=450$, $q_C=0$: two depots open, the implication holds, $B$ and $C$ are not both open, every quantity is inside its sandwich. Feasible.

Problem. A workshop may commission a machine at a one-off cost of £8,000. If commissioned, it produces up to $600$ units at £4 each; if not, it produces nothing. Units sell for £19. Formulate the profit-maximising decision, and say what goes wrong if the link is omitted.

Goal. A correct model, and a demonstration of why one constraint is load-bearing.

Relevant principle. A fixed charge needs its binary in the objective and a linking constraint, or the charge can be avoided while its benefit is enjoyed.

Step 1: variables. $x\in \{0,1\}$, $1$ if the machine is commissioned. $u\ge 0$, units produced.

Step 2: the objective. Revenue $19u$, variable cost $4u$, fixed cost $8000x$:

Step 3: the capacity and the link. Production is capped at $600$ and is only possible if commissioned. One constraint does both:

With $x=0$ this forces $u\le 0$, hence $u=0$. With $x=1$ it is the capacity limit.

Step 4: solve by cases. With $x=0$: $u=0$ and profit $0$. With $x=1$: maximise $15u-8000$ subject to $u\le 600$, so $u=600$ and profit $9000-8000=1000$.

Answer. Commission the machine and produce $600$ units, for a profit of £1,000.

Step 5: now omit the link. Keep the objective and replace $u\le 600x$ with $u\le 600$. The solver sets $x=0$, why pay £8,000?, and $u=600$, reporting profit $9000$.

What that answer says. Produce $600$ units on a machine that was never commissioned. The model permits it because nothing connects $u$ to $x$; the binary appears only in the objective, as a cost with no compensating benefit, so it is switched off.

A fixed charge is not modelled by putting a cost in the objective. It is modelled by the cost and the link. Without the link the charge is optional, and an optimiser will always decline it.

Check. With the link restored, $x=0$ forces $u=0$, so the £9,000 plan is infeasible and the reported optimum is the genuine £1,000.

Not a constraint: $y_A+y_B+y_C\ge 0$. Every assignment satisfies it, because the variables are already nonnegative. It is a true sentence about the model that forbids nothing.

Not a constraint: $q_A\le 500$ when the sandwich $q_A\le 500y_A$ is already present. The tighter constraint implies the looser one, so adding it changes no feasible set. Harmless, but it is not doing the job the modeller thinks it is doing, if they believed this was what stopped shipping from a closed depot, they have not written that condition at all.

Not an implication: $y_A=y_B$ for "if $A$ opens then $B$ opens". The equality also forbids $B$ open with $A$ closed, which the sentence explicitly allows. It over-constrains, and it can make an optimal plan infeasible.

Not a link: a fixed cost in the objective with no constraint tying it to the activity. The binary is then pure cost with no consequence, so a maximising model sets it to zero and enjoys the activity free.

Not a bound derived from the situation: $M=\mathrm{1,000,000}$. Logically valid, and it makes the relaxation nearly useless: $y=0.0005$ already permits $q=500$. The relaxed answer becomes meaningless and the solve becomes far harder.

Not a binary decision: a count. "How many vans to hire" is a general integer variable. Writing it binary forbids hiring more than one.

A constraint's job is to forbid something. Whether the sentence it encodes is true of the situation is a separate question, and conflating the two produces models that look thorough and constrain nothing.

A modeller reads "each depot can handle at most 500 tonnes" and writes $q_A\le 500$. True. They read "nothing ships from a closed depot" and, having already written a capacity constraint, feel the capacity is covered. The second condition never gets encoded, and $q_A=400$ with $y_A=0$ remains feasible: four hundred tonnes shipped from a depot that was never opened.

Why it is hard to see. Every constraint in the model is a true statement. Reviewing the model by reading the constraints and checking they are true will pass this model, because the fault is not a false statement. It is a missing one.

The test that catches it. For each constraint, name an assignment it forbids that the rest of the model would otherwise permit. For $q_A\le 500$ that is $q_A=600$, which is genuine work. Then ask of each condition in the description: which constraint forbids its violation? "Nothing ships from a closed depot" has no answer, and the gap becomes visible.

The general shape of the error. It is not confined to binaries. Any model can contain constraints that restate something already implied, while a condition the modeller believes is covered has no algebraic representative at all. Binaries make it more common because logical conditions feel like they have been handled once they have been written down in words.

The habit. Two passes. Once through the constraints, asking what each forbids. Once through the description, asking which constraint enforces each condition. The second pass is the one that finds what is missing, and it is the one most often skipped.

1. Write constraints for: exactly one of four suppliers is chosen; supplier 2 may only be chosen if supplier 1 is; suppliers 3 and 4 cannot both be chosen.

2. A machine has a £5,000 setup cost and a capacity of $900$ units. Write the objective terms and the linking constraint, and say what happens if the link is omitted.

3. A modeller writes $x\le y$ and $y\le x$ for "if we lease the warehouse we must insure it". What have they actually asserted, and what does it wrongly forbid?

4. For a quantity known never to exceed $80$ by a capacity limit, a modeller uses $M=\mathrm{10,000}$ in a linking constraint. The model is correct. Give two reasons to change it anyway.

5. Look at this constraint set: $x_1+x_2\le 2$, with $x_1,x_2$ binary. What does it forbid? What should be written instead if the intent was "not both"?

A binary variable records a yes-or-no decision, and which outcome is $1$ must be stated because the algebra does not carry it.

The vocabulary is short. Selection counts are sums bounded by a number. "If $x$ then $y$" is $x\le y$, and it is directional, check it by asking which single combination it forbids. "Not both" is $x+y\le 1$. A quantity permitted only when a decision is taken is $q\le Mx$, with a minimum level added as $q\ge \ell x$.

A fixed charge needs both its cost in the objective and a linking constraint. Without the link, the charge is optional and an optimiser declines it while keeping the benefit.

Choose $M$ from the situation. A capacity, a demand, a stated maximum. A loose bound is logically valid, weakens the relaxation badly, and makes the program harder to solve.

The recurring error is a constraint that is true and binding on nothing. Test every constraint by naming an assignment it forbids, then read the description again asking which constraint enforces each condition. The second pass is what finds the condition you believed you had written down and had not.