Computational complexity of maximizing sum of rational functions I have a optimization problem:

$$\max_z\ \sum_{i=1}^n \frac{W_i}{D_i - z_i} \quad \text{s.t.}\ \sum_{i=1}^n z_i \leq k, z_i \in [0,k],$$ where each $W_i$, $D_i$ are constants and $z_i$ are integer variables. Assume each $D_i &gt;k$.

The optimal solution obviously satisfies $\sum_{i=1}^n z_i =k$.
But it seems there is no efficient way to get the optimum other than trying out all partitions.

Also, I know the above problem can be formulated as linear integer programming.

Is there any hint of proving the hardness of the above problem?
Your problem can be solved in polynomial time.

Suppose $n-2$ variables (without loss of generality, say $z_3,\ldots,z_n$) are fixed, then the objective becomes maximizing $$\frac{W_1}{D_1-z_1}+\frac{W_2}{D_2-z_2}$$ where $z_1+z_2\le k-(z_3+\cdots+z_n):=K$. Let $$f(z)=\frac{W_1}{D_1-z}+\frac{W_2}{D_2-(K-z)}, 0\le z\le K,$$
then
$$f''(z)=\frac{2W_1}{(D_1-z)^3}+\frac{2W_2}{(D_2-K+z)^3}\ge0,$$
which means $f(z)$ is convex on $[0,K]$, thus the maximum value is achieved at either $z=0$ or $z=K$. This suggests that we can adjust an optimal solution such that either $z_1=0$ or $z_2=0$. 

We can repeat this adjustment until there are only one non-zero variable among $z_1,\ldots,z_n$. So to solve your primary problem, just try the solutions $(k,0,\ldots,0),(0,k,\ldots,0),\ldots,(0,\ldots,0,k)$ and choose the optimal one among them.