# Rewrite the constraint $p(x)=0 \Rightarrow q(x)=0$ in an optimization problem

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 constraint $$p(x)=0 \Rightarrow q(x)=0$$ where $$p:\mathbb{R}^k\rightarrow \mathbb{R}$$ and $$q:\mathbb{R}^k\rightarrow [-1,1]^m$$, $$p$$ and $$q$$ linear in $$x$$.

using the big-M modelling approach (as here for example).

Any suggestion?

I'm trying to understand the answer below. My understanding of the answer is that $$p(x)=0 \Rightarrow q(x)=0$$ is equivalent to $$\begin{cases} q(x)\geq -M(1-\delta_2)\\ q(x)\leq M(1-\delta_2)\\ -----------\\ p(x)\leq M(1-\delta_1)-\epsilon\\ -----------\\ p(x)\leq M(1-\delta_2)+\epsilon\\ p(x)\geq -M(1-\delta_2)-\epsilon\\ -----------\\ p(x)\geq -M(1-\delta_3)+\epsilon\\ -----------\\ \delta_1+\delta_2+\delta_3=1 \end{cases}$$

If this is the correct understanding of the answer, I have doubts:

(1) $$q(x)\geq -M(1-\delta_2), q(x)\leq M(1-\delta_2)$$ forces $$q(x)=0$$ when $$\delta_2=1$$

(2) $$p(x)\leq M(1-\delta_1)-\epsilon$$ sets $$\delta_1=1$$ when $$p(x)+\epsilon>0$$ (so that $$\delta_2=\delta_3=1$$ and hence $$q(x)$$ is not activated) and leaves $$\delta_1$$ free otherwise

(3) $$p(x)\geq -M(1-\delta_3)+\epsilon$$ sets $$\delta_3=0$$ when $$p(x)-\epsilon<0$$ (so that $$\delta_2=1$$ or $$\delta_1=1$$ and hence $$q(x)$$ may be activated) and leaves $$\delta_3$$ free otherwise

(4) $$p(x)\leq M(1-\delta_2)+\epsilon$$ sets $$\delta_2=0$$ when $$p(x)-\epsilon>0$$ (so that $$\delta_1=1$$ or $$\delta_3=1$$ and hence $$q(x)$$ is not activated) and leaves $$\delta_2$$ free otherwise

(5) $$p(x)\geq -M(1-\delta_2)-\epsilon$$ sets $$\delta_2=0$$ when $$p(x)+\epsilon<0$$ (so that $$\delta_1=1$$ or $$\delta_3=1$$ and hence $$q(x)$$ is not activated) and leaves $$\delta_2$$ free otherwise.

What is the correct way of reading all this? I can't see the closure of the logic.

• what are your thoughts? – LinAlg Nov 9 '18 at 15:09
• I'm confused. Firstly, can we do that? I know almost nothing about big-M modelling but I have doubts on whether we can transform equalities. – STF Nov 9 '18 at 15:15
• Yes, but the problem is incredibly ill-posed, as being $0$ vs not being $0$ basically cannot be distinguished with numerical solvers. – Johan Löfberg Nov 9 '18 at 15:21
• Don't over-complicate the analysis. The disjoint $\delta$ variables with associated regions force $p$ to be in some region, and if $p$ is in a region, the corresponding $\delta$ has to be true because if it wasn't some other $\delta$ would be true, which would force $p$ to be in another region, which would be a contradiction. If $\delta_2$ is true, $q$ is forced to be 0. – Johan Löfberg Nov 9 '18 at 21:26

One simple way is by subdividing everything into disjoint cases. Introduce three binaries $$\delta_i$$ and you have

$$\delta_1=1 \Rightarrow p\leq -\epsilon$$

$$\delta_2=1 \Rightarrow -\epsilon \leq p\leq \epsilon, q = 0$$

$$\delta_3=1 \Rightarrow p\geq \epsilon$$

$$\delta_1+\delta_2 + \delta_3 = 1$$

The big-M model of an implication between a binary $$\delta$$ and an inequality $$g(x)\geq 0$$ is $$g(x)\geq -M(1-\delta)$$ where $$M$$ is the infamous big-M constant (which should be called as-small-as-possible-but-sufficiently-large, i.e. it should be so large that $$g(x)\geq -M$$ is redundant)

• Thanks, but that notation is too technical for me. What does it mean "$\delta_1$ implies ..."? What are "$\delta_1,\delta_2,\delta_3$"? – STF Nov 9 '18 at 15:25
• I have 2 other doubts: 1) suppose that I have many implications of the type above to rewrite within my constrained optimization problem: does $M$ have to be the same across all the transformations? 2) you wrote $M$ should be chosen such that $g(x)\geq -M$ is redundant: my understanding is that $p(x)\geq 0 \Rightarrow q(x)\geq 0$ is rewritten as $p(x)+\epsilon \leq M\delta$ and $q(x)\geq -M(1-\delta)$ with $\epsilon>0$ very small; in this sense, $M$ should be chosen such that $q(x)\geq -M$ is redundant AND $p(x)+\epsilon \leq M$ is satisfied for $p(x)>0$. – STF Nov 9 '18 at 18:19
• $M$ should be picked as tight as possible for every single constraint. The $\epsilon$ variable is only included to deal with the fact that you cannot really talk about a variables being 0, so we look at $-\epsilon \leq p \leq \epsilon$ instead, where that tolerance is something you will have to eperiment with in practice, to make it relevant for your problem, and reasonable for the solver. – Johan Löfberg Nov 9 '18 at 21:30