3

Let's have binary variables $x$ and $y$. I'd like to define a helping binary variable $z$ such that $$ z = 1 \; \;\; \mathrm{iff} \; \; \; x + y = 2.$$ If I wanted to express the equivalence between binary variables $a$ and $b$, I would simply convert them into a conjunctive normal form: $$ a \Leftrightarrow b \equiv (a \Rightarrow b) \land (b \Rightarrow a) \equiv (\lnot a \lor b) \land (\lnot b \lor a)$$ and do a standard SAT $\to$ ILP conversion: $$ (1 -a) + b \geq 1, $$ $$ (1 - b) + a \geq 1. $$ Now let's try to substitute $a \to (z = 1)$ and $b \to (x + y = 2)$ into the CNF: $$ (\lnot (z = 1) \lor (x + y = 2)) \land (\lnot (x + y = 2) \lor (z = 1)). $$ Since we can't use inequalities, we can rewrite the equalities as follows $$ (\lnot (z \geq 1) \lor (x + y \geq 2)) \land (\lnot (x + y \geq 2) \lor (z \geq 1)) $$ and then we can simply negate the inequalities $$ ((z \leq 0) \lor (x + y \geq 2)) \land ((x + y \leq 1) \lor (z \geq 1)). $$ Now, my idea was to use the fact that the logical AND is implicit within the constraints and that we can emulate logical OR between the inequalities using big $M$. Let's define helping variables $a_1$ and $a_2$. $$ z \leq \mathrm{M}a_1, $$ $$ x + y + \mathrm{M}(1 - a_1) \geq 2, $$ $$ x + y \leq 1 + Ma_2, $$ $$ z + M(1 - a_2) \geq 1. $$ Now this won't work since we could just use $a_1 = 1$ and $a_2 = 0$ and there would be no constraint on $z$.

My idea is that we would somehow need to connect the lefthand side of the logical AND with the righthand side.

Was my approach correct up until the point right before the last conversion?

How would one go about expressing the logical rules between entire equalities and inequalities in general?

RobPratt
  • 32,006
  • 1
  • 44
  • 84
tomashauser
  • 133
  • 4

3 Answers3

4

For binary variables $x$ and $y$, notice that $x+y=2$ is equivalent to $xy=1$, so you want to linearize $z=xy$. I gave a derivation via conjunctive normal form in my answer here: https://or.stackexchange.com/a/473/500

RobPratt
  • 32,006
  • 1
  • 44
  • 84
  • Nice, I'll have a look at that, but what if the epxression was something that was not obvious like this? Is there a general way of converting the equivalence of two inequalities into constraints? – tomashauser Mar 20 '23 at 12:55
  • How general do you want? Are you asking how to model $f(x)\le a \iff g(x)\le b$, where $f$ and $g$ are linear functions of variable $x\in\mathbb{R}^n$, and $a$ and $b$ are constants? – RobPratt Mar 20 '23 at 13:05
  • Yes, that's exactly it. If there is a nicer way of doing it there are only binary variables or whatever, than that could also be useful. – tomashauser Mar 20 '23 at 13:07
  • OK, please open a separate question for that. – RobPratt Mar 20 '23 at 13:08
  • I already asked that in the question and in the title. I just chose some random constraints to ilustrate what I wanted and to show my attempt to solving it. – tomashauser Mar 20 '23 at 13:09
  • 2
    See my new question and answer here: https://or.stackexchange.com/questions/10172/how-to-enforce-logical-implication-sum-j-a-j-x-j-le-b-implies-sum-j-c-j-x-j – RobPratt Mar 20 '23 at 14:10
3

Not sure if you need all this machinery. I would write:

$$ \begin{aligned} & z=0 \iff 0 \le x+ y \le 1 \\ & z=1 \iff 2 \le x+ y \le 2 \end{aligned} $$

or $$ 2z \le x+y \le 1 + z $$

(Actually Rob's answer is better than this: use $z=xy$ and linearize that using $z\le x$, $z \le y$ and $z\ge x+y-1$. That is tighter. In fact it is so tight that we can relax $z$ to be continuous between 0 and 1).

Erwin Kalvelagen
  • 2,676
  • 1
  • 6
  • 11
  • 1
    This is correct but can be strengthened by disaggregating $2z \le x+y$. – RobPratt Mar 20 '23 at 12:45
  • What did you do with the inequalities to obtain the final one? – tomashauser Mar 20 '23 at 12:51
  • Yes, 100% correct. We should use that. But is it still needed these days? I believe some of this disaggregation is done automatically. We can even write $z=xy$. My usual early morning "bad" formulations often do just as good as the good ones. – Erwin Kalvelagen Mar 20 '23 at 12:51
  • Yes, the strengthened version is often obtained dynamically in cut generation, but it is worth trying both ways. – RobPratt Mar 20 '23 at 13:02
  • I don't understand how you got the final inequality. Did you sum them up and somehow substituted for $z$? – tomashauser Mar 20 '23 at 13:10
  • 1
    No. $z=0 (1) \implies L=0 (2)$ is obviously the same as $L=2z$. Similar, $z=0(1) \implies U= 1(2)$ is the same as $U=1+z$. I can do this before my morning coffee (but then my capabilities stop). – Erwin Kalvelagen Mar 20 '23 at 13:16
  • Ok, now I see it but what makes me a little nervous is that I'm not sure if it's going to be this easy to see with a more complicated expression. I was looking for a more algorithmic and generally appliable process. What you did is that you took two piecewise functions and "guessed" the expression that would fit all the outputs which is fine but I can't be sure that it would be easy to see in a more complicated example. – tomashauser Mar 20 '23 at 13:22
  • Note that indicator constraints can simplify things. Most capable solvers support this. – Erwin Kalvelagen Mar 20 '23 at 13:47
1

You can't let $a_1=1$ and $a_2=0$, because it will enforce $x+y \geq 2$ and $x+y \leq 1$, which is infeasible. That is the connection between the two new variables. So your model is totally correct but maybe not efficient.

xd y
  • 1,186
  • 3
  • 9
  • Nice, I didn't notice that. So I guess now I can use the conversion of constraints into CNF whenever I feel lost. Good to know! Although I'm glad I read other answer as they gave me more insight into the problem. The fact that it is equivalent to linearizing $z = xy$ is just a pure coincidence as I made the example up. – tomashauser Mar 21 '23 at 09:20