2
$\begingroup$

I need to find an algorithm for the following problem. Any idea to which kind of algorithm to look for as starting point is welcomed. Should I look for a graph algorithm? Combinatorial problem? Mathematical or dynamic programming?

Objective:

I have a set of 48 classes with 25 students each. I need to divide each class in two groups, lets call them A and B. There are the following constrains:

  • Some students have brothers/sisters in other classes. I need that all brother/sister be in the same partition A or B. This should be a hard condition that must be fulfilled by the solution.
  • A second constrain is that girls and boys should be equally divided in the both partitions of each class. If class 12 has 11 boys and 14 girls; the partition should be: partition 12A with 6 boys and 12 girls and partition 12B with 5 boys and 12 girls. This constrain is not hard, it may be violated by the solution slightly.

What if the number of constrains increases a lot.

In the comments, it is suggested to use a greedy algorithm, because it is easy to move students with no constrains (no siblings) from one partition to another. What to do if the number of constrains is very high. For some reason we have a lot of constrains of the type: studentA can't be in the same partition of studentB, ... What algorithmic approach is best?

Some numbers:

There are around 1200 students, divided in 16 years. Each year has 3 classes. The ratio girls and boys is, as expected, 1:1. There should be between 500 and 600 brother/sister relations.

Background:

Due to the COVID19 pandemic it is possible that next school year, students may be separated in two groups. These groups will alternate going to school and staying at home. To easy the logistics for parents, it may be desirable to have all siblings in the same group, going to school or staying at home.

$\endgroup$
4
  • $\begingroup$ Since you don't seem to care too much about an optimal algorithm, I would just create a greedy algorithm combined with a small local search after. I don't think you should be too far away given that it so easy to move single persons around (I'm guessing). $\endgroup$ – Pål GD May 5 '20 at 14:55
  • $\begingroup$ If you want an optimal solution, though, you might have run into an NP-hard problem, but there are solvers available for this if you model it through an integer linear program. $\endgroup$ – Pål GD May 5 '20 at 14:56
  • $\begingroup$ Well, actually, since the "graph" is a cluster graph of cliques whose sizes are bounded by something like five, it's possibly not NP-complete at all. $\endgroup$ – Pål GD May 5 '20 at 20:25
  • $\begingroup$ @PålGD Thanks for taking the time to think about this. What approach would you take if the number of constrains increases? Suppose that we add constrains like studentA can't go in the same partition of studentB, and so on for a lot of students. $\endgroup$ – TeXtnik May 6 '20 at 7:53
2
$\begingroup$

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:

  1. $N$ variables representing the $N$ students
  2. $N$ variables representing their genders (linked through a constraint)

There are two constraints:

  1. siblings need to be in the same partition
  2. 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.

$\endgroup$
5
  • $\begingroup$ Thanks. I think I understand how to define the goal function. This was one of my biggest issue with the integer optimisation approach. One detail that it maybe not very clear in the problem description is that the student are divided in classes/level and that the gender parity should be maintained in the partition of each class; not globally. It is a very good starting point. $\endgroup$ – TeXtnik May 7 '20 at 6:23
  • $\begingroup$ I guess that for each class I should add a term in the optimization function similar to $(n/2-\sum g)^2$, where n is the size of each class and the sum is done for the member of the class. $\endgroup$ – TeXtnik May 7 '20 at 9:20
  • $\begingroup$ Yes, that is an option, but it's very difficult to predict how well it will work. You are getting very close to needing multi-objective Integer Linear Program, which I don't know if this framework (or other) supports. $\endgroup$ – Pål GD May 7 '20 at 15:16
  • $\begingroup$ You can also consider trying a genetic algorithm which is a kind of local search, but which is quite easy to model with and play around in. $\endgroup$ – Pål GD May 7 '20 at 15:18
  • $\begingroup$ Thanks very much. I would do some research in these direction." $\endgroup$ – TeXtnik May 11 '20 at 11:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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