Find an optimal solution formula from multiple variables analytically

Question

If I have an optimization problem as follows: \begin{equation} \label{eqn:for3b} \begin{aligned} (\mathbf{P}_1) \phantom{10} & \max_{\boldsymbol{\pi}} \phantom{5} \sum_{i=1}^I\pi_i(a_i - b_i). \end{aligned} \end{equation} \begin{eqnarray} \text{ s.t. } \quad \sum_{i=1}^I \pi_i a_i \leq S, \label{eqn:for3c} \\ 0 \leq \pi_i \leq 1, \forall i \in [1, I] \end{eqnarray} how to find the optimal solution formula of $\pi_i, \forall i \in [1,I]$? As far as I understand the optimal solution occurs if $\frac{\partial(\sum_{i=1}^I\pi_i(a_i - b_i))}{\partial\pi}= 0$. In this way I can obtain Lagrangian expression: \begin{equation} \label{eqn:for3a} \begin{aligned} L(\pi,\lambda,\sigma) &= \sum_{i=1}^I\pi_i(a_i - b_i) - \lambda_1(S - \sum_{i=1}^I \pi_i a_i - \sigma_1) + \lambda_2(\pi_1 - \sigma_2) \\ &+ \lambda_3(1 - \pi_1 - \sigma_3) + ... + \lambda_{I+1}(\pi_I - \sigma_{I+1}) + \lambda_{I+2}(1 - \pi_I - \sigma_{I+2}). \end{aligned} \end{equation} However, since it has many $\pi$'s, how can I obtain the general optimal $\pi^*_i, \forall i \in [1,I]$ formula? Is there any suggestion using KKT conditions?

Answer 1

This problem is the linear programming (LP) relaxation of a 0-1 knapsack problem, and an optimal solution is obtained by sorting in descending order the ratio $(a_i-b_i)/a_i$ and setting $\pi_i$ according to this order. This greedy algorithm is optimal for the LP relaxation but only a heuristic if you require $\pi_i \in \{0,1\}$.