3
$\begingroup$

I have an optimization problem and I want to convert the following if conditions to linear constraints:

If $(y_1 > U_1)$ and $(m_1)$ and $(E_1)$ then $x_1=1$

If $(y_2 > U_2)$ and $(m_2)$ and $(E_2)$ then $x_2=1$

If $(y_1-U_1) \geq (y_2-U_2)$ and $(x_1)$ then $X_1=1$ elseif $(x_2)$ then $X_2=1$

Where $x_1, x_2, X_1, X_2 \in \{0,1\}$ are binary variables, $y_1,y_2$ are positive real decision variables, $m_1,m_2,E_1,E_2 \in \{0,1\}$ are binary parameters and $U_1, U_2$ are parameters.

Can anybody help me to convert these conditions to linear constraints?

Improve this question
$\endgroup$
2
  • $\begingroup$ What type of variables are $y_1$ and $y_2$? $\endgroup$
    – RobPratt
    Mar 30, 2022 at 22:08
  • $\begingroup$ @RobPratt $y_1, y_2$ are positive real variables. $\endgroup$
    – hamta
    Mar 30, 2022 at 22:17

3 Answers 3

Reset to default
4
$\begingroup$

You need only one additional binary variable $z$, which will indicate whether $y_1 - U_1 \ge y_2 - U_2$, with the usual caveat that the equality case can correspond to either value of $z$.

You can use indicator constraints: \begin{align} x_1 = 0 &\implies y_1 \le U_1 &&\text{if $m_1 = 1$ and $E_1 = 1$} \\ x_2 = 0 &\implies y_2 \le U_2 &&\text{if $m_2 = 1$ and $E_2 = 1$} \\ z = 1 &\implies y_1 - U_1 \ge y_2 - U_2 \\ z = 0 &\implies y_1 - U_1 \le y_2 - U_2 \\ X_1 = 0 &\implies z + x_1 \le 1 \\ X_2 = 0 &\implies z \ge x_2 \\ X_2 = 0 &\implies x_1 \ge x_2 \end{align}

Alternatively, use big-M constraints. For $i\in\{1,2\}$, let $\bar{y}_i$ be an upper bound on $y_i$ and impose: \begin{align} y_1 - U_1 &\le (\bar{y}_1 - U_1) x_1 &&\text{if $m_1 = 1$ and $E_1 = 1$} \\ y_2 - U_2 &\le (\bar{y}_2 - U_2) x_2 &&\text{if $m_2 = 1$ and $E_2 = 1$} \\ (y_2 - U_2) - (y_1 - U_1) &\le (\bar{y}_2 + U_1 - U_2)(1-z) \\ (y_1 - U_1) - (y_2 - U_2) &\le (\bar{y}_1 - U_1 + U_2)z \\ z + x_1 - 1 &\le X_1 \\ x_2 -z &\le X_2 \\ x_2 - x_1 &\le X_2 \end{align}

Improve this answer
$\endgroup$
3
  • $\begingroup$ Many thanks for your reply. In order to embed if $m_1=1$ and $E_1=1$ in the linear constraints, Is it correct if I write: $k(y_1-U_1) \leq (\bar{y}_1-U_1)x_1$ where k=$m_1 E_1$? If it is not correct, how can I embed it? $\endgroup$
    – hamta
    Mar 31, 2022 at 6:48
  • $\begingroup$ If you really want to do that, it is better to multiply both sides of the constraint by $k$, but a better practice is to just omit the constraint if the condition is not satisfied. $\endgroup$
    – RobPratt
    Mar 31, 2022 at 12:33
  • $\begingroup$ Yes, you are right. Thank you so much for your help!! Your reply was very helpful for me!! $\endgroup$
    – hamta
    Mar 31, 2022 at 13:14
3
$\begingroup$

Define four binary variables $t_1^+$, $t_1^-$, $t_2^+$, $t_2^-$ and also define $s_1=m_1E_1$ and $s_2=m_2E_2$. Obviously $s_1$ and $s_2$ are binary parameters. The following constraints set ($M$ is a large positive number) will do the logical constraints that you have:

$\left\{ \begin{array}{rcl} t_1^+ + t_1^-= 1\\ -t_1^-M<y_1-U_1<t_1^+M\\ (1-t_1^-)s_1<x_1<t_1^+s_1\\ \end{array} \right.$

$\left\{ \begin{array}{rcl} t_2^+ + t_2^-= 1\\ -t_2^-M<y_2-U_2<t_2^+M\\ (1-t_2^-)s_2<x_2<t_2^+s_2\\ \end{array} \right.$

These sets of constraints will model the first two constraints in the question. The last condition can be captured using the following set of constraints, again here two more binary variables $t_3^+$, $t_3^-$ need to be defined:

$\left\{ \begin{array}{rcl} t_3^+ + t_3^-= 1\\ -t_3^-M<(y_1-y_2)-(U_1-U_2)<t_3^+M\\ X_1\leq(1-t_3^+)+x_1\\ X_2\leq(1-t_3^+)+x_2\\ X_1\leq t_3^+\\ X_2\leq t_3^+\\ \end{array} \right.$

Improve this answer
$\endgroup$
2
$\begingroup$

I implemented both the suggested solutions above but none of them were correct. I solved it myself and the correct solution is as follows ($s_1=m_1E_1, s_1=m_1E_1$):

$ -(1-t_1)M \leq y_1-U_1 \leq t_1 M \\ -(1-t_2)M \leq y_2-U_2 \leq t_2 M \\ x_1 \leq t_1s_1 \\ x_2 \leq t_2s_2 \\ -(1-z_1)M\leq (y_1-y_2)-(U_1-U_2) \leq z_1M \\ -(1-z_2)M\leq (y_2-y_1)-(U_2-U_1) \leq z_2M \\ X_1 \leq (1-z_1)+x_1 \\ X_2 \leq (1-z_2)+x_2 \\ X_1 \leq z_1 \\ X_2 \leq z_2 $

Hope it is useful for the other guys.

Improve this answer
$\endgroup$
13
  • $\begingroup$ What is incorrect about them? $\endgroup$
    – RobPratt
    Apr 2, 2022 at 13:11
  • $\begingroup$ @RobPratt Thanks for your comment. The notation of my main problem was different and I made some mistake about the notation, I edited the solution. In your solution, you need two binary variables ($z_1, z_2$) to compare $y_1-U_1$ with $y_2-U_2$ $\endgroup$
    – hamta
    Apr 2, 2022 at 14:12
  • $\begingroup$ @RobPratt Moreover, in the case that $y_1<U_1$ (which means $x_1=0$) and $z_1=0$, the result must be: $X_1=0$ while in your solution $X_1$ can be both 0 and 1. So we need more binary variables. $\endgroup$
    – hamta
    Apr 2, 2022 at 14:20
  • $\begingroup$ It looks like from your answer and comments that you have additional requirements that are not in your question. Nothing in your question forces $x_i=0$ or $X_i=0$. Maybe you meant to also enforce the converse of some requirements? $\endgroup$
    – RobPratt
    Apr 2, 2022 at 15:55
  • 1
    $\begingroup$ No, the correct formulation of $X_i =1 \iff (z_i =1 \land x_i = 1)$ is $X_i \le z_i, X_i \le x_i, X_i \ge z_i + x_i - 1$. What you have instead allows $(X_i,z_i,x_i)=(0,1,1)$, for example. $\endgroup$
    – RobPratt
    Apr 2, 2022 at 17:04

Your Answer

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