2
$\begingroup$

Consider the following binary variable $x \in \{0,1\}$ and two continuous real variables $y,p \in \mathbb{R}$.

I am trying to model the following conditional equations as constraints:

\begin{cases} -y \le p \le y ,& \text{if } y \ge 0 \\ y \le p \le -y ,& \text{if } y \le 0 \\ p = 0 ,& \text{if } x = 0 \\ \end{cases}

Whats the best way to do so while maintaining a MILP formulation?


The above is a restatement of the problem I attempted to explain below:

If the following two binary variables $x,z \in \{0,1\}$ and continuous real variable $y \in \mathbb{R}$. Whats the best way to linearize the product of the three (i.e. $xyz$) if I am using them in a constraint?

$ xyz \le p \le xyz$

Where $p \in \mathbb{R} $ is another continuous variable. The actual constraint in mind is supposed to maintain the variable $p$ within the same range when the continuous variable $y$ switches signs. For more details, here is the actual expression:

$x((1-z)y + 2yz)) \le p \le x(2(1-z)y + yz)$

$(1-z)y \le zy$

So the idea is that $z$ is 0 when $y$ is positive, and $z$ is 1 when $y$ is negative. $x$ is a switching binary that is turned to $0$ to limit the value of $p$ to 0. Is there a way to linearize this expression?

$\endgroup$
7
  • 1
    $\begingroup$ Welcome to ORSE. Your question needs some clarification. Your first inequality $xyz \le p \le xyz$ is the same as $p = xyz$, and that matches your title, but then you write different nonlinear constraints later. Also, your "$z$ is $1$ when $y$ is positive, and $z$ is $0$ when $y$ is positive" looks like a copy-and-paste error. Finally, the usual linearization requires lower and upper bounds on $y$. $\endgroup$
    – RobPratt
    Mar 21, 2023 at 15:00
  • $\begingroup$ If $x=1$ and $z=1,$ your inequality on $p$ becomes $2y \le p \le y.$ Since $z=1 \implies y\ge 0,$ that will force $y=0=p.$ If $x=1$ and $z=0,$ the inequality becomes $y \le p \le 2y.$ Since $z=0 \implies y\le 0,$ that will again force $y=0=p.$ I'm guessing that is not what you want. $\endgroup$
    – prubin
    Mar 21, 2023 at 15:41
  • $\begingroup$ @RobPratt Thank you. You are correct regarding the copy-and-paste error it was a typo, and I fixed it. In the latter expressions, I have $xyz$ multiplication occurring a couple of times on each side, and I assumed the linearization of such an expression would be similar. and I started with $xyz \le p \le xyz$ for brevity. $\endgroup$
    – Ahmed
    Mar 21, 2023 at 21:41
  • $\begingroup$ It looks like your correction is backwards. Please see the comment from @prubin. It might help to just write the logical conditions you want and leave the algebraic expressions for the community to provide. $\endgroup$
    – RobPratt
    Mar 21, 2023 at 22:23
  • $\begingroup$ Your rewritten question looks better. I see three logical implications that you want to enforce, but I don’t think you want $f(x)=$. $\endgroup$
    – RobPratt
    Mar 21, 2023 at 23:19

3 Answers 3

5
$\begingroup$

More compactly, you want to enforce $$-x|y| \le p \le x|y|$$ Assume $L \le y \le U$ for some constants $L\le 0$ and $U\ge 0$, and let $M=\max(-L,U)$. Introduce continuous decision variable $w$ (to represent $|y|$) and binary decision variable $z$, and impose linear constraints \begin{align} -Mx \le p &\le Mx \tag1\label1 \\ -w \le p &\le w \tag2\label2 \\ -w \le y &\le w \tag3\label3 \\ w - y &\le (M-L) z \tag4\label4 \\ w + y &\le (M+U)(1-z) \tag5\label5 \end{align} Constraint \eqref{1} enforces $x=0 \implies p=0$. Constraint \eqref{4} enforces $z=0 \implies w\le y$ (hence $w=y$). Constraint \eqref{5} enforces $z=1 \implies w\le -y$ (hence $w=-y$).

$\endgroup$
1
  • $\begingroup$ Thank you so much. This worked just right! $\endgroup$
    – Ahmed
    Mar 22, 2023 at 19:41
1
$\begingroup$

By updating the question, the mentioned conditional inequalities can be linearized by introducing new indicator variables, $z_i$, for each part and coupling those to make linearization. For example the first part, $\{-y \leq p \leq y , \ \text{if } y \ge 0\}$, would be:

$$ z_1 = 1 \iff (y \geq 0) $$ $$ z_2 = 1 \iff (- y - p \leq 0)$$ $$ z_3 = 1 \iff (p - y \leq 0)$$ $$ z_4 = 1 \iff (z_2 + z_3 = 2)$$ $$ z_1 = 1 \implies z_4 = 1$$

and the same should be held for the rest inequalities.

$\endgroup$
0
$\begingroup$

Basically you are trying the following: $ p \le xp_{max}$: ensures $p=0$ if $x=0$, else $p$ is free,
$ p_{max}$ is upper bound of $p$
And
$ y(2z-1) \le p \le y(1-2z) $

For $ y, z$ switching I think you already have
$ y \le y_{max}(1-z)$
$-y \le y_{max}z$

To linearize $ yz$ you can try with a new continuous variable $w$ in same domain as $y$ with following standard constraints (link)
$ w \le M(1-z)$
$ -w \le M(1-z)$
$ y-Mz \le w$
$ w \le y + Mz$

The above 4 constraints forces $w=y$ if $z=0$ or $0 \le y$, else 0

So $ 2w-y \le p \le y-2w$

$\endgroup$
2
  • $\begingroup$ If $z=0,$ the first two constraints on $w$ give you $-M \le w \le 0$ and the next two constraints give you $\vert y - w \vert \le M,$ which does not tell you much about $w.$ In particular, for $z=0$ you have neither $w = 0$ nor $w=y.$ $\endgroup$
    – prubin
    Mar 21, 2023 at 15:34
  • $\begingroup$ Thanks, I have corrected it. $ w=0$ if $ z=0$ $\endgroup$ Mar 21, 2023 at 15:55

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.