Sign in to follow this  

Optimal Resource Distribution Calculation?

This topic is 4015 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm wondering if this problem is solvable in low-order polynomial time in the numbers of elements in the problem, and if anyone can suggest a good algorithm or approach to use. I have a few ideas, but figure some additional input would be good. The problem is to optimize resource allocation with constraints. I believe there exists an optimal solution, which may ont be unique, but should be unambiguously optimal. Input: * A priority queue of projects that need up to some limit of a resource. * A set of sources of the resource, which have a limited total amount of the resource they can provide to projects. * A matrix of constraints giving a limit on how much of the resource each source can send to each project. A typical source will be able to send to most of the projects, but will have different sending limits for each project. If it helps to visualize, the limits on resource sending between each source-project pair can be thought of as like a practiacl limit due to the distance between them. Requirements / Details: * Projects higher on the queue should be funded as much as possible, before projects lower on the queue. * Projects should be funded as much as possible, up to their funding requirement. Additional funding should go to other projects. * Sources can send their resources to one or more projects, subject to their limited supply, the need of the project(s), and the pairwise limit between the source and project * Projects can receive resources from one or more sources, subject to the limited total need they have, the supply of hte sources, and the pairwise limit. To solve this, one might employ a guess-and-revise scheme. Sources would be picked somewhat arbitrarily for the first project on the queue, to supply it as much as possible, given the available supply and its need. Subsequent projects would then be supplied in the same manner, though if they are unable to be supplied because a project higher on the queue took some of their supply, then an attempt to free up that supply by finding an alternative sources for the higher project would be made. This revising could go several layers deep, as supplying project 3 might require revising project 2's allocation, which might require revising project 1's allocation, etc. This would continue, adding each subsequent project on the queue until all projects are supplied as much as possible, hopefully with an optimal solution. If I'm not glazing over too many nontrivial details, this might work... or would it? Any other suggestions? Thanks.

Share this post


Link to post
Share on other sites


If you relax the contraints on how much each source can give to a particular project, then I think a simple greedy heuristic can solve this. If you always assign the highest capacity source to the top-most project in the queue, you'd always have the highest probability of satisfying the needs of the other projects.

For the full problem, there might be a straightforward dynamic-programming solution, but nothing comes to mind ATM. Its been a while since my last algorithms class.

JB

Share this post


Link to post
Share on other sites
If there were no constraints on how much each source can give to each project other than the source's total supply and the project's need, then the solution would just be to sum up all sources' supplies and doll out the resources to the projects on the queue in order until the pooled supply or needs of projects are all used up. There'd be no need to determine which source actually supplies which project in this case. (There's no constraint against splitting a source's supplies over multiple projects.)

Based on my perhaps flawed and definitely limited knowledge of dynamical programming, I'm not sure that it applies. There's no way to break down the problem into optimally solvable subproblems. For example, I could fist try to find a way to fully supply the first project on the queue, then use that solution to limit solutions for later projects on the queue. But the first project can be supplied in many different ways, with no way to know (is this true?) whether one solution is better than another solution with regard to how it affects the ability to supply projects later on the queue. Hence, I mentioned above the need to go back and resolve the supply problem for the first project after trying to solve the second project problem, using the constrains provided by analyzing the second problem. That is, "project 2 needs supplies from this source, but project 1 is taking them. Can I supply project 1 from another source than the one that project 2 needs, freeing up the supply for project 2 without adversely affecting project 1's supply?". Of course, this gets much more complicated with more than two or three projects, requiring nested correction attempts, etc.

Share this post


Link to post
Share on other sites

This topic is 4015 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this