1 comment

Hi,

We can cast this problem as a non-convex mixed-integer quadratic program by introducing a few additional variables. I'll assume all of the $$b_i$$ and $$c_i$$ are strictly positive.

If all of the $$x_i$$ are $$0$$, then $$y$$ evaluates to an undefined value of $$\frac{0}{0}$$. So, we should make sure that at least one of the $$x_i$$ is $$1$$. We can write this problem as follows:

\begin{alignat}{2} \min_{u,v,x,y} && y \quad & \\ \textrm{s.t.} && u &= \sum_{i = 1}^n b_i x_i \\ && v &= \sum_{i = 1}^n c_i x_i \\ && yv &= u \\ && \sum_{i = 1}^n x_i &\geq 1 \\ && x &\in \{0,1\}^n \end{alignat}

That said, if all of the $$b_i$$ and $$c_i$$ are strictly positive and you have no additional constraints, then we can construct an optimal solution to this problem by setting $$x_k = 1$$, where $$k \in \arg\min_{i = 1, \ldots, n} b_i / c_i$$, and $$x_i = 0$$ for all $$i = 1, \ldots, k-1, k+1, \ldots, n$$. This should be straightforward to prove.

I hope this helps. Thanks!

Eli