Distributed resource allocation

1. A computer-implemented method for performing resource allocation, the method comprising:

using a distributed computing system that includes a number of individual computer-implemented solvers for performing resource allocation of M resources among N users into K pools by solving a knapsack problem (KP) subject to K global constraints and L local constraints:

receiving data representing the K global constraints and the L local constraints, wherein K is smaller than L, each of the K global constraints restricts a respective maximum per-pool cost of the M resources across two or more users, and each of the L local constraints restricts a per-user selection of the M resources;

decomposing the KP into N sub-problems using K dual multipliers, each of the N sub-problems corresponding to a respective one of the N users and subject to the L local constraints with respect to (w.r.t.) the corresponding user, wherein N is on an order of billions or larger, wherein each of the K dual multipliers corresponds to a respective one of the K global constraints;

determining the number of individual computer-implemented solvers for solving the N sub-problems;

distributing the N sub-problems among the number of individual computer-implemented solvers by assigning each sub-problem to a respective computer-implemented solver;

solving the KP by the distributed computing system by performing two or more iterations, and, in one iteration, the method comprising:

solving each of the N sub-problems by the computer-implemented solver to which the sub-problem was assigned independently, wherein solving each of the N sub-problems comprises computing an amount of each of the M resources to be allocated to the corresponding user of the N user, and

computing, for each of the K pools, a per-pool cost of the M resources across the N users based on the amount of each of the M resources to be allocated to the corresponding user of the N user, and

updating each of the K dual multipliers w.r.t. a corresponding pool based on a difference between a maximum per-pool cost of the M resources across two or more users for the corresponding pool restricted by a corresponding global constraint and a per-pool cost of the M resources across the N users for the corresponding pool computed based on the amount of each of the M resources to be allocated to the corresponding user of the N user;

determining whether a convergence condition is met based on the K dual multipliers;

in response to determining that a convergence condition is met based on the K dual multipliers, solving each of the N sub-problems based on the K dual multipliers by one of the number of individual computer-implemented solvers independently, wherein solving each of the N sub-problems comprises computing an amount of each of the M resources to be allocated to the corresponding user of the N user; and

allocating the amount of each of the M resources to the corresponding user of the N user.

2. The method of claim 1 , wherein L is on an order of billions or larger.

3. The method of claim 1 , wherein:

determining the number of individual computer-implemented solvers for solving the N sub-problems comprises determining the number of individual computer-implemented solvers for solving the N sub-problems based on a specified computation time for solving the KP; and

solving each of the N sub-problems by the computer-implemented solver to which the sub-problem was assigned independently comprises solving two or more of the N sub-problems by computer-implemented solvers to which the two or more of the N sub-problem were assigned in parallel.

4. The method of claim 1 , wherein:

determining the number of individual computer-implemented solvers for solving the N sub-problems comprises determining the number of individual computer-implemented solvers to be N, and

solving each of the N sub-problems by the computer-implemented solver to which the sub-problem was assigned independently comprises solving each of the N sub-problems by a respective one of the N individual computer-implemented solvers in parallel.

5. The method of claim 1 , wherein solving each of the N sub-problems by the computer-implemented solver to which the sub-problem was assigned independently comprises solving an integer programming (IP) problem by an IP solver independently.

6. The method of claim 1 , wherein solving each of the N sub-problems further comprises computing, for each of the K pools, a per-pool cost of the M resources by the corresponding user based on the amount of each of the M resources to be allocated to the corresponding user.

7. A distributed computing system for performing resource allocation of M resources among N users into K pools by solving a knapsack problem (KP) subject to K global constraints and L local constraints, comprising:

one or more computers; and

one or more computer memory devices interoperably coupled with the one or more computers and having tangible, non-transitory, machine-readable media storing one or more instructions that, when executed by the one or more computers, perform one or more operations comprising:

receiving data representing the K global constraints and the L local constraints, wherein K is smaller than L, each of the K global constraints restricts a respective maximum per-pool cost of the M resources across two or more users, and each of the L local constraints restricts a per-user selection of the M resources;

decomposing the KP into N sub-problems using K dual multipliers, each of the N sub-problems corresponding to a respective one of the N users and subject to the L local constraints with respect to (w.r.t.) the corresponding user, wherein N is in an order of billions or larger, wherein each of the K dual multipliers corresponds to a respective one of the K global constraints;

determining a number of individual processors out of the plurality of processors for solving the N sub-problems independently;

distributing the N sub-problems among the number of individual processors

solving the KP by the distributed computing system by performing two or more iterations, and, in one iteration, the operations comprising:

solving each of the N sub-problems by the computer-implemented solver to which the sub-problem was assigned independently, wherein solving each of the N sub-problems comprises computing an amount of each of the M resources to be allocated to the corresponding user of the N user, and

computing, for each of the K pools, a per-pool cost of the M resources across the N users based on the amount of each of the M resources to be allocated to the corresponding user of the N user, and

updating each of the K dual multipliers w.r.t. a corresponding pool based on a difference between a maximum per-pool cost of the M resources across two or more users for the corresponding pool restricted by a corresponding global constraint and a per-pool cost of the M resources across the N users for the corresponding pool computed based on the amount of each of the M resources to be allocated to the corresponding user of the N user;

determining whether a convergence condition is met based on the K dual multipliers;

in response to determining that a convergence condition is met based on the K dual multipliers, solving each of the N sub-problems based on the K dual multipliers by one of the number of individual processors independently, wherein solving each of the N sub-problems comprises computing an amount of each of the M resources to be allocated to the corresponding user of the N user; and

allocating the amount of each of the M resources to the corresponding user of the N user.

8. The distributed computing system of claim 7 , wherein L is in an order of billions or larger.

9. The distributed computing system of claim 7 , wherein:

determining the number of individual processors for solving the N sub-problems comprises determining the number of individual processors for solving the N sub-problems based on a specified computation time for solving the KP; and

solving each of the N sub-problems by one of the number of individual processors independently comprises solving each of the N sub-problems by one of the number of individual processors in parallel.

10. The distributed computing system of claim 7 , wherein:

determining the number of individual processors for solving the N sub-problems comprises determining the number of individual processors to be N, and

solving each of the N sub-problems by one of the number of individual processors independently comprises solving each of the N sub-problems by a respective one of the N individual processors in parallel.

11. The distributed computing system of claim 7 , wherein solving each of the N sub-problems by one of the number of individual processors independently comprises solving an integer programming (IP) problem by an IP processor independently.

12. The distributed computing system of claim 7 , wherein solving each of the N sub-problems further comprises computing, for each of the K pools, a per-pool cost of the M resources by the corresponding user based on the amount of each of the M resources to be allocated to the corresponding user.

13. A non-transitory, computer-readable storage medium storing one or more instructions executable by a computer system to perform operations for performing resource allocation, the operations comprising:

using a distributed computing system that includes a number of individual computer-implemented solvers for performing resource allocation of M resources among N users into K pools by solving a knapsack problem (KP) subject to K global constraints and L local constraints:

receiving data representing the K global constraints and the L local constraints, wherein K is smaller than L, each of the K global constraints restricts a respective maximum per-pool cost of the M resources across two or more users, and each of the L local constraints restricts a per-user selection of the M resources;

decomposing the KP into N sub-problems using K dual multipliers, each of the N sub-problems corresponding to a respective one of the N users and subject to the L local constraints with respect to (w.r.t.) the corresponding user, wherein N is on an order of billions or larger, wherein each of the K dual multipliers corresponds to a respective one of the K global constraints;

determining the number of individual computer-implemented solvers for solving the N sub-problems;

distributing the N sub-problems among the number of individual computer-implemented solvers by assigning each sub-problem to a respective computer-implemented solver;

solving the KP by the distributed computing system by performing two or more iterations, and, in one iteration, the operations comprising:

solving each of the N sub-problems by the computer-implemented solver to which the sub-problem was assigned independently, wherein solving each of the N sub-problems comprises computing an amount of each of the M resources to be allocated to the corresponding user of the N user, and

computing, for each of the K pools, a per-pool cost of the M resources across the N users based on the amount of each of the M resources to be allocated to the corresponding user of the N user, and

updating each of the K dual multipliers w.r.t. a corresponding pool based on a difference between a maximum per-pool cost of the M resources across two or more users for the corresponding pool restricted by a corresponding global constraint and a per-pool cost of the M resources across the N users for the corresponding pool computed based on the amount of each of the M resources to be allocated to the corresponding user of the N user;

determining whether a convergence condition is met based on the K dual multipliers;

in response to determining that a convergence condition is met based on the K dual multipliers, solving each of the N sub-problems based on the K dual multipliers by one of the number of individual computer-implemented solvers independently, wherein solving each of the N sub-problems comprises computing an amount of each of the M resources to be allocated to the corresponding user of the N user; and

allocating the amount of each of the M resources to the corresponding user of the N user.

14. The non-transitory, computer-readable storage medium of claim 13 , wherein L is on an order of billions or larger.

15. The non-transitory, computer-readable storage medium of claim 13 , wherein:

determining the number of individual computer-implemented solvers for solving the N sub-problems comprises determining the number of individual computer-implemented solvers for solving the N sub-problems based on a specified computation time for solving the KP; and

solving each of the N sub-problems by the computer-implemented solver to which the sub-problem was assigned independently comprises solving two or more of the N sub-problems by computer-implemented solvers to which the two or more of the N sub-problem were assigned in parallel.

16. The non-transitory, computer-readable storage medium of claim 13 , wherein:

determining the number of individual computer-implemented solvers for solving the N sub-problems comprises determining the number of individual computer-implemented solvers to be N, and

solving each of the N sub-problems by the computer-implemented solver to which the sub-problem was assigned independently comprises solving each of the N sub-problems by a respective one of the N individual computer-implemented solvers in parallel.

17. The non-transitory, computer-readable storage medium of claim 13 , wherein solving each of the N sub-problems by the computer-implemented solver to which the sub-problem was assigned independently comprises solving an integer programming (IP) problem by an IP solver independently.

18. The non-transitory, computer-readable storage medium of claim 13 , wherein solving each of the N sub-problems further comprises computing, for each of the K pools, a per-pool cost of the M resources by the corresponding user based on the amount of each of the M resources to be allocated to the corresponding user.