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$

  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Apr 2 '17 at 12:55
  • $\begingroup$ 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. $\endgroup$ – D.W. Apr 2 '17 at 16:03
  • $\begingroup$ @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". $\endgroup$ – user_777 Apr 3 '17 at 2:02
  • $\begingroup$ @D.W. how do you check all 28 cases? $\endgroup$ – user_777 Apr 3 '17 at 2:03
  • 1
    $\begingroup$ $y=1 \vee x=0$ is not always true $\endgroup$ – Dmitri Chubarov Apr 3 '17 at 7:43

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$.

  • $\begingroup$ 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)$. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.