1

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?

  • Is the table in your question a realistic indication of the complexity of the relationship between consumers and resources? If it is, you may be able to get a decent indication by grouping consumers by their respective eligible resource. In the example above consumers C1, C2 and C3 would be in a group. You could then determine that the number of eligible resources is smaller than the number of consumers in the group, indicating them for resource exhaustion. – Jonathan van de Veen Feb 27 '18 at 12:09
  • @JonathanvandeVeen I've actually considered this, but note that the table was just a simple example. Grouping comes natural in that example, it'd be the obvious choice, but in a real case there would be many cross sections and scattered "eligibilities". In some cases grouping would be possible, but implementing a way to identify these groups would probably be a challenge in itself. – dabadaba Feb 27 '18 at 12:25
  • Why do you create all consumers at once instead of creation of only necessary consumers when there are eligible resources? You can have a queue of incoming resources and a queue for each particular consumer. When there is no consumer for particular resource, create one and push resources into its queue. – cassandrad Feb 27 '18 at 12:57
  • Sounds very similar to the Banker's algorithm/problem. While not the answer, it could potentially be a starting point or give early warning. – wondra Feb 27 '18 at 13:20
  • To clarify - for say, C1, do they require both R1 & R2 or either? – Robbie Dee Feb 27 '18 at 13:43
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.)

  • In practice these regularities may not be found. There are many different kind of cases, sometimes groups can be identified, sometimes the "eligibilities" are scattered. I would have to design a way to identify all these different groups; I'm not sure if this is even possible? I am good with approximations though, the perfect solution does not have to be found, however identifying those exhaustion cases is important. – dabadaba Feb 27 '18 at 12:33
0

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.

  • Actually your first suggestion is partly a thing, I just didn't include it so as not to complicate the code. When the first try fails to assign resources to all consumers, on the second try and on, the harder consumers are the first ones on the list. However I should also try with the most popular resources as you say, and probably do it from the very first try as well. – dabadaba Feb 27 '18 at 14:03
  • I didn't quite understand what you are suggesting in your second point. – dabadaba Feb 27 '18 at 14:04
  • I could make some more cases, but honestly I am not sure they would give much additional information. The eligibility of resources can vary greatly depending on the case. – dabadaba Feb 27 '18 at 14:05
  • @dabadaba Re the 2nd point, I wasn't sure if you wanted to do the allocations from scratch each time or whether there were resources already assigned to consumers that you might want to consider. – Robbie Dee Feb 27 '18 at 14:10
  • Oh, good. Now we're rewarding the customers that scream the loudest. – Robert Harvey Feb 27 '18 at 16:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.