2
$\begingroup$

I have a system with $N$ resources.

There are $K$ users in the system demanding these resources.

The demand of resources for a given user $k$, $d_k$ follows $d_k\in\{1,3,6\}$

The constraints for this problem are

a. The resources assigned to any user are contiguous

b. One resource can be assigned to one user only.

c. One or more users may not get any resources.

d. An user can access only a given set of contiguous resources, its candidates.

Example,

For user 1, we have $d_1=3$, this means user 1 needs three resources out of $N$ resources. Lets say, for this user, the number of sets of accessible contiguous resources is 4, and the sets of given resources are given as $\{\{1,2,3\},\{7,8,9\},\{11, 12,13\}, \{17,18,19\}\}$. This means, if user 1 gets its demand satisfied, the assigned resources must be of one of these 4 sets/subsets/candidates.

Similarly, let the demand of user 2 be 1, $d_2=1$, i.e., needs 1 out of $N$ resources. And it has 5 candidates.

The different sets of resources that can be assigned to this user $2$ is given by $S_2=\{\{1\},\{9\},\{17\},\{27\},\{33\}\}$. So, for user 2, we have 5 candidates/sets/subsets of contiguous resources.

I want to serve as many users as possible.

What is an efficient heuristic model for this user packing problem.

$\endgroup$
8
  • 2
    $\begingroup$ Why heuristic but not metaheuristic? $\endgroup$
    – prubin
    Commented May 20, 2022 at 14:38
  • $\begingroup$ @prubin I cannot effort the complexity (due to the iterative process) of the meta-heuristics. Also, I don't prefer to use any special toolboxes $\endgroup$
    – KGM
    Commented May 20, 2022 at 18:17
  • $\begingroup$ OK ... but I'm not sure a "heuristic" will be any faster/less complex than a metaheuristic. $\endgroup$
    – prubin
    Commented May 20, 2022 at 18:32
  • $\begingroup$ Out of curiosity, what sort of dimensions are you looking at ($N$, $K$, $\max_k d_k$ and maximum number of compatible resource sets for any user)? $\endgroup$
    – prubin
    Commented May 23, 2022 at 16:07
  • $\begingroup$ @prubin thanks. $N=100$,$K=20$,$\max_kd_k=16$ and maximum number of compatible resource set for any user is around 10. I have the feeling that the solutions you proposed will be very far from the optimal. $\endgroup$
    – KGM
    Commented May 23, 2022 at 19:14

1 Answer 1

1
$\begingroup$

I can suggest a couple of heuristics, with absolutely no guarantee that they will perform well. They share a common data structure. Start by identifying all sets of contiguous resources useful to any user. Map each user to the set of resource sets suitable for that user (noting that a given resource set might be useful for more than one user), and each resource set to the set of users that can use it. Next, map each resource set to the set of resource sets with which it conflicts (intersects). For instance, $\lbrace 1, 2\rbrace$ and $\lbrace 2, 3, 4\rbrace$ conflict because resource 2 is contained in their intersection.

You can now proceed in a number of ways. One is to prioritize the resource sets either randomly or according to how many unserved users they would serve (I would go with a smaller user set having higher priority than a larger user set) or based on the number of surviving conflicts they have (fewer means higher priority), then take the highest priority resource and assign it to one of the users it can serve (either randomly or by picking the user with the fewest remaining options). Another is to prioritize the users based on how many of their options survive, then take the user with the fewest remaining choices and assign a resource (either randomly or based on the fewest surviving conflicts). In each case, after making an assignment, delete the user from the pool of unserved users and delete the resource and all surviving conflicted resources from the pool of available resources.

Addendum: I wrote a blog post about this that includes a link to my Java code.

$\endgroup$
16
  • $\begingroup$ thanks a lot for your answer. The solutions looks good. Sometimes it is difficult to follow because of the many choices you provide for user priority and resource set priority. Can you provide me the code to implement this options for a small example. $\endgroup$
    – KGM
    Commented May 20, 2022 at 21:57
  • $\begingroup$ Sorry, but I have not coded this. $\endgroup$
    – prubin
    Commented May 21, 2022 at 2:23
  • $\begingroup$ would you please clarify 'I would go with a smaller user set having higher priority than a larger user set'. $\endgroup$
    – KGM
    Commented May 21, 2022 at 9:19
  • $\begingroup$ you mean we can prioritise the resource sets in three ways, (1) randomly, (2) according to how many unserved users they would serve and (3) based on the number of surviving conflicts they have? $\endgroup$
    – KGM
    Commented May 21, 2022 at 9:22
  • 1
    $\begingroup$ If you have $N_r$ resources, $N_s$ distinct resource sets and $N_u$ users, mapping resource sets to users that can take them would be $O(N_u \cdot N_s).$ I think identifying and recording conflicts would be $O(N_r \cdot N_s^2).$ Sorting the resource sets in priority order would be $O(N_s\log(N_s)).$ Making the assignments would be $O(N_s).$ So the dominant term would seem to be $O(N_r \cdot N_s^2).$ $\endgroup$
    – prubin
    Commented Aug 17, 2022 at 2:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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