Nonlinear Optimization with Gurobi
Hello all,
I am trying to solve the following nonlinear problem to minimize for y
 y = sum(x_1*b_1,x_2*b_2,...,x_n*b_n) / sum(x_1*c_1,x_2*c_2,...,x_n*c_n)
 x_i are binary variable, b_i/c_i are scalars.
Is there a product of Gurobi to solve for this problem?
Thanks,

Hi,
We can cast this problem as a nonconvex mixedinteger 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, k1, k+1, \ldots, n \). This should be straightforward to prove.
I hope this helps. Thanks!
Eli
Please sign in to leave a comment.
Comments
1 comment