Search code examples
matlaboptimizationresourcesmathematical-optimizationallocation

Specifying Resource Allocation algorithm?

Can someone help me to solve or specify what type of problem is this:

I have a set of resources and a number of users, and for each user there is a specific subset of resources that can choose a single resource from for allocation. Two different users could not be assigned to the same resource.I need to allocate resources to users in a way to maximize the allocation. for example:

R={r1,r2,r3,r4} %set of resources

U={u1,u2,u3,u4} %set of users

u1 can choose a single resource from: {r1, r2, r3}

u2 can choose a single resource from: {r1, r2}

u3 can choose a single resource from: {r1, r4}

u4 can choose a single resource from: {r2}

in this case I should allocate

r3->u1, r1->u2, r4->u3, r2->u4.

If this was allocated differently u4 will have no resource to be allocated.

This is only to explain the problem, I need to solve this for 200 users and 100 resources. Can I seek your advise on which algorithm to use or how to solve this?

Solution

  • I often solve these type of assignment problems with an LP/MIP solver. The size is not too big so almost any solver will do and there are many readily available. It may look like a bit of overkill but in my experience it offers some useful flexibility (e.g. fixing some assignments, allowing additional ad-hoc constraints).

    Your problem could be formulated as:

    enter image description here

    I solved the problem as an RMIP which is just an LP (the x variables are automatically integer for this type of problem).

    In response to your question let me try to explain the equations.

    First of all we need to note that the variables x(u,r) only assume the values 0 or 1. This is a property of linear assignment problems. The reason is not totally obvious but a good book on linear programming can tell you more.

    The first equation assign1 says: we can assign each user to at most one resource. E.g. for user u1 we have: x(u1,r1)+x(u1,r2)+x(u1,r3) <= 1. This equation forbids that a user is assigned to two or more resources. We allow for unassigned users in case we are short of resources (e.g. if we have a dataset with 2 users and just 1 resource). As a user cannot be assigned to all resources, we do not sum over all r but only over the allowed combinations.

    The second equation assign2 says: we can assign each resource to at most one user. E.g. for resource r1 we have: x(u1,r1)+x(u2,r1)+x(u3,r1) <= 1. This equation forbids that a resource is assigned to two or more users. We need this one also otherwise several different users could be assigned to the same resource. We allow for unassigned resources in case we are short of users (e.g. for the case where we have 2 resources and just 1 user). As a resource cannot be assigned to any user, we do not sum over all u but only over the allowed combinations.

    Finally the objective counts how many valid assignments were made. This is the value we want to maximize. The trick is again to sum over the allowed combinations to prevent illegal assignments.

    The model is a slight variation on the LP model described here. Much more information on the assignment problem can be found in this book.

    For your little data set, here is the input data and the results: enter image description here