The following problem was posted on Operations Research Stack Exchange. A system contains $K$ users and $N$ resources. Each unit of resource may be allocated to at most one user. Each user $k$ requires a specified number $d_k$ of resource units, which must be consecutive. Not all resource sequences of the proper length will be acceptable to a user. Citing an example from the original post, you might have $d_1=3,$ with user 1 accepting only one of following sets: $\{1, 2, 3\},$ $\{7, 8, 9\},$ $\{11, 12, 13\},$ or $\{17, 18, 19\}.$ The objective is to assign resources to as many users as is possible.
Formulating this as an integer linear program is straightforward, and I coded the IP model in Java (using CPLEX as the solver) to provide a benchmark. The author of the question, however, was looking for heuristic solutions. I suggested a few possibilities, and decided to code two of them just to see how well they did. The setup for all of them is identical. You start with the following elements:
- the set of unsatisfied users (initially, all users);
- an enumeration of all resource sets compatible with any user (with each such set represented by an integer ID number);
- a mapping of each user ID to the set of IDs of all compatible resource sets;
- a mapping of each resource set ID to the set of IDs of all users who would accept that set; and
- a mapping of each resources set ID to the set of IDs of all other resources sets that conflict with that set.
Two resource sets conflict if they intersect, in which case allocating one of them precludes allocating the other since each unit of resource can be used at most once.
All the heuristics I suggested work by finding a valid allocation (an unused resource set that does not conflict with any resource set already used and an user who has not yet been served and will accept that resource set), making that allocation, and then updating the mappings described above. Updating the mappings means removing the user who just received resources, removing the resource set just assigned, and removing any other unassigned resource sets that conflict with the set just assigned. Those changes can have "ripple effects": removing a user may result in a surviving resource set having no compatible users left (in which case the resource set can be removed), and removing a resource set (whether used or due to a conflict) may leave a user with no surviving resource sets that are compatible, in which case the user can be removed. So the update step involves some looping that must be coded carefully.
The various heuristics I suggested are distinguished by two fundamental choices. First, in each iteration do you pick an available resource set and then look for a user who will accept it, or do you pick a user who has not yet been served and then look for a compatible resource set that is still available? Second, regardless of order, what criteria do you use for selecting users and resource sets?
There are a lot of ways to make those choices, and I home in on two. My first approach starts by selecting the available resource set with the fewest remaining conflicts and then chooses the compatible user having the fewest surviving options for resource sets. My second approach starts by selecting the remaining user with the fewest surviving options for resource sets and then choosing the compatible resource set with the fewest remaining conflicts. In all cases, ties are broken randomly. My logic is that picking the resource set with the fewest conflicts will leave the most surviving resource sets and (hopefully) allow more users to be served, and picking the user with the fewest remaining options will (hopefully) reduce the number of users who are frozen out because all compatible resource choices have already been allocated.
I'll take a moment to note here that the two approaches I just stated are intended to be one-pass heuristics (find a feasible allocation and stop). You could rerun them with different random seeds, but that would only change the results (not necessarily for the better) if one or more ties had occurred during the first pass. Another possibility, which I did not bother to code, would be to select either resource set or user randomly at each stage, then select the other half of the assignment randomly from the compatible choices. I suspect that any single run of the random approach would likely do worse than what I described above, but you could keep rerunning the purely random heuristic for a specific number of iterations (or with a time limit) and track the best solution ever found. That might improve over the versions I tested.
Using the dimensions specified (in a comment, replying to me) by author of the question, I did a small number of tests. In those tests, the resource set first heuristic consistently beat the user first heuristic, and both exhibited what I would consider to be decent results. On three test runs with different seeds for the random problem generator, I got results of 14/13/11, 15/14/11 and 14/13/10, where the first number is the optimal number of customers served (from the IP model), the second is the number served by the resource-first heuristic, and the third is the number served by the customer-first heuristic. Run times for the heuristics on my humble PC (including setup times) were minuscule (under 20 milliseconds).
My Java code can be found here.
Please note that the number of resources per user is not any number within a range, but only some specific numbers within a range. For example, {1, 2, 4, 8, 16} or {1, 3, 6, 12}.
ReplyDeleteThis does not directly affect the operation of the heuristics (nor the IP model), but it does reduce the size of the problem by limiting the number of resource sets that might be of use to at least one user.
DeleteActually, it may not even reduce the problem size. What really matters is how many distinct resource sets are compatible with at least one user, not how many different resource set sizes there are.
DeleteInteresting Problem. I am not a java user, thus trying to transform this script into python/Matlab. Specially interested in ConflictHeuristic solution. In this script, it seems that the Maps such as users, resources, and conflicts are not defined anywhere. For example, you have (i) for (int u : users.get(set)), (ii) double x = resources.get(u).size() and (iii)for (Entry> e : conflicts.entrySet())
DeleteJava uses class inheritance. The ConflictHeuristic and UserHeuristic classes extend (are descended from) the parent Heuristic class, which contains code common to both heuristics ... including the map declarations and, in the constructor, the code to initialize them.
DeleteThanks a lot. The ConflictHeuristic is iterative and the condition you have is 'while (!users.isEmpty())', i.e., iterate until no resource sets are left. But there is no guarantee that you have 100% resource utilisation or 100% user packing depending on number of resource sets and users and their demands. Then it seems to be a never ending loop!
DeleteYou are correct that there is no guarantee all resources can be used (or all users can be satisfied). The key is in how the updates are done at each step. You want to continue allocating resource sets until no legal allocations are left. In the update loop, I delete not just the resource set and user that were just paired, but any unmatched users for whom no allocation is possible and any resource set that cannot be allocated to any remaining user. So as long as a resource set remains, there must also be at least one user to whom it can be allocated.
DeleteI implemented this conflict heuristic method, i.e., user first and selecting the best resource set. Unfortunately, this is performing little worse than the another solution my fellow friend has. Is there a way to improve this performance of this solution?
DeleteI'm not sure. You might try keeping track, for each pair of unsatisfied user and compatible remaining resource set, how many options the user has other than that set. For instance, if set S is compatible with user U and U has three options left (including S), the "score" for that pair would be 2 (U has two options left if S goes away). After picking the next user to serve, scan that user's remaining options and choose the one for which either the minimum or average score (excluding the score for the chosen user) is largest, indicating that consuming that resource would do less damage to other users' prospects ... maybe.
DeleteBut the score for all compatible resource sets will be equal for a given user. Previously, for the user that is to be served now, we used to find the set that has minimum number of conflicts. Since we are not doing as you mentioned in your reply, how come we have different scores for the compliant/remaining resource sets of the user to be served?
DeleteI think for all the compatible remaining resource set, the score will be the same. 'if set S is compatible with user U and U has three options left (including S)', then all three sets will have same score, right? Would you please elaborate on this?
DeleteAll three sets will have the same score (2) *for that user*. If any of those sets are compatible with other unsatisfied users, they will have scores for those users as well. For each set compatible with the current user, you look at that set's score for other users, compute a min or average, and select the set whose min or average is smallest.
DeleteI implemented this...unfortunately, it is not performing well...worse than the previous one.
DeleteCan any heuristic perform better than the MIP solution?
ReplyDeleteI assume by "perform better" you mean get the same answer faster or get a better (but not necessarily optimal) answer in the same amount of time. This of course depends on the MIP solver used. Commercial solvers have the advantage of being coded (and continually improved) by professionals, and they usually contain heuristics of their own. Also, commercial solvers typically use parallel threading by default. Some heuristics are more amenable to parallel threads than others, and for amateurs it can be tricky to code parallel threads safely. There's also the setup time for a MIP model to consider. So, bottom line, sometimes heuristics get good solutions sooner than MIP solvers and sometimes not. There is no general rule that "heuristic X is always faster than a MIP solver" or "heuristic Y is always slower than a MIP solver".
DeleteNo, by performing better I meant packing more users.
ReplyDeleteThe optimal solution to the MIP model will pack the maximum possible number of users, so there is no way a heuristic solution can do better.
Delete