Resource Allocation Algorithm with Constraints

Question

I know that some algorithms exist for my kind of problem but I'm having problems naming it and the solution associated. Here is my problem :

I have a set W of wallet with money
I have a set P of project on which I can spend my money
Each wallet w has an amount of money M, and I can spend this money only on several project and only a specific amount
Each project p needs an amount d of money

Goal : Maximize the allocation of my wallet money so I can fund most of my project.

Also I would rather have all my project funded at for instance 95%, than having some project funded at 100% and other at 0%.

So I guess the function to minimize would be the sum of all (d-(all the money allocted to this project))² assuming I have not enough money to fund all my projects

Example :

I have 100€ on my first wallet, and I can spend 70% on project 1, 20% on project 3 and 10% on project 3

And I have 200€ my second wallet where I can spend 30% on project 1, 50% on project 2 and 20% and project 3.

About my projects :

Project 1 needs at least 120€
Project 2 needs at least 100€
Project 3 needs at least 110€

Thank you for help !

Please read and follow the posting guidelines in the help documentation, as suggested when you created this account. On topic, how to ask, and ... the perfect question apply here. StackOverflow is not a design, coding, research, or tutorial resource. However, if you follow whatever resources you find on line, make an honest coding attempt, and run into a problem, you'd have a good example to post. — Prune
– Prune, Commented Feb 19, 2019 at 19:16
Your specifications reduce the problem to a simple linear combination of monetary amounts. The problem description -- as presently given -- appears to require only straightforward algebraic analysis, not a special algorithm. — Prune
– Prune, Commented Feb 19, 2019 at 19:24

David Eisenstat · Accepted Answer · 2019-02-20 00:17:11Z

3

You can formulate this as a maximum flow problem. Connect a source vertex to vertices corresponding to the wallets, where the capacity of each arc is the amount of money in the wallet. Connect vertices corresponding to the projects to a sink vertex, where the capacity of each arc is the amount of money needed for that project. Connect wallets to projects with arcs whose capacity reflect the amount of money from that wallet that can be spent on that project.

Handling the piecewise quadratic objective is a bit tricky. Luckily, it's convex, so I bet you could use a quadratic program solver to good effect.

answered Feb 20, 2019 at 0:17

David Eisenstat

65.7k7 gold badges66 silver badges127 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Resource Allocation Algorithm with Constraints

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related