Formulating an equation for a group sorting program. I'm trying to formulate an equation/algorithm to solve this problem (for a program I'm writing):
Rules:


*

*A person, p, that is to be sorted can exclude n amount of people from the list. The excluded people, n, cannot be in the same group as p.

*The list will contain around 100-150 people.

*A group should contain 5-7 people (ideally 6)
My current thoughts:


*

*Take the list count and divide it by 6, which will give me the amount of groups.

*Feed people into the groups untill an exclusion occurs. When this happens, try to move the mismatched persons into other groups, based on some sort of score-system untill proper groups are formed.
However, I still feel like I need to put a limit on the amount of people allowed to be excluded per person.
My question is basically how I would express this mathematically to figure out how many people a certain person can exclude to make this endeavor possible. Ideas and thoughts are also appriciated!
 A: In general, I think it is very difficult to analyse the feasibility of the formation of these groups based on the number of excluded members. Because you allow variation in the group size, and if we assume that $ n \ll |N| $ where $ |N| $ is the total number of people to be grouped, I think feasible groups should exit. This is only intuition, and it probably would be straightforward to construct instances where this is not true.
In any case, we can still analyse your problem. Probably the best way to model your problem is to consider a bin packing problem. Formally, we would have
$$  B  = \sum_{y=1}^n y_i $$
$$ s.t. B \geq 1$$
$$ \sum_{j=1}^n a_j x_{ij} \leq Vy_i\ \forall j$$
$$ \sum_{i=1}^n x_{ij} = 1 \ \forall i$$
$$ y_i \in {0,1} \ \forall i $$
$$ x_{ij} \in \{0,1\} \ \forall i \  \forall j $$
Such a formulation means essentially trying to fit items $j \in  \{1,..,n\}$ with weights $\ a_1,a_2,...,a_n\ $ into smallest number of "bins" that can contain at most $V$ units of weight.
In your problem, we could say that each person represents an item and has a weight of $1/7$, as maximum $7$ people can be grouped together. Similarly, the bin is represented by a group with $V=7$
You can read more about these problems in Wikipedia. https://en.wikipedia.org/wiki/Bin_packing_problem
Obviously, your problem is not a standard bin packing problem. The normal version assumes that any item can be packed with any other item, as long as the weight constraints are respected. In addition to the maximum group size, your problem involves restrictions on the group composition. This makes finding solutions more difficult (and the initial problem is already quite difficult). You could read for example www.eecs.berkeley.edu/Pubs/TechRpts/2005/CSD-05-1378.pdf that considers bin packing problem where some items cannot be packed together.
Already in you current approach, you have correctly identified the need for coming up with a good heuristic. The bin packing problem is NP-hard and solving it to optimality with any reasonably sized problem instance is going to take a lot of time. With your specific problem of grouping restrictions, the complexity is still increased. Thus, you are on the right track with your solution approach. Do some additional research with the above resources and the correct name of the problem, and I am sure you can arrive at a good solution.
