2
$\begingroup$

I am trying to linearize the following logical expression without using any auxiliary binary variables, and I am interested in knowing if there is a way to do that.

$$ (x = y) \implies (b = 1) $$

where $x$, $y$ are positive variables with a known $LB$ and $UB$, and $b$ is binary. It can be easily rewritten as:

$$ (b = 0) \implies ((x \geq y + \epsilon) \ \lor \ (x \leq y - \epsilon)) \quad (1)$$ $$ (b = 0) \implies (z_1 \implies (x \geq y + \epsilon) \ \lor \ z_2 \implies (x \leq y - \epsilon)) \quad (2)$$ $$ \{(z_1 + z_2 + b \geq 1), (x \geq (y+\epsilon)-M(1-z_1)), (x \leq (y-\epsilon)+M(1-z_2)) \} \quad (3)$$

As far as I know, the DNF in the RHS of the $(1)$ needs auxiliary binary variables to linearize, and I want to know if it is possible to use only $b$ to linearize that.

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ you can eliminate one of the $z$ variables as $z_1+z_2\le 1$ holds. $\endgroup$ Commented Apr 24 at 6:52
  • $\begingroup$ @Kuifje, Thanks. I guess it would do in the pre-solving phase in the solver automatically. Do you think it would be possible to use only $b$ to linearize? $\endgroup$ Commented Apr 24 at 7:26
  • $\begingroup$ What does "Iff(...)" mean here? Do you mean $(x=y) \iff (b=1)?$ $\endgroup$ Commented Apr 24 at 16:06
  • $\begingroup$ Dear @prubin, I mean $(x=y) \implies (b=1)$. $\endgroup$ Commented Apr 24 at 16:10
  • 1
    $\begingroup$ For clarity, I think you should remove the "Iff" part. $\endgroup$ Commented Apr 24 at 19:41

1 Answer 1

Reset to default
1
$\begingroup$

For a nonconvex quadratic MIP approach with no additional binary variables, $(b = 0) \implies (x \neq y)$ can be modeled as \[(x-y)^2 \ge \epsilon^2 (1-b)\] where $\epsilon > 0$ is the tolerance for claiming $|x-y| > 0.$

(Personally, I would go with the extra binary variables and keep things linear.)

Improve this answer
$\endgroup$
4
  • $\begingroup$ Dear @prubin, Thanks for your answer. It is an interesting approach. It seems there is NO way to linearize the logical expression with only the binary variable $b$. However, as per the problem is non-convex, it would need the linearization method if I want to apply it in the modeling layer. May I have your insight? $\endgroup$ Commented Apr 26 at 7:51
  • $\begingroup$ Sorry, I do not understand what you are asking. $\endgroup$ Commented Apr 26 at 16:21
  • $\begingroup$ Dear @prubin, I mean it seems we cannot linearize the logical expression as a linear problem only by using $b$. $\endgroup$ Commented Apr 26 at 19:52
  • 1
    $\begingroup$ I do not know of a way to do it (which is not the same as saying it is impossible ,.. but I suspect it is impossible). $\endgroup$ Commented Apr 26 at 21:30

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.