# Expressing the condition as a set of linear constraints

Express the condition "$x = 0$ if and only if $y = 0$" as a set of linear constraints, where $x,y$ are integers such that $- 5 \le x \le 8$ and $0 \le y \le 1$

• If you're not sure whether your solution works, try proving that it does. We cannot help you unless there is a specific step you are worried about. – Yuval Filmus Apr 2 '17 at 12:55
• Or, write a problem to exhaustively check all cases. There are only 28 cases (14 values of $x$, 2 values of $y$); you can check all of them and see whether the condition holds or not and whether all the inequalities are satisfiable or not. – D.W. Apr 2 '17 at 16:03
• @YuvalFilmus i have never seen an example of type $x = a \leftrightarrow y = a$ given the domain of $x,y$ hence my worry if i solved is correctly. Would be nice if you show some examples of such types. Most examples i saw i inequality type with "if then" or "either or". – user_777 Apr 3 '17 at 2:02
• @D.W. how do you check all 28 cases? – user_777 Apr 3 '17 at 2:03
• $y=1 \vee x=0$ is not always true – Dmitri Chubarov Apr 3 '17 at 7:43

## 2 Answers

Let us instead translate $x=0 \leftrightarrow y=0$ into disjunctive normal form. We would get

$$(x=0 \wedge y=0 ) \vee (x>0 \wedge y=1) \vee (x<0 \wedge y=1)$$

Each conjunction is a linear constraint.

In your solution you assumed that the constraint $y=1 \vee x=0$ is always true. In fact $y=1 \vee y=0$ is always true, since this is the domain of $y$.

If you kept this constraint, you would have eliminated solutions where $y=0$ and $x \not= 0$.

Another issue is with your interpretation of the constraints. The pair $$\begin{array}{c} -M < x < 0\\ y=0 \end{array}$$ is a set of two constraints not a single constraint, therefore it is satisfied by the following 19 pairs $(-5,0),...,(8,0),(-5,1),...,(-1,1)$. The first 14 pairs clearly violate the condition $x=0 \leftrightarrow y=0$.

• When you have $y = 0$ any value of $x$ other than $0$ will violate logical condition. You can check this by writing a small program and putting in your if statement $(x \ne 0 \vee y = 0) \wedge (y \ne 0 \vee x = 0)$, then you can set $y = 0$ and $x$ for example $x = \{ - 100,100\}$ . It will always print $x = 0$. Now if you set $y = 1$ it will print $x = [ - 100, - 1] \cup [1,100]$, of course assuming we are not applying the domain restriction for $x$ here but just checking what values of $x$ the logic will pass through. Thus you cannot have pairs like $(-5,0),(-4,0)$. – user_777 Apr 8 '17 at 2:45

I have managed to solve this problem:

So we must apply integer programming to satisfy logical condition: $$(x \ne 0 \vee y = 0) \wedge (y \ne 0 \vee x = 0)$$

The encoding i got $${M_1}y \le x \le {M_2}y \cup {M_3}y \le x \le {M_4}y{\text{ }}$$

Now set $${M_1} = - 5,\,{M_2} = - 1,\,{M_3} = 1,\,{M_4} = 8$$

The encoding becomes $$-5y \le x \le -y \cup y \le x \le 8y{\text{ }}$$

The logical condition implies when $y = 0$, the value of $x = 0$. When $y = 1$, the value of $x \in [ - 5, - 1] \cup [1,8]$. If fact, when $y = 1$, integer variable $x$ can take on any value from $( - \infty , - 1] \cup [1,\infty )$. Hence we must provide an encoding that will force $x$ to take all values from its domain excluding $0$.

Case $y = 0$:

The encoding results in $0 \le x \le 0$, which forces $x = 0$

Case $y = 1$:

The encoding results in $$- 5 \le x \le - 1 \cup 1 \le x \le 8$$

Thus, depending on $y = \{ 0,1\}$ a program can assign $x$ any value from its domain.