1
$\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 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.

$\endgroup$
  • $\begingroup$ what are your thoughts? $\endgroup$ – LinAlg Nov 9 '18 at 15:09
  • $\begingroup$ 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. $\endgroup$ – STF Nov 9 '18 at 15:15
  • $\begingroup$ Yes, but the problem is incredibly ill-posed, as being $0$ vs not being $0$ basically cannot be distinguished with numerical solvers. $\endgroup$ – Johan Löfberg Nov 9 '18 at 15:21
  • $\begingroup$ 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. $\endgroup$ – Johan Löfberg Nov 9 '18 at 21:26
2
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ Thanks, but that notation is too technical for me. What does it mean "$\delta_1$ implies ..."? What are "$\delta_1,\delta_2,\delta_3$"? $\endgroup$ – STF Nov 9 '18 at 15:25
  • $\begingroup$ added more info $\endgroup$ – Johan Löfberg Nov 9 '18 at 16:08
  • $\begingroup$ 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$. $\endgroup$ – STF Nov 9 '18 at 18:19
  • $\begingroup$ I have added some comments to your answer in my question. Apologies but I have zero knowledge on this topic and you answer looks still very cryptic to me. $\endgroup$ – STF Nov 9 '18 at 19:44
  • $\begingroup$ $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. $\endgroup$ – Johan Löfberg Nov 9 '18 at 21:30

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.