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.
