Product of weighted binary variables equivalent to sum of weighted binary variables?

Question

I'm working on an optimization problem with a non-linear objective function of the form $$\max\prod_{i=1}^{n}(1-a_{i}x_{i}).$$

The objective function represents the combined probability of success for a series of independent stochastic trials.

I assert that this is equivalent to the linear objective function $$\min \sum_{i=1}^{n}a_{i}x_{i}$$ where

• $a_{i}$ are constant weights (failure rate) in the range $(0,1]$ (the assertion breaks down if any $a_{i}=0$);

• $x_{i}$ are binary variables.

The assertion is true for the small set of cases that I've tested. That is, the optimal set of $x_{i}$ variables is the same for both forms of the objective function.

But is the assertion true in general? Why / why not?

Answer 1

It is not true in general, but you can make it work with

$$\max\sum_{i=1}^{n}\log(1-a_{i})x_{i}$$

Since $\log$ is monotonic, your objective is equivalent to $$\max\log\left(\prod_{i=1}^{n}(1-a_{i}x_{i})\right)$$ which becomes $$\max\sum_{i=1}^{n}\log(1-a_{i}x_{i})$$ and finally, since $x_i$ is binary and $\log(1) = 0$ $$\max\sum_{i=1}^{n}\log(1-a_{i})x_{i}$$

I guess that your $a_i$ are quite small, in which case $\log(1 + a_i) \approx a_i$, and the objective you tried is a good approximation.

Answer 2

No it's not true in general.

Consider $n=4$ with $a=(0.3,0.7,0.5,0.5)$ under the constraint $(x_1 \wedge x_2) \text{xor}(x_3\wedge x_4)$ which can be expressed in terms of MILP by introducing helper binary variables. For the linear term, $(1,1,0,0)$ and $(0,0,1,1)$ are equally good optima while for the product term they obviously differ in quality, meaning solving the MILP can produce a sub-optimal result.