Assume we have a simple resource allocation problem, where all players have the same cost, but a different utility $a_s$. The resources assigned to a certain player must be between $L$ and $M$. Moreover, we add a proportion constraint. That is, each player $s$ is assumed to contribute a percentage of $p_s$ of his utility to a goal that we require to be at least $P$ % of the total utility. We assume that these quantities are inversely related, that is: players with a large utility, have a small $p_s$. The problem is formulated as:

\begin{align} z_{BP}=\max \quad & \sum_{s \in \mathcal{S}} a_{s} \cdot y_{s} & \\ \text{s.t.} \quad & \sum_{s \in \mathcal{S}}y_s = R & \\ & \sum_{s \in \mathcal{S}} a_{s} \cdot y_{s}\cdot p_s \geq \sum_{s \in \mathcal{S}} a_{s} \cdot y_{s}\cdot P \\ & L \leq y_s \leq M & \forall s \in \mathcal{S} \end{align} where $y_s$ is the decision variable deciding the amount of resources assigned to player $s$.

We use Lagrangian relaxation to relax the difficult constraints, i.e. the constraint prescribing the minimum proportion of utilities. We are left with a simple knapsack problem, where we can just select the players with the highest score (utility corrected for constraint violation).

I was wondering whether there would be a way to estimate the Lagrange multiplier given the instance, without solving the problem and without using subgradient optimization. As the optimal solution without the proportion constraint is trivial, I suspect that there should be a way to estimate the 'price' of the constraint. For example by comparing the number of players with $p_s \geq P$ and the number of players with $p_s < P$, or the sum $\sum_{s \in \mathcal{S}:p_s < P} a_s$ and the sum $\sum_{s \in \mathcal{S}:p_s \geq P} a_s$.

  • 1
    $\begingroup$ What is $u_s$ (or is that a typo and should be $a_s$? $\endgroup$
    – prubin
    Jan 25, 2021 at 22:31
  • $\begingroup$ Sorry, that is indeed a typo. It should be $a_s$. I'll update it. $\endgroup$
    – Pete S
    Jan 26, 2021 at 7:58
  • 1
    $\begingroup$ I don't see any easy way to estimate the multiplier. Definitely not either of the possibilities you suggested (since they don't take $L$, $M$ and $R$ into account). You could get the multiplier value by solving a linear program, but that would also solve the original problem, so you wouldn't need the multiplier. Re subgradient optimization, with only one relaxed constraint you could just do binary search on the multiplier, which would be pretty easy. $\endgroup$
    – prubin
    Jan 26, 2021 at 23:05


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.