Rewrite $[p_1(x)\geq 0 \text{ and } p_2(x)\geq 0] \Rightarrow q(x)\geq 0$, $[-p_1(x)\geq 0 \text{ and } -p_2(x)\geq 0] \Rightarrow q(x)\geq 0$

68 Views Asked by At

I am trying to reformulate an optimisation problem with unknown $x$ into a mixed-integer program. In this respect, I would like your help to rewrite the following constraints $$ \begin{cases} p_1(x)\geq 0 \text{ and } p_2(x)\geq 0 \Rightarrow q(x)\geq 0\\ -p_1(x)\geq 0 \text{ and } -p_2(x)\geq 0 \Rightarrow q(x)\geq 0\\ \end{cases} $$ where $p_1:\mathbb{R}^k\rightarrow \mathbb{R}$, $p_2:\mathbb{R}^k\rightarrow \mathbb{R}$, and $q:\mathbb{R}^k\rightarrow \mathbb{R}$, $p_1, p_2, q$ linear in $x$.

using the big-M modelling approach. These questions here and here are related.


If I had only to consider $$ \Big[ p_1(x)\geq 0 \text{ and } p_2(x)\geq 0 \Big] \Rightarrow q(x)\geq 0\\ $$ I think the correct procedure would have been to model the following implications with $\delta_1, \Delta_{1,1}, \Delta_{1,2}$ binary $$ \begin{cases} \Delta_{1,1}=1\\ \Delta_{1,2}=1 \end{cases} \Rightarrow \delta_1=1 \Rightarrow \begin{cases} p_1(x)\geq 0\\ p_2(x)\geq 0\\ q(x)\geq 0 \end{cases} $$ leading to $$ \begin{cases} p_1(x)+\epsilon\leq M_1*\Delta_{1,1}\\ p_2(x)+\epsilon\leq M_1*\Delta_{2,1}\\ \delta_1\geq 1+\Delta_{1,1}+\Delta_{2,1}-2\\ q(x)\geq -M_1(1-\delta_1)\\ \end{cases} $$ where $\epsilon$ is added to activate $q(x)\geq -M_1(1-\delta_1)$ also when $p_1(x)=p_2(x)=0$.

I have doubts on what happens when instead we consider

$$ \Big[p_1(x)\geq 0 \text{ and } p_2(x)\geq 0 \Big] \text{ or } \Big[-p_1(x)\geq 0 \text{ and } -p_2(x)\geq 0 \Big]\Rightarrow q(x)\geq 0\\ $$

Specifically, I don't know whether we have to double the number of auxiliary binary variables (option 1 below) or we can keep the same number of auxiliary binary variables (option 2 below).


Option 1 $$ \begin{cases} p_1(x)+\epsilon\leq M_1*\Delta_{1,1}\\ p_2(x)+\epsilon\leq M_1*\Delta_{2,1}\\ \delta_1\geq 1+\Delta_{1,1}+\Delta_{2,1}-2\\ q(x)\geq -M_1(1-\delta_1)\\ -------------\\ \color{blue}{-p_1(x)+\epsilon\leq M_2*\Delta_{1,2}}\\ \color{blue}{-p_2(x)+\epsilon\leq M_2*\Delta_{2,2}}\\ \color{blue}{\delta_2\geq 1+\Delta_{1,2}+\Delta_{2,2}-2}\\ \color{blue}{q(x)\geq -M_2(1-\delta_2)}\\ -------------\\ \delta_1\in \{0,1\}\\ \delta_2\in \{0,1\}\\ \Delta_{1,1}\in \{0,1\}\\ \Delta_{2,1}\in \{0,1\}\\ \Delta_{1,2}\in \{0,1\}\\ \Delta_{2,2}\in \{0,1\}\\ \end{cases} $$

Option 2

$$ \begin{cases} p_1(x)+\epsilon\leq M_1*\Delta_{1,1}\\ p_2(x)+\epsilon\leq M_1*\Delta_{2,1}\\ \delta_1\geq 1+\Delta_{1,1}+\Delta_{2,1}-2\\ q(x)\geq -M_1(1-\delta_1)\\ -------------\\ q(x)\geq -M_1(1-\color{blue}{(1-\delta_1)})\\ -------------\\ \delta_1\in \{0,1\}\\ \Delta_{1,1}\in \{0,1\}\\ \Delta_{2,1}\in \{0,1\}\\ \end{cases} $$

1

There are 1 best solutions below

0
On BEST ANSWER

With option 2, if $p_i$ is negative, $\Delta_{i,1}$ could be anything. Therefore, you never force $\delta_i$ to take the value 1. Moreover, option 2 has the constraints $q(x) \geq -M_1(1-\delta_1)$ and $q(x) \geq -M_1 \delta_1$, so you always force $q(x) \geq 0$, independent of the value taken by $\delta_1$.

Option 1 is a correct reformulation.