The very general problem is (weakly) NP-complete if you want the optimal solution, however, in general there aren't arbitrarily large sibling cliques.
The problem can always be modeled as an integer linear program (ILP).
If you just want a good enough solution, then I would start with a greedy algorithm, followed by local search. You can always keep the local search (with random restarts) running over the night in hope for ever better solutions.
Since you seem to have added some more constraints in comments, if the constraints are really hard constraints, you can consider using an off-the-shelf ILP solver.
For illustrative purposes, I picked the first I could (cvxpy) find in a programming language I am familiar with (Python). I am not familiar with ILP solvers, so I have no idea if this is a good choice. (Note that it is not actually a solver, but an interface for several solvers.)
So I wrote a short example just to get you started. It can be done in about 50 lines.
There are $2 \cdot N$ variables:
- $N$ variables representing the $N$ students
- $N$ variables representing their genders (linked through a constraint)
There are two constraints:
- siblings need to be in the same partition
- a helper-constraint to make the balancing of genders simpler
The optimization is basically to optimize (minimize)
$$2 \cdot (N/2 - \sum{s})^2 + (N/2 - \sum{g})^2,$$
where $\sum{s}$ is the number of students put in partition 0 and $\sum{g}$ is the number of girls put in partition 0.
caveat emptor
from collections import namedtuple, Counter
import random
import cvxpy as cp
Student = namedtuple("Student", "name level gender")
def generate_students(N=100):
# generate random data
students = [Student(i, 1, random.choice("MF")) for i in range(N)]
siblings = []
for i in range(0, N // 2, 3):
siblings += [(i, i + 1), (i, i + 2), (i + 1, i + 2)]
return students, siblings
def create_variables(students):
"""Return stud_var and gender_var.
These will be constrained to be set to the same value, i.e.
stud[i] == gender[i].
This is to ensure that we can easily count gender-difference in
addition to "normal" difference.
"""
stud_vars = [cp.Variable(1, boolean=True) for s in students]
gender_vars = [cp.Variable(1, boolean=True) for s in students]
return stud_vars, gender_vars
def create_constraints(stud_vars, gend_vars, students, siblings):
stud_const = [stud_vars[l] == stud_vars[r] for (l, r) in siblings]
link = [stud_vars[i] == gend_vars[i] for i in range(len(stud_vars))]
return stud_const
def create_objective(stud_vars, gend_vars):
mid = len(stud_vars) // 2
objective = cp.Minimize(
2 * (mid - cp.sum(stud_vars)) ** 2 + (mid - cp.sum(gend_vars)) ** 2
)
return objective
students, siblings = generate_students()
stud_vars, gender_vars = create_variables(students)
constraints = create_constraints(stud_vars, gender_vars, students, siblings)
objective = create_objective(stud_vars, gender_vars)
prob = cp.Problem(objective, constraints)
result = prob.solve()
if result is None:
exit("Could not find feasible solution.")
print(round(result))
print(Counter(int(round(e.value[0])) for e in stud_vars))
def get_gender_count(partition):
lst = [
students[idx].gender
for (idx, s) in enumerate(stud_vars)
if round(s.value[0]) == partition
]
return Counter(lst)
print("Partition 0:", get_gender_count(0))
print("Partition 1:", get_gender_count(1))
# for idx, e in enumerate(stud_vars):
# print(students[idx], "\tPartition", int(round(e.value[0])))
for (l, r) in siblings:
lv = int(round(stud_vars[l].value[0]))
rv = int(round(stud_vars[r].value[0]))
assert lv == rv
Running the snippet output:
(e375) [ubuntu ~/textnik]$ time python textnik.py
297.0
Counter({0: 52, 1: 48})
Partition 0: Counter({'F': 27, 'M': 25})
Partition 1: Counter({'F': 25, 'M': 23})
real 0m4,060s
user 0m4,926s
sys 0m1,189s
meaning that it put 52 students in one group and 48 in the other, with 27/25 F/M in the first group and 25/23 F/M in the other group.
All the siblings should be in the same group by constraints.
