Group Division for Minimizing the Stranger People We plan to take place a welcome party for new 13 employees.
The party includes the networking event and
it is composed of three periods (which allows the change of employees by a period) and
we divide them into three groups in each period.
In other words, all employees exactly join the three periods.
Our main objective is "minimizing the number of members who have not faced to others (,say a stranger)".
If A is together with B in a period, we define A and B was faced each other.
In short, we'd like to communicate as many employees as can while three periods.
We have additional constraints:

*

*Three guys A, B and C won't change the group
e.g.,

p1: A E K H I (G1) B D F G L (G2) C J M (G3)
p2: A D K F H (G1) B I (G2) C E F G J M L (G3)
p3: A D E F G H I J K L M (G1) B (G2) C (G3)
This allocation is obviously wasteful since B hasn't met E, H or J for instance.

*

*The number of members in each group must be almost the same (within one difference).

Do you know the efficient algorithm to find such an allocation?
 A: You obviously cannot cover pairs AB, AC, and BC.  But you can cover all other pairs by keeping everybody else together:
p1: A D E F G H I J K L M (G1) B (G2) C (G3)
p2: A (G1) B D E F G H I J K L M (G2) C (G3)
p3: A (G1) B (G2) C D E F G H I J K L M (G3)


With the additional constraint on group sizes, you can cover a maximum of $58$ of the $\binom{13}{2}=78$ pairs as follows, where I have renamed the employees as $1,\dots,13$:
{1,5,6,13} {2,4,7,11} {3,8,9,10,12}
{1,4,9,12} {2,6,8,10,13} {3,5,7,11}
{1,7,8,10,11} {2,5,9,12} {3,4,6,13}

I used integer linear programming, with three sets of binary decision variables:

*

*$x_{e,g,p}$ indicates whether employee $e$ is assigned to group $g$ in period $p$

*$y_{e_1,e_2,g,p}$ indicates whether employees $e_1$ and $e_2$ are assigned to group $g$ in period $p$

*$z_{e_1,e_2}$ indicates whether employees $e_1$ and $e_2$ are ever assigned to the same group

The problem is to maximize $\sum_{e_1<e_2} z_{e_1,e_2}$ subject to:
\begin{align}
\sum_g x_{e,g,p} &= 1 &&\text{for all $e$ and $p$} \tag1 \\ 
y_{e_1,e_2,g,p} &\le x_{e_1,g,p} &&\text{for all $e_1<e_2$, $g$, and $p$} \tag2 \\ 
y_{e_1,e_2,g,p} &\le x_{e_2,g,p} &&\text{for all $e_1<e_2$, $g$, and $p$} \tag3 \\ 
z_{e_1,e_2} &\le \sum_{g,p} y_{e_1,e_2,g,p} &&\text{for all $e_1<e_2$} \tag4 \\
-1 \le \sum_e x_{e,g_1,p} - \sum_e x_{e,g_2,p} &\le 1 &&\text{for all $g_1<g_2$ and $p$} \tag5
\end{align}
Constraint $(1)$ assigns each employee to exactly one group per period.
Constraints $(2)$ and $(3)$ enforce $y_{e_1,e_2,g,p} \implies (x_{e_1,g,p} \land x_{e_2,g,p})$.
Constraint $(4)$ enforces $z_{e_1,e_2} \implies \bigvee_{g,p} y_{e_1,e_2,g,p}$.
Constraint $(5)$ restricts the group sizes to differ by no more than 1 in each period.
To force the assignments of the first three employees to different groups, you can fix $x_{e,e,p} = 1$ for $e\in\{1,2,3\}$ and all $p$.

Here's an alternative formulation that can be faster to solve, depending on the input parameters.  Let $\ell$ and $u$ be bounds on the group size, and let $G=\{g \subset \{1,\dots,n\}: \ell \le |g| \le u\}$ be the set of all groups that respect these bounds.  For your example instance, take $\ell=\lfloor13/3\rfloor=4$ and $u=\lceil13/3\rceil=5$.  Let $G_e$ be the groups that contain employee $e$.
Define two sets of binary decision variables:

*

*$x_{g,p}$ indicates whether group $g$ is used in period $p$

*$z_{e_1,e_2}$ indicates whether employees $e_1$ and $e_2$ are ever assigned to the same group

The problem is to maximize $\sum_{e_1<e_2} z_{e_1,e_2}$ subject to:
\begin{align}
\sum_{g\in G_e} x_{g,p} &= 1 &&\text{for all $e$ and $p$} \tag6 \\ 
z_{e_1,e_2} &\le \sum_{g\in G_{e_1} \cap G_{e_2},p} x_{g,p} &&\text{for all $e_1<e_2$} \tag7
\end{align}
Constraint $(6)$ assigns each employee to exactly one group per period.
Constraint $(7)$ enforces $z_{e_1,e_2} \implies \bigvee_{g\in G_{e_1} \cap G_{e_2},p} x_{g,p}$.
To force the assignments of the first three employees to different groups, you can omit groups $g$ with $|g \cap \{1,2,3\}| > 1$.
