2
$\begingroup$

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 >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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ Alternatively, use Lagrange multipliers. $\endgroup$ Nov 2, 2018 at 8:34
  • $\begingroup$ @xskxzr I think there is a problem in your analysis. f(z) is convex but not necessarily monotone. The maximum value is not necessarily at z=0 or z=K. In fact, I have run some simulations and find that optimal solutions might be (0,0,..,k_1,...,0,0,k_2,...,0,0) $\endgroup$
    – Paradox
    Nov 2, 2018 at 15:48
  • $\begingroup$ @Paradox The conclusion that the maximum value is achieved at z=0 or z=K does not require f(z) to be monotone. If f(z) is not monotone, it must first decrease then increase. $\endgroup$
    – xskxzr
    Nov 2, 2018 at 18:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.