I was wondering if the following nonlinear integer programming problem is NP-hard or not.
$$\max_{x_i \in \{0,1\}} \frac{\sum_{i=1}^{n}a_i x_i}{\sqrt{\sum_{i=1}^{n}b_i x_i}}$$
such that $\sum_{i=1}^{n} x_i = K, x_i \in \{0,1\}, ~\forall i \in \{1,\dots,n\}$
where $a_i \in \mathbb{R}$, $b_i \in \mathbb{R}_{+}$, $K > 0$.
It is NP-hard. Below is a reduction from the partition problem.
The partition problem asks for a list of positive integers $x_1,\dots,x_n$ whether it can be partitioned into two subsets with equal sum.
Say we want to solve the partition problem on $u_1,\dots,u_n$. Define the list $v$ of size $2n$ by $v_i = 2u_i / (\sum_{i=1}^n u_i)-1/n$ for $1 \le i \le n$ and $v_i = -1/n$ for $n < i \le 2n$. The partition problem is then equivalent to checking whether there is a subset of $v$ with size $n$ and sum zero.
We can then take $K = n$, $a_i = -(1+v_i/4)/n$ and $b_i = (1+v_i/2)/n$ for $1 \le i \le 2n$. Note $-1 < v_i < 2$ so that $a_i < 0 < b_i$. Then your optimization objective is $-1$ if and only if such a subset exists.
To see this, consider some $x$ with $\sum_{i=1}^n x_i = K = n$. Let $A = -\sum_{i=1}^n a_i x_i = 1+\frac{1}{4n}\sum_{i=1}^n v_i x_i$ and $B = 2\sum_{i=1}^n b_i x_i = 1+\frac{1}{2n}\sum_{i=1}^n v_i x_i$. Note that $A = B = 1$ if and only if $x$ selects a subset of $v$ with size $n$ and sum zero. Additionally, note $2A=B+1$. The objective is to maximize $-A/\sqrt B$. It is straightforward to check that $-A/\sqrt B \ge -1$ and $2A=B+1$ has only one solution $A = B = 1$.
Hence, your problem is at least as hard as the partition problem, which is NP-hard.
