Transforming constraints into linear inequality

Question

I want to model the following two constraints in terms of LP, but after trying various ways without success, I wonder if it is possible at all?

Given $x$ and $y_{ij}$ are binary variables. We need the following two constraints:

1. If $x = 1$, then $\sum_{i = 1}^{n} y_{ij}\leq 1$ for any $j=1,2,\ldots, n$
2. If $x=0$, then $\sum_{i = 1}^{n} y_{ij} = 2$ for any $j = 1,2,\ldots, n$.

Can someone please help me write these two constraints in terms of linear inequality? It seems so simple yet surprisingly difficult to me. Any help would really be appreciated.

Answer 1

Answer: \begin{cases} \sum\limits_{i=1}^n y_{ij} \leq 2 -x &\mbox{for every } j = 1, 2, \dotsc, n \\ \sum\limits_{i=1}^n y_{ij} \geq 2 - 2x &\mbox{for every } j = 1, 2, \dotsc, n \end{cases}

Motivation:

What you want can be rewritten as:

• If $x = 1$, then $0 \leq \sum\limits_{i=1}^n y_{ij} \leq 1$ for every $j = 1, 2, \dotsc, n$;
• If $x = 0$, then $2 \leq \sum\limits_{i=1}^n y_{ij} \leq 2$ for every $j = 1, 2, \dotsc, n$.

Therefore, we just need to find two linear functions $f, g$ such that $f(1) = 0$, $f(0) = 2$, $g(1) = 1$, $g(0) = 2$. This is easy to do, using slope-intercept or whichever is your favourite way to compute equations for straight lines.