Resource Allocation Algorithm Sought

Question

For a project of mine (no, not a homework or exam problem, though I think it would make a good one), I am in need of an algorithm. The problem seems familiar and general enough that I'm pretty confident it has been solved in the literature, but I do not have my algorithms books handy and it is not clear what terms would be used to describe it, so googling is of limited use.

Stripped of extraneous detail, the problem is as follows: You are given a set of resources { R_1, R_2, ... R_n} and a set of tasks {T_1, T_2, ... T_m}. Each task can be accomplished using any one of alternative sets of resources TR_m = { { R_1m1, R_1m2, ... }, { R2m1, R_2m2, ... }, ... }. Each resource can only be used by one task at a time. The problem is to see if all tasks can be fulfilled at the same time or, if that is not possible, what the largest number of tasks (starting at T_1) can be fulfilled simultaneously.

A naive algorithm which just assigns each task the first set of available resources is bound to fail unnecessarily sometimes: Think of TR_1 = { { R_1, R_2 }, { R_1 } } and TR_2 = { { R_1 }, { R_2 } }. T_1 would grab R_1 and R_2 and T_2 would fail, while TR_1 could have just taken R_1 and TR_2 could have taken R_2.

I am looking for an algorithm, preferably elegant and simple, that would do a better job.

In so far as it matters, the resources largely consist out of interchangeable subsets and tasks usually require just one or more resources from each set, so the naive algorithm usually succeeds, but that will not always be case.

Moreover, there are usually less than a dozen tasks and resources and the problem (coded currently in Python 3) is not real-time, so brute-force would generally be an acceptable solution, but I am looking for something better.

Any suggestions or links?

Answer 1

Use could use Branch and Bound.

You'd branch on "for tasks i, which set do I pick?", picking the biggest set first to cause failure as high up in the tree in as possible to save work. For the initial solution, you can flip that around to find a reasonable (but not optimal) solution quickly, which ends up saving work by pruning more in the real search later.

You could also branch on the s[q,t] of the following model which is closest to 0.5 (in a way, the choice which it is "least sure about").

The bound could be based on the linear relaxation of this ILP model:

maximize sum of x[t] over all t

variables:
0 <= x[t] <= 1  ; x[t] decides whether task t is scheduled or not
0 <= r[i,t] <= 1 ; r[i,t] decides whether task t uses resource i
0 <= s[q,t] <= 1 ; s[q,t] decides whether set q of task t is used

constraints:
1. for all tasks t: (sum s[q,t] over all valid q) - x[t] = 0
2. for all sets s[q,t]: (sum r[i,t] over all i in the set) - size_of_set * s[q,t] >= 0
3. for all resources i: sum r[i,t] over all t <= 1

1. forces exactly 1 set of resources to be associated with any task that is chosen.
2. forces the resources used by choosing set q for task t to be used by task t (>= 0 because sets may overlap)
3. forces all resources to be used no more than once.

I may have made mistakes in the model, and I'm not sure how good it is. Anyway, solve it with linear programming (no doubt there's a library for it for Python) and then do a couple of Gomory cuts for good measure (they may look scary, but they're actually pretty simple to program), not too many though, trying to get an all-integer solution with only Gomory cuts often converges very slowly. Doing some of them is a cheap way to improve a solution.

This will give you an estimate that will let you prune some of the search space. How much it actually prunes depends on how close it gets to the actual solution. I predict that it will tend to select several sets belonging to a task with some factor between 0 and 1, because selecting a set "only a bit" allows it to use the same resource for multiple tasks. It has to pick several sets then because it must use a total of 1 set per task, but that also means it has more choice of resource so it can do that. Linear Programming is sneaky that way, always trying to give you, in a sense, the most annoying answer :)

Of course in this model, you'd exclude any possibilities that are no longer possible (allocated resources and the sets that contain them and tasks that would have zero possible sets), and skip tasks that are already scheduled.

If this is too complicated, you can calculate a much simpler bound like this: for all tasks t, take the size of their smallest set s[t]. Check how many you can take until the total size is larger than the number of unallocated resources (so take the smallest, add the next smallest, and so on - sort them or use a min-heap).

Of course if with the resources allocated so far, so many tasks are now without any possible sets that in total (including the ones that were already scheduled) you can not get more than the best solution so far, you can give up on the current branch of the recursion tree.

For the initial solution, you could try using the greedy algorithm you described but with one change: take the smallest set that only contain unallocated resources. That way it tries to "keep out of the way" of further tasks, though obviously you can construct cases where this is worse than picking the first possible set.

edit: and of course if there is a set in the collection of sets of a task that is a superset of an other set in that collection, just delete it. It can't be any better to use that superset. That happens to fix the example given in OP, but it typically it wouldn't.

Answer 2

Suppose all the tasks are identical.

Then your problem is equivalent to the known NP-complete maximum set packing problem.

So your problem is certainly NP-hard and you are unlikely to find a perfect algorithm for this.