Modelling with Binary Variables

A variable restricted to zero or one records a yes-or-no decision, and a small vocabulary of linear constraints turns logical conditions into algebra: at most one of these, if this then that, this only if that is open. The patterns are few and compose, and the recurring error is writing a condition that is true of the situation but does not constrain the model.

Definition

A binary variable satisfies $x \in {0, 1}$ , interpreted as a yes-or-no decision: $1$ for chosen, open, assigned, used; $0$ otherwise. What each value means must be stated, because nothing in the algebra records it.

A short vocabulary covers most conditions.

Selection count. At most one of a set: $\sum_{j \in S} x_{j} \leq 1$ . Exactly one: $= 1$ . At least one: $\geq 1$ . At most $k$ : $\leq k$ .

Implication. "If $x$ then $y$ " is $x \leq y$ . Choosing $x = 1$ forces $y = 1$ ; $x = 0$ leaves $y$ free. "Not both" is $x + y \leq 1$ .

Linking a decision to a quantity. To allow a continuous quantity $q$ only when $x = 1$ , write

q \leq M x,

with $M$ an upper bound on $q$ . Then $x = 0$ forces $q = 0$ , and $x = 1$ imposes only $q \leq M$ . To require the quantity when the decision is taken, add $q \geq ℓ x$ for a minimum level $ℓ$ .

Fixed charges. A cost incurred only if an activity runs is $f x$ in the objective, with $q \leq M x$ linking the two. Without that link the objective can set $x = 0$ while $q$ runs freely, and the charge is never paid.

On the choice of $M$ . Any valid upper bound works logically. A loose one weakens the relaxation badly, so $M$ should be the smallest defensible bound rather than a large round number.

Assumptions and scope

The meaning of each binary variable must be stated, including which outcome is 1. The algebra is symmetric between the two values and carries no interpretation of its own.
A linking constraint requires a valid upper bound $M$ . If the bound is not genuinely an upper bound on the quantity the constraint forbids feasible plans; if it is loose the relaxation is weakened and the program becomes harder to solve.
An implication constraint is directional. $x \leq y$ says if $x$ then $y$ , and says nothing about what follows from $y$ . Writing $x = y$ instead asserts both directions and usually over-constrains the model.
A constraint that is satisfied by every assignment the model can make restricts nothing, whatever it says about the situation. Checking that a proposed constraint forbids something is part of writing it.
Binary variables record decisions, not quantities. Summing them gives a count of decisions taken, which is meaningful; multiplying one by a rate as though it were an amount is not.

Worked material

Example

Five conditions, five constraints

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} \geq 0$ tonnes from each.

"Open at most two depots."

y_{A} + y_{B} + y_{C} \leq 2 .

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

y_{A} \leq y_{B} .

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."

y_{B} + y_{C} \leq 1 .

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

q_{A} \leq 500 y_{A}, q_{B} \leq 500 y_{B}, q_{C} \leq 500 y_{C} .

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."

q_{A} \geq 100 y_{A}, q_{B} \geq 100 y_{B}, q_{C} \geq 100 y_{C} .

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

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.

Non-example

Constraints that are true and useless

Not a constraint: $y_{A} + y_{B} + y_{C} \geq 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} \leq 500$ when the sandwich $q_{A} \leq 500 y_{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 = 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.

Contrast

True is not the same as binding

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} \leq 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} \leq 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.

Common errors

Common misconception

A constraint that makes a true statement about the situation is a correct constraint, so if the sentence is right the algebra must be doing its job.

Modelling with Binary Variables

Assumptions and scope

Worked material

Five conditions, five constraints

Constraints that are true and useless

True is not the same as binding

Common errors

Related units

Requires

Connected

Learn this topic

Used in

Sources

Settings

Focus timer

Today

Last seven days

Where the time went

Recent sessions

Settings

Notifications

Your history