Logic programming: how to distribute resources among consumers?

Question

I have a task in which I must distribute unique resources among consumers. Rules are:

• each consumer has a set of resource types they can use,
• each resource is unique,
• each consumer must receive n>0 resources,
• all resources must be distributed.

E. g. we have this list of consumers and their preferences:

• A: {X, W}
• B: {X, Y, V}
• C: {X, Z}
• D: {Z}

We have a list of resources: [X, W, Y, V, Z].

If we assign resources naively by iterating through the list of consumers and providing them with the first available resource from their set, we fail on D because the only Z is already assigned to C. A better solution is this: A(W), B(Y, V), C(X), D(Z).

Looks like a logic programming problem to me! While it is trivial to write a Prolog program that provides solutions for this particular case, what I want is a general program that can solve any such problems, or tell me that no solution for given data exists.

Where should I look, what should I google for, does this problem have a name?

Answer 1

This is an example of an endless variety of resource allocation tasks for which logic programming is indeed well-suited and frequently used. Related tasks are called transportation and assignment problems in the literature, though the details in this formulation are different. Consider this Prolog formulation as a working starting point with which you can solve such tasks:

distribution([], [], []).
distribution([C-Ps|CPs], Rs0, [C-As|CAs]) :-
        allocation(Ps, As, Rs0, Rs1),
        As = [_|_],
        distribution(CPs, Rs1, CAs).

allocation(_, [], Rs, Rs).
allocation(Ps0, [A|As], Rs0, Rs) :-
        select(A, Ps0, Ps1),
        select(A, Rs0, Rs1),
        allocation(Ps1, As, Rs1, Rs).

distribution/3 expects as its first argument a list of pairs of the form Consumer-Preferences, and as its second argument a list of resources. It relates this instance description to solutions in the form of pairs Consumer-Allocated resources. Example query with SWI-Prolog for the concrete task you specified:

?- distribution([a-[x,w],b-[x,y,v],c-[x,z],d-[z]], [x,w,y,v,z], Ds).
Ds = [a-[w], b-[y, v], c-[x], d-[z]] ;
Ds = [a-[w], b-[v, y], c-[x], d-[z]] ;
false.

You can use this formulation for all tasks of this kind. The formulation is complete: It reports all solutions that exist (and some redundantly, because the allocated resources may be stated in any order, as you already see in the example above; you can introduce symmetry breaking constraints in allocation/4 to avoid this - one way to solve this is to insist that As be ascending with respect to the standard term order), and hence there are no (further) solutions if it answers false.