3
$\begingroup$

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?

$\endgroup$

3 Answers 3

3
$\begingroup$

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

$\endgroup$
8
  • 1
    $\begingroup$ This is correct but can be strengthened by disaggregating $2z \le x+y$. $\endgroup$
    – RobPratt
    Mar 20, 2023 at 12:45
  • $\begingroup$ What did you do with the inequalities to obtain the final one? $\endgroup$ Mar 20, 2023 at 12:51
  • $\begingroup$ 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. $\endgroup$ Mar 20, 2023 at 12:51
  • $\begingroup$ Yes, the strengthened version is often obtained dynamically in cut generation, but it is worth trying both ways. $\endgroup$
    – RobPratt
    Mar 20, 2023 at 13:02
  • 1
    $\begingroup$ 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). $\endgroup$ Mar 20, 2023 at 13:16
4
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$ Mar 20, 2023 at 12:55
  • $\begingroup$ 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? $\endgroup$
    – RobPratt
    Mar 20, 2023 at 13:05
  • $\begingroup$ 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. $\endgroup$ Mar 20, 2023 at 13:07
  • $\begingroup$ OK, please open a separate question for that. $\endgroup$
    – RobPratt
    Mar 20, 2023 at 13:08
  • 2
    $\begingroup$ See my new question and answer here: or.stackexchange.com/questions/10172/… $\endgroup$
    – RobPratt
    Mar 20, 2023 at 14:10
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Mar 21, 2023 at 9:20

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .