0
$\begingroup$

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} $$

$\endgroup$
  • $\begingroup$ could you indicate the implications you have modeled? $\endgroup$ – LinAlg Nov 10 '18 at 22:50
  • $\begingroup$ @LinAlg Thanks: I have added some clarifications (I hope in line with your request). $\endgroup$ – STF Nov 11 '18 at 17:38
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.