4
$\begingroup$

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?

$\endgroup$
9
  • $\begingroup$ It may be: 1) $x_1 \leq x_2$, $\quad$ 2) $y-2+\epsilon \leq (M+\epsilon)x_2$ $\quad$ with $M\leq1$. $\endgroup$
    – A.Omidi
    Nov 30, 2022 at 12:37
  • $\begingroup$ @A.Omidi Your 1) is too strong. For example, it mistakenly cuts off the feasible solution $(x_1,x_2,y)=(1,0,0)$. $\endgroup$
    – RobPratt
    Nov 30, 2022 at 17:41
  • $\begingroup$ @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? $\endgroup$
    – A.Omidi
    Dec 2, 2022 at 10:31
  • 1
    $\begingroup$ @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$. $\endgroup$
    – RobPratt
    Dec 2, 2022 at 13:20
  • 1
    $\begingroup$ @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. $\endgroup$
    – RobPratt
    Dec 3, 2022 at 14:05

3 Answers 3

11
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – RobPratt
    Nov 30, 2022 at 15:29
  • $\begingroup$ @RobPratt Good catch. PS: Your answer is definitely more elegant (+1) than mine. $\endgroup$
    – joni
    Nov 30, 2022 at 16:14
  • $\begingroup$ Thanks. I gave you a +1 as well. It is good to have a variety of approaches, and your formulation is tighter. $\endgroup$
    – RobPratt
    Nov 30, 2022 at 17:39
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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