Tuesday, October 18, 2016

MIP Modeling: if constraint

From http://cs.stackexchange.com/questions/51025/cast-to-boolean-for-integer-linear-programming/51089#51089

could you please explain the your logic with binary variable delta, for more general case, for instance, if y={a: x>0, b: x<0}.

If we assume \(y\) can be either \(a\) or \(b\) (constants) when \(x=0\), and \(x \in [L,U]\)  (with \(L<0\) and \(U>0\)) then we can write

\[\begin{matrix}
y = \begin{cases}a&x\ge 0\\b&x\le 0 \end{cases}
& \Longrightarrow
& \boxed{\begin{align}&L(1-\delta) \le x \le U \delta\\&y=a\delta + b (1-\delta)\\ &\delta \in \{0,1\} \end{align}}
\end{matrix} \]

I am not sure if the left part is formulated mathematically correctly. May be I should say:

\[y = \begin{cases} a&x> 0\\
                   b&x< 0 \\
                   a \text{ or } b & x=0
\end{cases}\]

If we want to exclude \(x=0\) then we need to add some small numbers:

\[\begin{matrix}
y = \begin{cases}a&x> 0\\b&x < 0 \end{cases}
& \Longrightarrow
& \boxed{\begin{align}&\varepsilon + (L-\varepsilon)(1-\delta) \le x \le –\varepsilon +(U+\varepsilon)\delta\\&y=a\delta + b (1-\delta)\\&\delta \in \{0,1\}\\
&\varepsilon=0.001\end{align}}
\end{matrix} \]
Of course in many cases we can approximate \(U\approx U+\varepsilon\) (similar for \(L\)), I was a bit precise here.

If \(a\) and \(b\) are variables (instead of constants) things become somewhat more complicated. I believe the following is correct:

\[\boxed{\begin{align}
&\varepsilon + (L-\varepsilon)(1-\delta) \le x \le –\varepsilon +(U+\varepsilon)\delta\\
&a+M_1(1-\delta)\le y \le a+ M_2(1-\delta)\\
&b+M_3\delta\le y \le b+M_4\delta\\
&\delta \in \{0,1\}\\
&\varepsilon=0.001\\
&M_1 = b^{LO}-a^{UP}\\
&M_2 = b^{UP}-a^{LO}\\
&M_3 = a^{LO}-b^{UP}\\
&M_4 = a^{UP}-b^{LO}
\end{align}}\]

I used here \(a \in [a^{LO},a^{UP}]\) and \(b \in [b^{LO},b^{UP}]\).