# Optimization of nonlinear $f(x)$ where $x$ is a vector of binary variables

I'd like to find a solution (potentially approximate) to the problem

$$\max_{x_{i,j}} \sum_{k=0}^K\left[ 1 - \prod_{i=1}^{I} \left(1 - \prod_{j=1}^{J}(1-b_{k,i,j} \, x_{i,j}) \right)\right]$$

where the parameters, $$b_{k,i,j}$$, are continuous on the interval $$[0,1]$$ and the variables which we are optimizing over $$x_{i,j}$$ can only take values 0 or 1.

It is a nonlinear, integer-valued, optimization problem. In addition the problem is quite big, I'm thinking of problems where $$K$$ = 1000, $$I$$ = 100,000, and $$J$$ = 20.

My thought for a solution method would be to first try a greedy algorithm, which I would then use to seed a genetic algorithm. But that method won't be able to put bounds on how sub-optimal the answer is. Given the structure of the problem, I thought it might be worth seeing if there is any mathematics that can be used to find a solution efficiently (or provide bounds on how sub-optimal a solution might be using a particular algorithm).

• have you tried branch and bound? Jan 22, 2019 at 6:56