# Linearizing if else conditions in ILP

We are given three binary indicator variables $$X_{ij}, Y_{jk}$$ and $$Z_{jl}$$. Write linear constraints such that,

a) if $$X_{ij}$$ is equal to 1, then for that $$j$$ when $$X_{ij} = 1$$, exactly one $$Y_{jk} = 1$$, while if $$X_{ij}$$ is equal to 0, then for that $$j$$ all $$\sum_{k} Y_{jk}$$ should be 0

b) if $$X_{ij}$$ and $$Y_{jk}$$ is equal to 1, exactly one $$Z_{jl} = 1$$, while $$X_{ij} = 0$$ implies $$Y_{jk} = 0$$ from the first constraint and also ensure $$\sum_{l} Z_{jl} = 0$$ for that $$j$$

The first constraint can be expressed as $$(1 - X_{ij}) + \sum_{k}{Y_{jk} = 1}, \forall i, j$$ derived from the boolean CNF expression

The second constraint can be expressed as $$(1 - X_{ij}) (1 - Y_{jk}) + \sum_{l}{Z_{jl} = 1} , \forall i, j, k$$, but is quadratic. How can this be expressed linearly?

• Are you sure you only want to model $x_{ij} = 0 \implies z_{jl} = 0$ for all $i,j,l$? Judging by your proposed second constraint I guess you rather want to model $x_{ij} = 0 \implies \sum_{l} z_{jl} = 0$ for all $i,j,l$.
– joni
Commented Sep 10, 2023 at 12:21
• @joni thats correct what you pointed out Commented Sep 10, 2023 at 12:44

Your first constraint enforces more than was asked. When $$X_{ij}=0$$, it forces $$\sum_k Y_{jk}=0$$, hence $$Y_{jk}=0$$ for all $$k$$. To enforce only $$X_{ij}=1 \implies \sum_k Y_{jk}=1,$$ you can instead impose $$-(1-X_{ij})\le \sum_k Y_{jk} -1 \le M_j(1-X_{ij}).$$

For the second constraint, you can apply the same big-M approach by first introducing $$W_{ijk}$$ to represent the product $$X_{ij}Y_{jk}$$ and additionally imposing $$W_{ijk}\ge X_{ij}+Y_{jk}-1$$.

Now that you have modified the question, it suffices to linearize the product of two binary variables, as shown in How to linearize the product of two binary variables?

• When $X_{ij} = 0$, none of the $Y_{jk}$ should be 1 for that value of $j$, I have captured that, $Y_{jk}$ should only be 1 only in the condition described above, do you think its too strong? I have edited and clarified this @RobPratt Commented Sep 10, 2023 at 11:59

Besides @RobPratt's answer, the first condition would be (for simplicity I omitted indices $$i$$ and $$j$$ and continued with only two $$y$$ variables:

$$x \implies (y_1 \oplus y_2)$$

$$\lnot x \lor (y_1 \oplus y_2)$$

$$y_1 + y_2 + (1-x) \geq 1$$

$$- y_1 - y_2 - x \geq -2$$

$$y_1 + y_2 -x \geq 0 \quad (1)$$

$$y_1 + y_2 + x \leq 2 \quad (2)$$

Now, by adding indices the constraints would be of the form:

$$\sum_{k} y_{jk} - x_{ij} \geq 0 \quad \forall i \in I, j \in J \quad (1)$$ $$\sum_{k} y_{jk} + x_{ij} \leq 2 \quad \forall i \in I, j \in J \quad (2)$$

For the second, the procedure almost is the same.