Linearizing if else conditions in ILP

Question

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?

Answer 1

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?

Answer 2

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.