How to make a non-linear problem linear?

Question

I have the following constraint which is the product of multiple binary variables: $1- \prod_i^n (1-(c_i x_i)) >= T$

where $x_i$ is a binary variable, $c_i$ is a constant and $T$ is a constant too. Are there any way to make this problem linear?

Answer 1

"If $x_i = 1$ multiply by $1-c_i$, otherwise multiply by $1$." $$\prod_i(1-c_ix_i) = \prod_i (1-c_i)^{x_i}$$

So $$\begin{align}1-\prod_i(1-c_ix_i) \geq T \Leftrightarrow 1-T &\geq \prod_i(1-c_ix_i) \\ &= \prod_i (1-c_i)^{x_i} \end{align}$$

$$\Leftrightarrow\log(1-T) \geq \sum_i x_i \log(1-c_i)$$

So the constraint becomes

$$T' \geq \sum_i x_i c_i'$$ where $T' = \log(1-T)$, $c_i' = \log(1-c_i)$.

Answer 2

From $1- \prod_i^n (1-(c_i x_i)) >= T$ we get $\prod_i^n (1-(c_i x_i)) \le 1-T$.

Taking logs, $\sum_i^n \log(1-(c_i x_i)) \le \log(1-T)$.

If this isn't good enough, you can approximate with $-\ln(1-x) =x+x^2/2+... > x $, so $\ln(1-x) < -x$.