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).

  • $\begingroup$ have you tried branch and bound? $\endgroup$
    – tortue
    Jan 22, 2019 at 6:56


You must log in to answer this question.