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

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?

• If you have no constraints, it is trivially true: the unique optimal solution for both is $x_i=0$ for all $i$. Otherwise, whether it is true depends on your constraints. Oct 17 at 2:55
• A minimal set of constraints is that $\sum_{i}x_{i}= [-1,0, or +1]$ for various selections of $i$. These constraints are a type of node flow balance in a network. Oct 17 at 3:21
• Can you elaborate more on what constraints you consider in general? They are essential for answering this question. Oct 17 at 11:32
• This is DeMorgan's Theorem plus some additional weighting. Oct 19 at 17:56

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.

• Thanks, that's very helpful. I had considered a log transformation, but I didn't recognize that the objective function can be rearranged to be linear in the special case where the variables are binary. Oct 18 at 8:09

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.

• Thanks. I'm not surprised that the equivalence is not true in general. But I am surprised that it appears to be true in my network flow model. Oct 17 at 18:49
• One thing you might want to look into is disciplined convex programming. If you can reformulate using cones ( exponential cone and turning the product in a sum of logarithms) you might that the non integer part of your problems is convex. Network flow is also a problem problem in P which might together might explain the niceties you see. Oct 17 at 18:58