# How to transform a logical constraint with integer variables?

Consider the binary variables $$x_1, x_2 \in \{0,1\}$$ and the integer variable $$y \in \mathbb{Z}$$ with $$0 \leq y \leq 3$$.

I'd like to formulate the following logical constraint:

$$x_1 = 1 \wedge y \geq 2 \implies x_2 = 1$$

and I don't have access to commercial solvers or modelling frameworks. Any ideas?

• It may be: 1) $x_1 \leq x_2$, $\quad$ 2) $y-2+\epsilon \leq (M+\epsilon)x_2$ $\quad$ with $M\leq1$. Commented Nov 30, 2022 at 12:37
• @A.Omidi Your 1) is too strong. For example, it mistakenly cuts off the feasible solution $(x_1,x_2,y)=(1,0,0)$. Commented Nov 30, 2022 at 17:41
• @RobPratt, Dear Rob, sorry for the delay and thanks for comment. Would you please say, 1) how (1,0,0) may be a feasible one? 2) Another approach I would like to try is by substituting $y \geq 2$ with an indicator constraint. If $z =1 \rightarrow y \geq 2$. Now, the original expression would be $x_1 = 1 \land z=1 \implies x_2 = 1$. The final result would be something like, ($x_1 + z - x_2 \leq 1$), ($y \geq 2-M(1-z)$),($y-2+\epsilon \leq (M+\epsilon)x_2$). Please, may I have your comments? Commented Dec 2, 2022 at 10:31
• @A.Omidi For $(1,0,0)$, the conditional $x_1 =1\land y\ge 2$ is false, so the proposition is true no matter what the value of the consequent. For your indicator constraint approach, you need the converse instead $y\ge 2\implies z=1$, equivalently, its contrapositive $z=0\implies y\le 1$. Commented Dec 2, 2022 at 13:20
• @A.Omidi glad to help. Yes, please post your approach as another answer, and I’ll upvote it. I guess you are asking my permission because I helped, and that is fine with me. Commented Dec 3, 2022 at 14:05

You can derive the desired linear constraint by rewriting in conjunctive normal form and rearranging to an equivalent implication: $$(x_1 \land (y\ge 2)) \implies x_2 \\ \lnot (x_1 \land (y\ge 2)) \lor x_2 \\ \lnot x_1 \lor (y\le 1) \lor x_2 \\ \lnot x_1 \lor x_2 \lor (y\le 1) \\ \lnot (x_1 \land \lnot x_2) \lor (y\le 1) \\ (x_1 \land \lnot x_2) \implies (y\le 1) \\ (x_1 \land \lnot x_2) \implies (2\le 3-y) \\ 2(x_1 + (1 - x_2) - 1) \le 3-y \\ 2(x_1 - x_2) + y \le 3$$ You can alternatively view this as a big-M constraint arising from the implication $$x_1-x_2=1 \implies y \le 1$$.

The range of values of the variable $$y$$ is quite small, so you could use the binary representation $$y = b_0 + 2b_1$$ with two binary variables $$b_0$$ and $$b_1$$ instead of the integer variable $$y$$.

Then your logical constraint is equivalent to

$$x_1 = 1 \wedge b_1 = 1 \implies x_2 = 1,$$

which can be modelled by

$$x_1 + b_1 \leq 1 + x_2.$$

• Multiplying by $2$ and adding $b_0$ would then yield $2(x_1-x_2)+y \le 2+b_0 \le 3$, avoiding the additional binary variables. Commented Nov 30, 2022 at 15:29
• @RobPratt Good catch. PS: Your answer is definitely more elegant (+1) than mine.
– joni
Commented Nov 30, 2022 at 16:14
• Thanks. I gave you a +1 as well. It is good to have a variety of approaches, and your formulation is tighter. Commented Nov 30, 2022 at 17:39

Another approach I was trying to do, also based on @RobPratt hints, would be by substituting $$y \geq 2$$ as an indicator constraint and changing the original logical expression into:

$$\{x_1 = 1 \wedge y \geq 2 \implies x_2 = 1\} \rightarrow \{x_1 = 1 \land \lnot z\implies x_2 = 1\}$$ $$\lnot x_1 \lor z \lor x_2$$ $$(1-x_1) + z + x_2 \geq 1$$ $$-x_1 + x_2 + z \geq 0$$

For the second part we need to add: $$y + Mz \leq 3$$ with $$M=2$$ to enforce $$y\ge 2\implies \lnot z$$.