Determining resource exhaustion beforehand

Question

I guess this is a problem solving question but I am out of ideas, don't really know where else I can resort for help, and I need to solve this problem.

Essentially we have a set of consumers and a set of resources, and the objective is to assign a resource to each consumer. Not every resource is eligible for every consumer: there are many different kind of rules that limit the choices.

Given these consumers and resources:

consumers = [C1, C2, C3, C4, C5]
resources = [R1, R2, R3, R4, R5, R6, R7, R8]

We can represent the eligible resources with a table (note that whether in this example grouping into resource sections may suggest a solution, in practice eligible resources would be more scattered and grouping would be hard or not possible at all):

    C1    C2    C3    C4    C5
R1  x     x     x     x
R2  x     x     x     x
R3                    x     x
R4                    x     x
R5                    x     x
R6                    x     x
R7                    x     x
R8                    x     x

We try assigning a resource to every consumer:

while unsatisfied_consumers:
    unassigned_resources = list(resources)
    unsatisfied_consumers = list(consumers)

    for c in unsatisfied_consumers:
        for r in eligible_resources[c]:
            if c.assign(r):
                unsatisfied_consumers.remove(c)
                unassigned_resources.remove(r)
                break

If not all consumers could be satisfied, for each one of them we try finding eligible already assigned resources, and the consumer assigned to it is given an unassigned resource instead (if eligible). Essentially a reassignment. This would be right after the for loop:

for c in unsatisfied_consumers:
   assigned_resources = [r for r in resources if r not in unassigned_resources]
   c_eligible_resources = [r for r in eligible_resources[c] if r in assigned_resources]

   for r in c_eligible_resources:
       satisfied_consumer = r.assigned_consumer()
       # try to find an alternative resrouce for the already satisfied consumer
       # so that c can be assigned its resource instead
       for unassigned_r in unassigned_resources:
           if satisfied_consumer.assign(unassigned_r):
               unassigned_resrouces.remove(unassigned_r)
               unsatisfied_consumers.remove(c)
               c.resource = r

As you can see, we are brute-forcing our way to finding the solution.

The problem is when not all consumers can be satisfied, simply due to the resource eligibility. No matter how many times reassigning resources is attempted, some consumers will never be assigned resources because there are not enough resources.

And there is where I am trying to get. I am trying to devise a way to be able to tell what consumers are exposed to resource exhaustion before even starting to assign resources, so that when unsatisfaction issues show up, we can safely assume their state and carry on with the consumers that can actually be assigned resources.

Using my table example, at first glance we can tell that consumers C1, C2 and C3 will rival for resources R1 and R2, therefore one of these consumers will simply be unsatisfied. What I am trying to do is to design a mechanism to acknowledge that [C1, C2, C3] are subject to resource exhaustion therefore if unsuccessful assignment occurs, we should not try again for these particular consumers.

We know what resources are elliglbe for each consumer, and inversely we know what consumers "fit" in each resource. Perhaps this information could be use in the solution?

Answer 1

In general, this looks like an NP-complete problem. This means that a brute-force approach is essentially the optimal solution (that we know of) if the compatibility table can be any value at all.

In practice, it might contain regularities that you can exploit. If the true situation is similar to the example data you gave, then effectively you have only two different types of resource to give out and three types of customer to claim them.

That means that instead of tracking each individual assignment, you simply count how many of the class-A customers will be satisfied and how many of the type-X resources will be assigned. Once you've decided that, you can then make the solution concrete by randomly choosing N from the M class-A customers who will be served, etc.

That doesn't make the problem more feasible in general, but it reduces the concrete number of cases to compute. In particular cases this might constitute the difference between "hopeless" and "expensive". (If it doesn't, then you'll have to give up on finding an optimal solution and instead look at the whole wide world of heuristic algorithms to find an approximate one.)

Answer 2

I might be missing something but it would seem to make sense to assign the most popular resource to the customer with the fewest suitable resources and continue in this fashion until no more allocations can be done.

If you wanted to take into account existing allocations, where the scores were equal, you could simply pick the resource allocations already assigned.

If you could supply some specific data sets, it would make things easier but I appreciate this might not be possible.