1
$\begingroup$

I have a matrix which contains compatibility scores between objects. I have 56 objects, thus, the matrix dimensions are 56*56.

I need to group said objects in groups of 8 to 10 elements.

I have tried to use linear optimization to do that using a sample problem in Python:

prob = LpProblem("Grouping_Optimization", LpMaximize)
# thing i in group j
x = {(i, j): LpVariable(cat="Binary", name=f"x_{i}_{j}") for i in result_sum.index for j in result_sum.index}

# group j exists
y = {j: LpVariable(cat="Binary", name=f"y_{j}") for j in result_sum.index}

# objectice function
obj_terms = []#auxiliary
for i in result_sum.index:#thing
    for j in result_sum.index:#thing
        for k in result_sum.index:#group
            if i != j:#don't compare the same thing
                z = LpVariable(cat="Binary", name=f"z_{i}_{j}_{k}")
                prob += z <= x[i, k]  # z is only 1 if i is in group k
                prob += z <= x[j, k]  # z is only 1 if j is in group k
                obj_terms.append(score_matrix.loc[i, j] * z)# z is only 1 if i and j are in the same group

prob += lpSum(obj_terms)


# each thing is in exactly one group
for i in result_sum.index:
    prob += lpSum(x[i, j] for j in result_sum.index) == 1

# each group has at least 2 things and at most 3 things
for j in result_sum.index:
    prob += lpSum(x[i, j] for i in result_sum.index) >= 2 * y[j]
    prob += lpSum(x[i, j] for i in result_sum.index) <= 3 * y[j]

# Solve the problem
prob.solve()

This code seems to work with sample data. However, with real data (56*56) it is taking too long. I need to use a metaheuristic algorithm instead to solve the problem. However, I have never used them.

Can someone please give me a clue on how to do this?

Edit: As an example, let's consider this matrix as the compatibility scores

    A   B   C   D   E   F   G   H   I   J   K
A   0   1   5   3   7   8   9   5   3   4   5
B   1   0   2   8   9   0   2   7   5   3   9
C   5   2   0   2   8   7   3   5   9   9   8
D   3   8   2   0   5   1   4   7   9   5   1   
E   7   9   7   5   0   2   7   6   4   6   9
F   8   0   7   1   2   0   1   9   5   6   3
G   9   2   3   4   7   1   0   1   2   5   6
H   5   7   5   7   6   9   1   0   2   8   6
I   3   5   9   9   4   5   2   2   0   5   9   
J   4   3   9   5   6   6   5   8   5   0   2
K   5   9   8   1   9   3   6   6   9   2   0

Then, if I were looking for grouping in groups of three to five elements, one group could be ABC, whith a score of 1+5+2=8, this is the sum of the compatibilities between A and B, A and C and B and C.

$\endgroup$
8
  • $\begingroup$ Before using a metaheuristic there are at least 2 things you can try: 1/ use the SCIP solver 2/ Pre-compute all possible groups of 2 or 3 elements (or a subset of them) and select the best ones with a linear program (set partitioning problem). $\endgroup$
    – Kuifje
    Dec 5, 2023 at 13:01
  • $\begingroup$ Thanks for the suggestion, I will try the first option, but the second one seems above my programming level. $\endgroup$ Dec 5, 2023 at 13:04
  • 1
    $\begingroup$ I have edited the question to make it clearer, or at least I hope $\endgroup$ Dec 5, 2023 at 13:11
  • 1
    $\begingroup$ You have a lot of $z$ variables (for i, for j, for k). You should be able to write your objective with just $z[i, j] = 1$ iff $i$ and $j$ are in the same group and $y[j]$ the number of elements in the group of element $j$. $\endgroup$
    – fontanf
    Dec 5, 2023 at 13:58
  • 1
    $\begingroup$ Reading the beginning of your post, it sounds like your problem is exactly a clustering problem. Have you tried some of the clustering algorithms implemented in scikit learn? scikit-learn.org/stable/modules/clustering.html#clustering $\endgroup$
    – Stef
    Dec 5, 2023 at 17:55

2 Answers 2

2
$\begingroup$

I would first try the mixed-integer linear programming approach, but if you want a metaheuristic, one possibility is a random key genetic algorithm. Given your minimum and maximum cluster sizes, you need either six or seven clusters. Moreover, there are only four possible size patterns: seven clusters of eight each; two clusters of eight and four clusters of ten; one cluster of eight, two clusters of nine and three clusters of ten; or four clusters of nine and two clusters of ten.

The chromosome will be a permutation of the indices 1 through 56 plus a single integer with domain $\lbrace 1, 2, 3, 4\rbrace.$ To decode the chromosome into a solution, you permute your 56 objects into the order specified by the permutation part of the chromosome. You then use the integer gene to select the group size pattern and create the groups from the permuted objects, assuming that smaller groups come first. The fitness function (to be maximized) is your objective function.

$\endgroup$
6
  • $\begingroup$ So, If I have understood correctly, if I had just 10 people, some chromosomes could be 1112223333, another one could be 3333222111 and a third could be 1231231233. How could I then do the crossover and the mutation? $\endgroup$ Dec 7, 2023 at 8:12
  • 1
    $\begingroup$ I think you misunderstood. Let's assume 8 objects (people?) being split into two or three groups, with three possible groupings: (4, 4); (2, 3, 3); or (2, 2, 4). A typical chromosome might be 34165872|2 where the first eight integers are a permutation of 1,...,8 and the last integer (1, 2 or 3) picks the grouping pattern. The chromosome decodes to using the (2, 3, 3) pattern, putting 3 and 4 in the first group, 1 5 and 6 in the second group, and 2 7 and 8 in the third group. As for how crossover and mutation work, that's tricky, but there are GA solvers that know how to implement permutations. $\endgroup$
    – prubin
    Dec 7, 2023 at 16:39
  • 1
    $\begingroup$ An add on to my last point: I know of at least one GA than will let you use permutations of an integer sequence as a chromosome, but I don't think it can handle the extra digit for selecting the pattern. To get around that limitation, I would use permutations of 1 through 11, where 1 through 8 represent objects and 9 through 11 represent the three possible patterns I listed. To decode a chromosome, I would look for which of 9 through 11 came first in the permutation, use the corresponding pattern, and then divide up 1 through 8 using that pattern. $\endgroup$
    – prubin
    Dec 7, 2023 at 16:42
  • $\begingroup$ Thanks for your answer. This seems pretty complicated. I will try to understand and implement this. $\endgroup$ Dec 9, 2023 at 8:17
  • $\begingroup$ My advice is to find a good software program/library for GAs. I frequently code in R, for which a library named GA is available that implements permutation chromosomes. $\endgroup$
    – prubin
    Dec 9, 2023 at 17:19
0
$\begingroup$

You can generate all $\binom{n}{8}+\binom{n}{9}+\binom{n}{10} \in \mathcal{O}(n^4)$ subsets of $8,9,10$ elements. Let $\Omega$ denote the set of the indexes of these precomputed subsets. For each subset $S_i$, you can also precompute its total value $C_i$ by summing over each pairwise values. Then define a binary variable $\lambda_i$ that takes value $1$ if subset $S_i$ is selected. Then solve the following: $$ \max \sum_{i\in \Omega}C_i \lambda_i $$ subject to:

  • Each element $v$ must be in one selected group exactly: $$ \sum_{i\in \Omega, v\in S_i} \lambda_i = 1 \quad \forall v $$

You can find a very similar problem solved with PuLP here.

$\endgroup$

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.