Modeling Decisions with Binary Variables

Image by Yannis Papanastasopoulos retrieved from Unsplash

Below, we present one of the most powerful tools in mathematical optimization modeling: the use of binary variables.

In pure Integer Linear Optimization problems, all variables must take integer values. However, there is an extremely important subgroup known as Binary Linear Optimization problems, where variables can only take the values $0$ or $1$. This approach is not only useful for making “yes or no” decisions, but it is also the key to translating complex logical conditions into mathematical constraints that keep the optimization model linear.

Modeling common relationships

The true art of mathematical optimization emerges when we need to represent more complex logical relationships. Below, we will see how to linearize them.

Disjunctive constraints (“OR” conditions)

Sometimes, a solution must satisfy one constraint or another, although both can also hold true simultaneously. These conditions are known as disjunctive constraints.

For example, imagine a knapsack problem where we want to impose the following condition: either we choose items 2 and 3 together, or we choose item 5 (where both situations can occur at the same time).

Let $x_j$ be a binary variable that takes the value $1$ if we select item $j$ and $0$ otherwise. The condition can be logically expressed as:

\[(x_2 + x_3 \geqslant 2) \lor (x_5 \geqslant 1)\]

To incorporate this condition into the model, we introduce an auxiliary binary variable $\delta$, moving all information from each initial constraint to one side of the inequality and leaving the binary variable (or its complement) multiplying a sufficiently large constant.

In this case, we can write:

\[2-x_2-x_3 \leqslant M_1(1-\delta)\] \[1-x_5 \leqslant M_2\delta\]

where $M_1=2$ and $M_2=1$ are the tightest valid bounds for this problem. In a Big-M formulation, it is best not to arbitrarily use huge values: the proper approach is to use the smallest valid bound that fully relaxes the constraint when it should not be active. This avoids introducing an unnecessarily weak formulation and can facilitate the solver’s job.

The variable $\delta$ determines which of the two conditions is enforced, although the other can also be satisfied:

• If $\delta=1$, the first constraint becomes $2-x_2-x_3\leqslant 0$, so necessarily $x_2=x_3=1$. The second constraint is relaxed.
• If $\delta=0$, the second constraint becomes $1-x_5\leqslant 0$, so necessarily $x_5=1$. The first constraint is relaxed.

Therefore, the auxiliary variable allows us to transform an A or B logical condition into a set of linear constraints.

Simple implications (“If … then …” conditions)

Another common scenario arises when one decision forces another. For example, if we select items 1, 2, and 3, then we must also select items 4 and 5.

If $x_j$ indicates whether we select item $j$, this condition can be logically expressed as:

\[x_1+x_2+x_3 \geqslant 3 \Rightarrow x_4+x_5\geqslant 2\]

An implication of the type if A then B is equivalent to not A or B, that is, we can use the previous procedure to model an implication. In the example above, the implication is equivalent to:

\[x_1+x_2+x_3 \leqslant 2 \lor x_4+x_5\geqslant 2\]

and its resulting formulation is:

• $x_1 + x_2 + x_3 - 2 \leqslant M_1 (1 - \delta)$, where $M_1 = 1$.

• $2 - x_4 - x_5 \leqslant M_2 \delta$, where $M_2 = 2$.

In this case, the values of $M_1$ and $M_2$ can be determined directly from the bounds of the variables. Since $x_1, x_2, x_3$ are binary, $x_1+x_2+x_3-2$ can take a maximum value of $1$, so $M_1=1$ is sufficient. Similarly, $2-x_4-x_5$ can take a maximum value of $2$, so $M_2=2$ is sufficient.

When implications involve only binary variables, many of these relationships can be modeled directly using simple inequalities. The four basic possibilities and their corresponding formulations are:

\[\begin{array}{c|c} x_j=0 \Rightarrow x_i=0 & x_j=0 \Rightarrow x_i=1 \\ x_i \leqslant x_j & x_i \geqslant 1-x_j \\ \hline\hline x_j=1 \Rightarrow x_i=0 & x_j=1 \Rightarrow x_i=1 \\ x_i \leqslant 1-x_j & x_i \geqslant x_j \end{array}\]

For example, if we want to express if we do not select item 4, we cannot select item 7, the logical condition is:

\[x_4=0 \Rightarrow x_7=0\]

which can be modeled simply as:

\[x_7 \leqslant x_4\]

The general idea is that binary variables allow us to represent logical decisions using linear constraints. This is especially useful for expressing conditions like “if … then …“, “either … or …“, and other relationships between decisions.

Fixed costs

In many optimization problems, using a resource incurs a fixed cost, regardless of the quantity used, in addition to a variable cost that depends on that quantity.

For example, imagine we want to buy a certain product. Let $x$ be the purchased quantity, with a cost of $c$ dollars per unit. Furthermore, the supplier charges a fixed cost $f>0$ every time an order is placed. In this case, the total cost is not simply proportional to the quantity purchased:

\[C(x) = \begin{cases} 0 & \text{if } x=0,\\ f+cx & \text{if } x>0. \end{cases}\]

The problem is that this function is discontinuous at $x=0$, and this type of behavior cannot be directly represented by a linear function. A standard way to model it is to introduce a binary variable $y$ indicating whether or not the order is placed:

\[y = \begin{cases} 1 & \text{if the order is placed},\\ 0 & \text{if the order is not placed}. \end{cases}\]

We can then write the cost as:

\[\min \; z = fy + cx\]

and add the constraint:

\[x \leqslant My\]

where $M$ is a valid upper bound on the quantity we can purchase.

This constraint establishes the link between the two variables:

• If $y=0$, then $x \leqslant 0$ and, since $x \geqslant 0$, necessarily $x=0$. The order is not placed, and the fixed cost is not paid.
• If $y=1$, we can have $x>0$. In that case, $f+cx$ appears in the objective function: we pay both the fixed cost and the variable cost.

Therefore, the complete model is:

\[\begin{align*} \min \quad & z = fy + cx\\ \text{s.t.:}\quad & x \leqslant My\\ & x \geqslant 0\\ & y\in\{0,1\} \end{align*}\]

The key take-away is that the binary variable represents the decision to activate or deactivate a specific activity, while the continuous variable represents the quantity associated with that activity.

This pattern appears constantly in optimization models. Whenever a decision incurs a fixed cost for activating, using, opening, hiring, installing, or performing something, we can introduce a binary variable to represent that decision and link it to the corresponding quantity via a constraint of the type:

\[x \leqslant My\]

Thus, a discontinuous cost function can be incorporated into a linear model using a binary variable.

Linearization of variable products

Products of variables cause a function or constraint to lose linearity. However, when binary variables are involved, these products can be transformed into linear relationships by introducing an auxiliary variable.

The core idea is to replace the product with a new variable and add constraints that guarantee this new variable takes the exact value of the product.

Product of two binary variables

Suppose we have two binary decisions $\beta_1$ and $\beta_2$, and we want to represent whether both decisions are made simultaneously. We define a new binary variable $\delta$ as:

\[\delta = \beta_1\beta_2\]

Since $\beta_1$ and $\beta_2$ can only take values $0$ and $1$, the product $\delta$ equals $1$ only when both variables equal $1$. We can eliminate the product and replace it with the following linear constraints:

• $\delta \leqslant \beta_1$

• $\delta \leqslant \beta_2$

• $\beta_1+\beta_2-\delta \leqslant 1$

These constraints guarantee that:

• If $\beta_1=0$ or $\beta_2=0$, then $\delta=0$.
• If $\beta_1=\beta_2=1$, then $\delta=1$.

Therefore, we can use $\delta$ in the rest of the model as a substitute for the product $\beta_1\beta_2$.

It is worth noting that linearizing a product is not always the best option. Linearization introduces a new variable and several additional constraints, which can considerably increase the size and complexity of the model.

Therefore, before introducing an auxiliary variable to represent a product, it is advisable to check whether a simpler equivalent formulation exists that directly expresses the same relationship by taking advantage of other constraints in the problem.

Linearization is especially useful when the product appears explicitly in the objective function or in a constraint and there is no simple way to reformulate it using existing variables. Conversely, if the variables in the product are already linked by other constraints, it may be possible to leverage those relationships and avoid adding new variables and constraints.

Product of a binary and a continuous variable

The same idea can be applied when multiplying a binary variable by a non-negative continuous variable. For instance, suppose $x \geqslant 0$ represents a quantity and $\beta$ indicates whether a given activity is active. If we want the relevant quantity in the model to be $x$ only when $\beta=1$, we can define:

\[\delta = x\beta\]

The issue is that the product $x\beta$ is non-linear. To linearize it, we need to know an upper bound for $x$. Suppose that:

\[0\leqslant x\leqslant M\]

where $M$ is a valid upper bound for $x$. We can use the following constraints:

• $\delta \leqslant x$

• $\delta \leqslant M\beta$

• $\delta \geqslant x-M(1-\beta)$

• $\delta \geqslant 0$

These are the well-known Fortet inequalities (Fortet, 1960) for this case. Thus:

• If $\beta=0$, the constraints force $\delta=0$, regardless of the value of $x$.
• If $\beta=1$, the constraints force $\delta=x$.

Therefore, in both cases, we have:

\[\delta=x\beta\]

The general idea is that whenever a product of variables breaks linearity, we can introduce an auxiliary variable to represent that product and add linear constraints to ensure equivalence.

This procedure transforms certain non-linear terms into a set of linear constraints and is one of the most common techniques for formulating Mixed-Integer Linear Optimization models.

---

Mastering formulation using binary variables is what turns mathematical optimization into a versatile tool capable of tackling real-world strategic decisions.

---

Would you like to keep exploring the world of Operations Research? Discover more posts on the topic here.