0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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\}$.

$\endgroup$
4
  • $\begingroup$ It would be easy to solve using optimization solver. However, is there any way to find $\pi_i^*, \forall i \in [1,I]$ analytically, i.e., $\pi_i^* = ...$, for example using KKT conditions? $\endgroup$
    – bnbfreak
    Sep 14 '19 at 1:58
  • $\begingroup$ I didn't mean to use an optimization solver. The optimal solution is to reindex so that $(a_i-b_i)/a_i \ge (a_{i+1}-b_{i+1})/a_{i+1}$ and then set $\pi_1 = \pi_2 = \dots = \pi_{j-1} = 1$ until $\sum_{i=1}^{j-1} a_i \le S < \sum_{i=1}^j a_i$, $\pi_j = (S - \sum_{i=1}^{j-1} a_i)/a_j$, and $\pi_{j+1} = \dots = \pi_I = 0$. $\endgroup$
    – RobPratt
    Sep 14 '19 at 2:36
  • $\begingroup$ At the end, is it correct that $\pi_i^* = \sum_{i=1}^{j-1}(a_i - b_i) + (a_j - b_j)\frac{S - \sum_{i=1}^{j-1}a_i}{a_j}$? In this case, how to find the correct $j$? $\endgroup$
    – bnbfreak
    Sep 14 '19 at 3:25
  • $\begingroup$ No, after reindexing in descending order of $(a_i-b_i)/a_i$, the optimal solution looks like $\pi^*=(1,\dots,1,\pi^*_j,0,\dots,0)$, where $j$ is the smallest index such that $\sum_{i=1}^j a_i > S$. $\endgroup$
    – RobPratt
    Sep 14 '19 at 3:31

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.