Non-linear Optimization with Gurobi

Comments

1 comment

  • Eli Towle

    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

    1
    Comment actions Permalink

Please sign in to leave a comment.

Powered by Zendesk