4

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?

Ronaldinho
  • 385
  • 2
  • 5
  • It may be: 1) $x_1 \leq x_2$, $\quad$ 2) $y-2+\epsilon \leq (M+\epsilon)x_2$ $\quad$ with $M\leq1$. – A.Omidi Nov 30 '22 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)$. – RobPratt Nov 30 '22 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? – A.Omidi Dec 02 '22 at 10:31
  • 1
    @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$. – RobPratt Dec 02 '22 at 13:20
  • @RobPratt, Thanks for the clarification. For the second part, I will update that and back to you. – A.Omidi Dec 02 '22 at 13:32
  • @RobPratt, based on your hint, the constraints would be ($-x_1+x_2+z \geq 0$), ($y+Mz \leq 3$), with $M=2$. Would you please, say your insight about that? – A.Omidi Dec 03 '22 at 13:05
  • @A.Omidi you have changed your original interpretation of the two values of $z$, but your new formulation is still correct. Your big-M constraint enforces $y\ge 2\implies \lnot z$, and your first constraint enforces $(x_1 \land \lnot z) \implies x_2$. – RobPratt Dec 03 '22 at 13:41
  • @RobPratt, thank you so much. Could you please, may I add this as an answer? – A.Omidi Dec 03 '22 at 13:50
  • 1
    @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. – RobPratt Dec 03 '22 at 14:05

3 Answers3

11

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

RobPratt
  • 32,006
  • 1
  • 44
  • 84
7

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

joni
  • 1,572
  • 7
  • 14
  • 1
    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. – RobPratt Nov 30 '22 at 15:29
  • @RobPratt Good catch. PS: Your answer is definitely more elegant (+1) than mine. – joni Nov 30 '22 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. – RobPratt Nov 30 '22 at 17:39
3

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

A.Omidi
  • 8,832
  • 2
  • 13
  • 49