I have a group of people that I need to split up into subgroups. The subgroups do not all have to be the same size, but can be no smaller than 5 and no larger than 10. I have created a matrix (in excel) where each possible pairing of two individuals is assigned an affinity score from 0 to 5. Individuals that have a score of 5 must be in the same group (such as for spouses/partners), while individuals that have a score of 0 cannot be in the same subgroup under any circumstance. I need an optimized configuration of subgroupings.

Below is the most recent iteration of code, which so far has failed to produce any solutions (and in fact does not even provide the requested status updates every 120 seconds). Previous iterations had moved very slowly, and when I ctrl+c'd the terminal the solution insisted on making subgroups of only one size (19 groups 5) when it was a set of 95 people. I have since reduced the people to 93 and changed the code, so I am not sure if the code is unable to handle a number that doesn't divide into an equal number of subgroups, or if there are other issues at play. I'm also wondering if PuLP would be better for this instead of ortools. Here is the script:

from ortools.sat.python import cp_model
import numpy as np
import pandas as pd
import time

def load_affinity_matrix(file_path):
    df = pd.read_excel(file_path, index_col=0)
    return df.to_numpy(), df.index.tolist()

def optimize_groups(affinity_matrix, min_size=5, max_size=10):
    num_people = len(affinity_matrix)
    model = cp_model.CpModel()
    
    # Decision Variables: x[i][g] is 1 if person i is in group g
    max_groups = num_people // min_size  # Upper bound on the number of groups
    x = {}  # Dictionary to hold variables
    for i in range(num_people):
        for g in range(max_groups):
            x[i, g] = model.NewBoolVar(f'x_{i}_{g}')
    
    # Constraint 1: Each person must be in exactly one group
    for i in range(num_people):
        model.Add(sum(x[i, g] for g in range(max_groups)) == 1)
    
    # Constraint 2: Group sizes must be within limits
    for g in range(max_groups):
        model.Add(sum(x[i, g] for i in range(num_people)) >= min_size)
        model.Add(sum(x[i, g] for i in range(num_people)) <= max_size)
    
    # Constraint 3: Handle affinity rules
    for i in range(num_people):
        for j in range(i + 1, num_people):
            if affinity_matrix[i][j] == 5:  # Must be together
                for g in range(max_groups):
                    model.Add(x[i, g] == x[j, g])
            elif affinity_matrix[i][j] == 0:  # Cannot be together
                for g in range(max_groups):
                    model.Add(x[i, g] + x[j, g] <= 1)
    
    # Objective: Maximize total affinity within groups
    objective_terms = []
    for g in range(max_groups):
        for i in range(num_people):
            for j in range(i + 1, num_people):
                if affinity_matrix[i][j] > 0:
                    affinity_value = affinity_matrix[i][j]
                    pair_var = model.NewBoolVar(f'pair_{i}_{j}_{g}')
                    model.AddMultiplicationEquality(pair_var, [x[i, g], x[j, g]])
                    objective_terms.append(affinity_value * pair_var)
    
    model.Maximize(sum(objective_terms))
    
    # Solve
    solver = cp_model.CpSolver()
    solver.parameters.num_search_workers = 8  # Optimized for Apple M2 chip
    
    print("Starting optimization...")
    start_time = time.time()
    
    class ProgressCallback(cp_model.CpSolverSolutionCallback):
        def __init__(self, start_time, log_interval=300):
            super().__init__()
            self.start_time = start_time
            self.log_interval = log_interval
            self.last_log_time = start_time
        
        def on_solution_callback(self):
            current_time = time.time()
            if current_time - self.last_log_time >= self.log_interval:
                print(f"Still optimizing... {round((current_time - self.start_time) / 60, 2)} minutes elapsed.")
                self.last_log_time = current_time
    
    callback = ProgressCallback(start_time)
    solver.parameters.log_search_progress = False  # Disable continuous logging
    status = solver.Solve(model, callback)
    print("Solver finished.")
    
    if status in (cp_model.FEASIBLE, cp_model.OPTIMAL):
        groups = [[] for _ in range(max_groups)]
        for i in range(num_people):
            for g in range(max_groups):
                if solver.Value(x[i, g]) == 1:
                    groups[g].append(i)
        
        # Convert indices to actual names before returning
        return [[people_names[i] for i in group] for group in groups if group]  # Remove empty groups
    else:
        return None

# Example usage
affinity_matrix, people_names = load_affinity_matrix('/Users/myname/Documents/affinity_matrix.xlsx')
groups = optimize_groups(affinity_matrix)

# Print groups with names
if groups:
    for idx, group in enumerate(groups, start=1):
        print(f"Group {idx}: {group}")
else:
    print("No valid grouping found.")

Here is a sample of the data:

I have a group of people that I need to split up into subgroups. The subgroups do not all have to be the same size, but can be no smaller than 5 and no larger than 10. I have created a matrix (in excel) where each possible pairing of two individuals is assigned an affinity score from 0 to 5. Individuals that have a score of 5 must be in the same group (such as for spouses/partners), while individuals that have a score of 0 cannot be in the same subgroup under any circumstance. I need an optimized configuration of subgroupings.

Below is the most recent iteration of code, which so far has failed to produce any solutions (and in fact does not even provide the requested status updates every 120 seconds). Previous iterations had moved very slowly, and when I ctrl+c'd the terminal the solution insisted on making subgroups of only one size (19 groups 5) when it was a set of 95 people. I have since reduced the people to 93 and changed the code, so I am not sure if the code is unable to handle a number that doesn't divide into an equal number of subgroups, or if there are other issues at play. I'm also wondering if PuLP would be better for this instead of ortools. Here is the script:

from ortools.sat.python import cp_model
import numpy as np
import pandas as pd
import time

def load_affinity_matrix(file_path):
    df = pd.read_excel(file_path, index_col=0)
    return df.to_numpy(), df.index.tolist()

def optimize_groups(affinity_matrix, min_size=5, max_size=10):
    num_people = len(affinity_matrix)
    model = cp_model.CpModel()
    
    # Decision Variables: x[i][g] is 1 if person i is in group g
    max_groups = num_people // min_size  # Upper bound on the number of groups
    x = {}  # Dictionary to hold variables
    for i in range(num_people):
        for g in range(max_groups):
            x[i, g] = model.NewBoolVar(f'x_{i}_{g}')
    
    # Constraint 1: Each person must be in exactly one group
    for i in range(num_people):
        model.Add(sum(x[i, g] for g in range(max_groups)) == 1)
    
    # Constraint 2: Group sizes must be within limits
    for g in range(max_groups):
        model.Add(sum(x[i, g] for i in range(num_people)) >= min_size)
        model.Add(sum(x[i, g] for i in range(num_people)) <= max_size)
    
    # Constraint 3: Handle affinity rules
    for i in range(num_people):
        for j in range(i + 1, num_people):
            if affinity_matrix[i][j] == 5:  # Must be together
                for g in range(max_groups):
                    model.Add(x[i, g] == x[j, g])
            elif affinity_matrix[i][j] == 0:  # Cannot be together
                for g in range(max_groups):
                    model.Add(x[i, g] + x[j, g] <= 1)
    
    # Objective: Maximize total affinity within groups
    objective_terms = []
    for g in range(max_groups):
        for i in range(num_people):
            for j in range(i + 1, num_people):
                if affinity_matrix[i][j] > 0:
                    affinity_value = affinity_matrix[i][j]
                    pair_var = model.NewBoolVar(f'pair_{i}_{j}_{g}')
                    model.AddMultiplicationEquality(pair_var, [x[i, g], x[j, g]])
                    objective_terms.append(affinity_value * pair_var)
    
    model.Maximize(sum(objective_terms))
    
    # Solve
    solver = cp_model.CpSolver()
    solver.parameters.num_search_workers = 8  # Optimized for Apple M2 chip
    
    print("Starting optimization...")
    start_time = time.time()
    
    class ProgressCallback(cp_model.CpSolverSolutionCallback):
        def __init__(self, start_time, log_interval=300):
            super().__init__()
            self.start_time = start_time
            self.log_interval = log_interval
            self.last_log_time = start_time
        
        def on_solution_callback(self):
            current_time = time.time()
            if current_time - self.last_log_time >= self.log_interval:
                print(f"Still optimizing... {round((current_time - self.start_time) / 60, 2)} minutes elapsed.")
                self.last_log_time = current_time
    
    callback = ProgressCallback(start_time)
    solver.parameters.log_search_progress = False  # Disable continuous logging
    status = solver.Solve(model, callback)
    print("Solver finished.")
    
    if status in (cp_model.FEASIBLE, cp_model.OPTIMAL):
        groups = [[] for _ in range(max_groups)]
        for i in range(num_people):
            for g in range(max_groups):
                if solver.Value(x[i, g]) == 1:
                    groups[g].append(i)
        
        # Convert indices to actual names before returning
        return [[people_names[i] for i in group] for group in groups if group]  # Remove empty groups
    else:
        return None

# Example usage
affinity_matrix, people_names = load_affinity_matrix('/Users/myname/Documents/affinity_matrix.xlsx')
groups = optimize_groups(affinity_matrix)

# Print groups with names
if groups:
    for idx, group in enumerate(groups, start=1):
        print(f"Group {idx}: {group}")
else:
    print("No valid grouping found.")

Here is a sample of the data:

• python
• combinatorics
• or-tools
• mixed-integer-programming
• cp-sat

• If I understood you correctly, this example of a wedding tables’ seating from ortools might be interesting. It also uses the CP-SAT solver (for Constraint Programming as an alternative to MILP). The main issue is to make sure your constraints are correctly formulated regardless CP or MILP. You may also want to test your model with a smaller group of people, first. – Anonymous Commented Mar 18 at 4:16
• @Anonymous wedding table seating is precisely what I am trying to solve for. I've since come to learn that "Combinatorial Optimization" seems to be the most accurate descriptor for the type of problem I'm trying to solve. That github code is interesting, but I don't like that it has the number of tables and table capacity as constraints - I want the number of tables to be dynamic and the number of people per table to be range bound rather than fixed. Also, I noticed that it simply includes the relevant matrix as part of the code - is this faster than allowing it to pull data from a .csv/.xlsx? – anon_group_optimizer Commented Mar 18 at 14:06
• 1 You may want to walk thru the GitHub code (and maybe also compare it to your code) to get an understanding how it works. Then you should be able to adjust it to your use case. Rgrd your question about the solver performance: I reckon, the matrix as part of the code makes it easier for others to follow the example. The solver does not care where the data comes from. It takes your model incl. the assigned data and does its job. Btw, I just noticed the matrix you added has decimals. You may want to have look here too: developers.google/optimization/cp/cp_solver – Anonymous Commented Mar 19 at 11:01

3 Answers 3

Since you didn't provide a sample of the input data, I made it up, so you'll have to adapt the code to your needs (if it works for you).

groups = [
    [ "e", 2 ],
    [ "g", 4 ],
    [ "b", 5 ],
    [ "l", 1 ],
    [ "j", 2 ],
    [ "f", 4 ],
    [ "m", 1 ],
    [ "i", 3 ],
    [ "c", 5 ],
    [ "n", 1 ],
    [ "o", 0 ],
    [ "k", 2 ],
    [ "p", 0 ],
    [ "h", 3 ],
    [ "q", 0 ],
    [ "a", 5 ],
    [ "r", 0 ],
]

maxPersons = 4
numberOfSubGroups = 5

def sortByAffinity( gps ):
    out = []
    unorderer = True
    while( unorderer ):
        unorderer = False
        for i in range( len( gps ) - 1 ):
            if gps[ i ][ 1 ] > gps[ i + 1 ][ 1 ]:
                aux = gps[ i ]
                gps[ i ] = gps[ i + 1 ]
                gps[ i + 1 ] = aux
                unorderer = True

def divideByAffinity( gps ):
    outer = []
    aux = [ gps[ 0 ] ]
    affinity = gps[ 0 ][ 1 ]
    for i in range( 1, len( gps )):
        if gps[ i ][ 1 ] == affinity:
            aux.append(( gps[ i ]))
        else:
            outer.append( aux )
            aux = [ gps[ i ]]
            affinity = gps[ i ][ 1 ]
    outer.append( aux )
    return outer
    
def createSubGroups( gps ):
    outer = [] 
    for i in range( numberOfSubGroups ):
        outer.append( [] )
        
    data = gps[ len( gps ) - 1 ]
    for i in range(  len( data ) ):  ## add "5's"
        outer[ 0 ].append( data[ i ] )

    data = gps[ 0 ]
    k = 0
    for i in range( len( data )):  ## add "0's"
        if i == 0 :
            if len( outer[ k ] ) >= maxPersons:
                k = 1 
        outer[ k + i ].append( data[ i ] )
        
    for x in range( 1, len( gps ) -1 ):  ## add others
        data = gps[ x ]
        for i in range( len( data )):
            for k in range( len( outer )):
                if len( outer[ k ] ) < maxPersons:
                    outer[ k ].append( data[ i ] )
                    break
    return outer

sortByAffinity( groups )     
subGroups = createSubGroups( divideByAffinity( groups ))

The first thing to do is to calculate the number of subgroups and their capacity.

Then we sort the people by affinity with sortByAffinity, I implemented the bubble algorithm because it is the easiest to write, you should replace it with the one you think is most convenient.

Next, we separate our ordered list into subgroups of people with the same affinity using divideByAffinity. This method receives the ordered list and, as it goes through it, loads the items that have the same affinity into an auxiliary list. When one appears that does not, it loads the auxiliary list into the output list, updates the affinity value, and continues.

After this, we only have to create the subgroups, we do it using createSubGroups

Within this method, we start by creating the list that we have to return, and we load the empty subgroups into it.

Then we assign data the last sublist of gps (it contains people with affinity "5"), we go through it with the for and we load each item, in the first subgroup of the outer, fulfilling the premise that all must be in the same subgroup.

Once the previous step is completed, we continue entering the people with affinity "0", who must be in different groups. To do this, we load the content of the first subgroup of gps into data and go through it, check if it is possible to add to the first subgroup (if not, we increase "k"), and load each item into a different subgroup.

Finally, we have to enter the rest, with the first ffor we go through the subgroups of gps, excluding the first and the last, the second goes through the data within them, and the third, iterates over the output list looking for subgroups that are not full, and proceeding to add the data to them.

Needless to say, this code can be optimized; it's just a guide that I hope will help you get what you need.

So I got some time to test your code @Colab with a smaller group of 20 persons and defined the affinity matrix with code (instead of loading from an xlsx file):

# 20 People names
people_names = [
    "Alice", "Bob", "Charlie", "David", "Eve", "Frank", "Grace", "Hank", "Ivy", "Jack",
    "Kate", "Leo", "Mia", "Nick", "Olivia", "Paul", "Quinn", "Rachel", "Steve", "Tina"
]

# Generate a symmetric affinity matrix (values 0-5, 0 on the diagonal)
np.random.seed(42)  # For reproducibility
affinity_matrix = np.random.randint(0, 6, (20, 20))
np.fill_diagonal(affinity_matrix, 0)  # No self-affinity
affinity_matrix = (affinity_matrix + affinity_matrix.T) // 2  # Make it symmetric

# Run optimization
groups = optimize_groups(affinity_matrix, min_size=3, max_size=6)

# Print results
if groups:
    for idx, group in enumerate(groups, start=1):
        print(f"Group {idx}: {group}")
else:
    print("No valid grouping found.")

… and got a result after approx. 50s.
Basically, the code works as expected, but not very efficiently.

Going thru your code, I noticed that you make use of .add_multiplication_equality() quite a lot.
While convenient, .add_multiplication_equality() is rather costly.

In this case, an alternative, linear formulation helps to reduce the solver time by an order of magnitude:

model.add(pair_var <= x[i, g])
model.add(pair_var <= x[j, g])
model.add(pair_var >= x[i, g] + x[j, g] - 1)

… and produces the result after 2s-5s (also @Colab).

As mentioned in my previous comments, you may also want to have a closer look at the example of a wedding tables’ seating from ortools for further inspiration and improvement potentials.

As an alternative to the ortools example I provided in my comment:

Recently, I came across Clingo ASP which makes it rather easy to formulate such combinatorial problems.

This PoC includes 4*26 persons, thereof:

• 26x couples to be grouped together
• 26x ‘avoid’ to be grouped in different groups
• 26x ‘company’ to be grouped together as many as possible

Further constraints:

• 16 groups
• group size not less than 5
• . . . and not more than 10

% Define 4*26 persons (to simplify using a1,a2,a3,a4,...,z1,z2,z3,z4)
person(a1; a2; a3; a4; b1; b2; b3; b4; c1; c2; c3; c4;
       d1; d2; d3; d4; e1; e2; e3; e4; f1; f2; f3; f4;
       g1; g2; g3; g4; h1; h2; h3; h4; i1; i2; i3; i4;
       j1; j2; j3; j4; k1; k2; k3; k4; l1; l2; l3; l4;
       m1; m2; m3; m4; n1; n2; n3; n4; o1; o2; o3; o4;
       p1; p2; p3; p4; q1; q2; q3; q4; r1; r2; r3; r4;
       s1; s2; s3; s4; t1; t2; t3; t4; u1; u2; u3; u4;
       v1; v2; v3; v4; w1; w2; w3; w4; x1; x2; x3; x4;
       y1; y2; y3; y4; z1; z2; z3; z4).

% Define 26 couples (x1 and x2 must be in the same group)
couple(a1,a2). couple(b1,b2). couple(c1,c2). couple(d1,d2). couple(e1,e2).
couple(f1,f2). couple(g1,g2). couple(h1,h2). couple(i1,i2). couple(j1,j2).
couple(k1,k2). couple(l1,l2). couple(m1,m2). couple(n1,n2). couple(o1,o2).
couple(p1,p2). couple(q1,q2). couple(r1,r2). couple(s1,s2). couple(t1,t2).
couple(u1,u2). couple(v1,v2). couple(w1,w2). couple(x1,x2). couple(y1,y2).
couple(z1,z2).

% Define 26 avoid relationships (x1 and x4 must be in different groups)
avoid(a1,a4). avoid(b1,b4). avoid(c1,c4). avoid(d1,d4). avoid(e1,e4).
avoid(f1,f4). avoid(g1,g4). avoid(h1,h4). avoid(i1,i4). avoid(j1,j4).
avoid(k1,k4). avoid(l1,l4). avoid(m1,m4). avoid(n1,n4). avoid(o1,o4).
avoid(p1,p4). avoid(q1,q4). avoid(r1,r4). avoid(s1,s4). avoid(t1,t4).
avoid(u1,u4). avoid(v1,v4). avoid(w1,w4). avoid(x1,x4). avoid(y1,y4).
avoid(z1,z4).

% Define 26 company relationships (x2 and x3 should preferably be in the same group)
company(a2,a3). company(b2,b3). company(c2,c3). company(d2,d3). company(e2,e3).
company(f2,f3). company(g2,g3). company(h2,h3). company(i2,i3). company(j2,j3).
company(k2,k3). company(l2,l3). company(m2,m3). company(n2,n3). company(o2,o3).
company(p2,p3). company(q2,q3). company(r2,r3). company(s2,s3). company(t2,t3).
company(u2,u3). company(v2,v3). company(w2,w3). company(x2,x3). company(y2,y3).
company(z2,z3).

% Define 16 groups
group(1..16).

% Assign each person to exactly one group
{ assign(P, G) : group(G) } = 1 :- person(P).

% Assign each group to 5-10 persons
5 { assign(P, G) :  person(P) } 10 :- group(G).

% Couples must be in the same group
assign(P, G) :- couple(P, Q), assign(Q, G).

% Persons in an avoid relationship must be in different groups
:- avoid(P, Q), assign(P, G), assign(Q, G).

% Maximization function to assign company pairs to same group
#maximize { 1, P, Q: company(P, Q), assign(P, G), assign(Q, G) }.

#show assign/2.

Output: (copy & paste to run the code online here)

clingo version 5.7.2 (6bd7584d)
Reading from stdin
Solving...
Answer: 1
assign(z1,9) assign(z2,9) assign(y1,8) assign(y2,8) assign(x1,15) assign(x2,15) assign(w1,14) assign(w2,14) assign(v1,15) assign(v2,15) assign(u1,5) assign(u2,5) assign(t1,8) assign(t2,8) assign(s1,11) assign(s2,11) assign(r1,16) assign(r2,16) assign(q1,9) assign(q2,9) assign(p1,15) assign(p2,15) assign(o1,12) assign(o2,12) assign(n1,8) assign(n2,8) assign(m1,14) assign(m2,14) assign(l1,11) assign(l2,11) assign(k1,5) assign(k2,5) assign(j1,9) assign(j2,9) assign(i1,9) assign(i2,9) assign(h1,9) assign(h2,9) assign(g1,10) assign(g2,10) assign(f1,16) assign(f2,16) assign(e1,16) assign(e2,16) assign(d1,12) assign(d2,12) assign(c1,12) assign(c2,12) assign(b1,10) assign(b2,10) assign(a1,12) assign(a2,12) assign(a3,13) assign(b3,13) assign(c3,1) assign(d3,1) assign(e3,13) assign(f3,13) assign(g3,4) assign(h3,13) assign(i3,4) assign(j3,4) assign(k3,4) assign(l3,1) assign(m3,14) assign(n3,11) assign(o3,2) assign(p3,2) assign(q3,2) assign(r3,2) assign(s3,6) assign(t3,2) assign(u3,6) assign(v3,6) assign(w3,6) assign(x3,6) assign(y3,1) assign(z3,1) assign(a4,3) assign(b4,3) assign(h4,3) assign(i4,3) assign(j4,3) assign(z4,4) assign(p4,5) assign(q4,5) assign(r4,5) assign(t4,5) assign(c4,7) assign(d4,7) assign(e4,7) assign(f4,7) assign(g4,7) assign(v4,10) assign(u4,12) assign(w4,12) assign(k4,15) assign(l4,15) assign(m4,15) assign(o4,15) assign(n4,16) assign(s4,16) assign(x4,16) assign(y4,16)
Optimization: -1
Answer: 2
assign(z1,9) assign(z2,9) assign(y1,8) assign(y2,8) assign(x1,15) assign(x2,15) assign(w1,14) assign(w2,14) assign(v1,15) assign(v2,15) assign(u1,5) assign(u2,5) assign(t1,8) assign(t2,8) assign(s1,11) assign(s2,11) assign(r1,16) assign(r2,16) assign(q1,9) assign(q2,9) assign(p1,15) assign(p2,15) assign(o1,12) assign(o2,12) assign(n1,8) assign(n2,8) assign(m1,14) assign(m2,14) assign(l1,11) assign(l2,11) assign(k1,5) assign(k2,5) assign(j1,9) assign(j2,9) assign(i1,9) assign(i2,9) assign(h1,9) assign(h2,9) assign(g1,10) assign(g2,10) assign(f1,16) assign(f2,16) assign(e1,16) assign(e2,16) assign(d1,12) assign(d2,12) assign(c1,12) assign(c2,12) assign(b1,10) assign(b2,10) assign(a1,12) assign(a2,12) assign(a3,13) assign(b3,13) assign(c3,1) assign(d3,1) assign(e3,13) assign(f3,13) assign(g3,4) assign(h3,13) assign(i3,4) assign(j3,4) assign(k3,5) assign(l3,1) assign(m3,14) assign(n3,11) assign(o3,2) assign(p3,2) assign(q3,2) assign(r3,2) assign(s3,6) assign(t3,2) assign(u3,6) assign(v3,6) assign(w3,6) assign(x3,6) assign(y3,1) assign(z3,1) assign(a4,3) assign(f4,3) assign(h4,3) assign(i4,3) assign(j4,3) assign(b4,4) assign(z4,4) assign(p4,5) assign(r4,5) assign(t4,5) assign(c4,7) assign(d4,7) assign(e4,7) assign(g4,7) assign(q4,7) assign(v4,10) assign(u4,12) assign(w4,12) assign(k4,15) assign(l4,15) assign(m4,15) assign(o4,15) assign(n4,16) assign(s4,16) assign(x4,16) assign(y4,16)
Optimization: -2
Answer: 3
assign(z1,9) assign(z2,9) assign(y1,8) assign(y2,8) assign(x1,15) assign(x2,15) assign(w1,14) assign(w2,14) assign(v1,15) assign(v2,15) assign(u1,5) assign(u2,5) assign(t1,8) assign(t2,8) assign(s1,11) assign(s2,11) assign(r1,16) assign(r2,16) assign(q1,9) assign(q2,9) assign(p1,15) assign(p2,15) assign(o1,12) assign(o2,12) assign(n1,8) assign(n2,8) assign(m1,14) assign(m2,14) assign(l1,11) assign(l2,11) assign(k1,5) assign(k2,5) assign(j1,9) assign(j2,9) assign(i1,9) assign(i2,9) assign(h1,9) assign(h2,9) assign(g1,10) assign(g2,10) assign(f1,16) assign(f2,16) assign(e1,16) assign(e2,16) assign(d1,12) assign(d2,12) assign(c1,12) assign(c2,12) assign(b1,10) assign(b2,10) assign(a1,12) assign(a2,12) assign(a3,12) assign(b3,13) assign(c3,1) assign(d3,1) assign(e3,13) assign(f3,13) assign(g3,4) assign(h3,13) assign(i3,4) assign(j3,4) assign(k3,5) assign(l3,1) assign(m3,14) assign(n3,11) assign(o3,2) assign(p3,2) assign(q3,2) assign(r3,2) assign(s3,6) assign(t3,2) assign(u3,6) assign(v3,6) assign(w3,6) assign(x3,6) assign(y3,1) assign(z3,1) assign(b4,3) assign(h4,3) assign(i4,3) assign(j4,3) assign(q4,3) assign(a4,4) assign(z4,4) assign(p4,5) assign(r4,5) assign(c4,7) assign(d4,7) assign(e4,7) assign(f4,7) assign(g4,7) assign(u4,7) assign(v4,10) assign(w4,12) assign(t4,13) assign(k4,15) assign(l4,15) assign(m4,15) assign(o4,15) assign(n4,16) assign(s4,16) assign(x4,16) assign(y4,16)
Optimization: -3
Answer: 4
assign(z1,9) assign(z2,9) assign(y1,8) assign(y2,8) assign(x1,15) assign(x2,15) assign(w1,14) assign(w2,14) assign(v1,15) assign(v2,15) assign(u1,5) assign(u2,5) assign(t1,8) assign(t2,8) assign(s1,11) assign(s2,11) assign(r1,16) assign(r2,16) assign(q1,9) assign(q2,9) assign(p1,15) assign(p2,15) assign(o1,12) assign(o2,12) assign(n1,8) assign(n2,8) assign(m1,14) assign(m2,14) assign(l1,11) assign(l2,11) assign(k1,5) assign(k2,5) assign(j1,9) assign(j2,9) assign(i1,9) assign(i2,9) assign(h1,9) assign(h2,9) assign(g1,10) assign(g2,10) assign(f1,16) assign(f2,16) assign(e1,16) assign(e2,16) assign(d1,12) assign(d2,12) assign(c1,12) assign(c2,12) assign(b1,10) assign(b2,10) assign(a1,12) assign(a2,12) assign(a3,13) assign(b3,13) assign(c3,1) assign(d3,12) assign(e3,13) assign(f3,13) assign(g3,4) assign(h3,13) assign(i3,4) assign(j3,4) assign(k3,5) assign(l3,1) assign(m3,14) assign(n3,11) assign(o3,2) assign(p3,2) assign(q3,2) assign(r3,2) assign(s3,6) assign(t3,2) assign(u3,6) assign(v3,6) assign(w3,6) assign(x3,15) assign(y3,1) assign(z3,1) assign(h4,1) assign(a4,3) assign(e4,3) assign(i4,3) assign(j4,3) assign(q4,3) assign(f4,4) assign(z4,4) assign(p4,5) assign(r4,5) assign(t4,5) assign(b4,6) assign(c4,7) assign(d4,7) assign(g4,7) assign(k4,7) assign(u4,7) assign(v4,10) assign(w4,12) assign(l4,15) assign(m4,15) assign(o4,15) assign(n4,16) assign(s4,16) assign(x4,16) assign(y4,16)
Optimization: -4
Answer: 5
assign(z1,9) assign(z2,9) assign(y1,8) assign(y2,8) assign(x1,15) assign(x2,15) assign(w1,14) assign(w2,14) assign(v1,15) assign(v2,15) assign(u1,5) assign(u2,5) assign(t1,8) assign(t2,8) assign(s1,11) assign(s2,11) assign(r1,16) assign(r2,16) assign(q1,9) assign(q2,9) assign(p1,15) assign(p2,15) assign(o1,12) assign(o2,12) assign(n1,8) assign(n2,8) assign(m1,14) assign(m2,14) assign(l1,11) assign(l2,11) assign(k1,5) assign(k2,5) assign(j1,9) assign(j2,9) assign(i1,9) assign(i2,9) assign(h1,9) assign(h2,9) assign(g1,10) assign(g2,10) assign(f1,16) assign(f2,16) assign(e1,16) assign(e2,16) assign(d1,12) assign(d2,12) assign(c1,12) assign(c2,12) assign(b1,10) assign(b2,10) assign(a1,12) assign(a2,12) assign(a3,13) assign(b3,13) assign(c3,12) assign(d3,1) assign(e3,13) assign(f3,13) assign(g3,4) assign(h3,13) assign(i3,4) assign(j3,4) assign(k3,5) assign(l3,1) assign(m3,14) assign(n3,11) assign(o3,2) assign(p3,2) assign(q3,2) assign(r3,2) assign(s3,6) assign(t3,2) assign(u3,5) assign(v3,6) assign(w3,6) assign(x3,15) assign(y3,1) assign(z3,1) assign(h4,1) assign(a4,3) assign(i4,3) assign(j4,3) assign(p4,3) assign(t4,3) assign(q4,4) assign(z4,4) assign(r4,5) assign(b4,6) assign(e4,6) assign(c4,7) assign(d4,7) assign(f4,7) assign(g4,7) assign(k4,7) assign(u4,7) assign(v4,10) assign(w4,12) assign(l4,15) assign(m4,15) assign(o4,15) assign(n4,16) assign(s4,16) assign(x4,16) assign(y4,16)
Optimization: -5
Answer: 6
assign(z1,9) assign(z2,9) assign(y1,8) assign(y2,8) assign(x1,15) assign(x2,15) assign(w1,5) assign(w2,5) assign(v1,15) assign(v2,15) assign(u1,5) assign(u2,5) assign(t1,8) assign(t2,8) assign(s1,11) assign(s2,11) assign(r1,16) assign(r2,16) assign(q1,9) assign(q2,9) assign(p1,15) assign(p2,15) assign(o1,13) assign(o2,13) assign(n1,8) assign(n2,8) assign(m1,14) assign(m2,14) assign(l1,11) assign(l2,11) assign(k1,5) assign(k2,5) assign(j1,9) assign(j2,9) assign(i1,9) assign(i2,9) assign(h1,9) assign(h2,9) assign(g1,10) assign(g2,10) assign(f1,16) assign(f2,16) assign(e1,16) assign(e2,16) assign(d1,12) assign(d2,12) assign(c1,12) assign(c2,12) assign(b1,10) assign(b2,10) assign(a1,12) assign(a2,12) assign(a3,12) assign(b3,13) assign(c3,12) assign(d3,1) assign(e3,4) assign(f3,13) assign(g3,4) assign(h3,13) assign(i3,4) assign(j3,4) assign(k3,4) assign(l3,1) assign(m3,14) assign(n3,11) assign(o3,2) assign(p3,15) assign(q3,2) assign(r3,2) assign(s3,6) assign(t3,2) assign(u3,6) assign(v3,6) assign(w3,5) assign(x3,15) assign(y3,1) assign(z3,1) assign(f4,1) assign(b4,2) assign(c4,3) assign(d4,3) assign(i4,3) assign(p4,3) assign(t4,3) assign(r4,5) assign(j4,6) assign(z4,6) assign(a4,7) assign(g4,7) assign(k4,7) assign(l4,7) assign(q4,7) assign(v4,10) assign(u4,12) assign(w4,12) assign(e4,14) assign(h4,14) assign(m4,15) assign(o4,15) assign(n4,16) assign(s4,16) assign(x4,16) assign(y4,16)
Optimization: -6
Answer: 7
assign(z1,12) assign(z2,12) assign(y1,15) assign(y2,15) assign(x1,10) assign(x2,10) assign(w1,5) assign(w2,5) assign(v1,13) assign(v2,13) assign(u1,5) assign(u2,5) assign(t1,15) assign(t2,15) assign(s1,12) assign(s2,12) assign(r1,16) assign(r2,16) assign(q1,11) assign(q2,11) assign(p1,15) assign(p2,15) assign(o1,12) assign(o2,12) assign(n1,9) assign(n2,9) assign(m1,14) assign(m2,14) assign(l1,8) assign(l2,8) assign(k1,6) assign(k2,6) assign(j1,8) assign(j2,8) assign(i1,9) assign(i2,9) assign(h1,9) assign(h2,9) assign(g1,10) assign(g2,10) assign(f1,16) assign(f2,16) assign(e1,16) assign(e2,16) assign(d1,13) assign(d2,13) assign(c1,10) assign(c2,10) assign(b1,8) assign(b2,8) assign(a1,5) assign(a2,5) assign(a3,5) assign(b3,4) assign(c3,10) assign(d3,1) assign(e3,7) assign(f3,1) assign(g3,4) assign(h3,1) assign(i3,7) assign(j3,7) assign(k3,3) assign(l3,4) assign(m3,14) assign(n3,9) assign(o3,12) assign(p3,15) assign(q3,11) assign(r3,2) assign(s3,12) assign(t3,15) assign(u3,4) assign(v3,1) assign(w3,6) assign(x3,10) assign(y3,15) assign(z3,4) assign(z4,1) assign(f4,2) assign(h4,2) assign(i4,2) assign(j4,2) assign(c4,3) assign(d4,3) assign(p4,3) assign(t4,3) assign(r4,5) assign(g4,6) assign(q4,6) assign(k4,7) assign(l4,7) assign(b4,11) assign(e4,11) assign(w4,12) assign(m4,13) assign(u4,13) assign(a4,14) assign(v4,14) assign(o4,15) assign(n4,16) assign(s4,16) assign(x4,16) assign(y4,16)
Optimization: -11
Answer: 8
assign(z1,13) assign(z2,13) assign(y1,15) assign(y2,15) assign(x1,10) assign(x2,10) assign(w1,5) assign(w2,5) assign(v1,13) assign(v2,13) assign(u1,5) assign(u2,5) assign(t1,15) assign(t2,15) assign(s1,12) assign(s2,12) assign(r1,16) assign(r2,16) assign(q1,11) assign(q2,11) assign(p1,15) assign(p2,15) assign(o1,12) assign(o2,12) assign(n1,9) assign(n2,9) assign(m1,14) assign(m2,14) assign(l1,8) assign(l2,8) assign(k1,6) assign(k2,6) assign(j1,9) assign(j2,9) assign(i1,4) assign(i2,4) assign(h1,4) assign(h2,4) assign(g1,5) assign(g2,5) assign(f1,16) assign(f2,16) assign(e1,16) assign(e2,16) assign(d1,13) assign(d2,13) assign(c1,10) assign(c2,10) assign(b1,8) assign(b2,8) assign(a1,12) assign(a2,12) assign(a3,12) assign(b3,8) assign(c3,10) assign(d3,1) assign(e3,7) assign(f3,1) assign(g3,5) assign(h3,1) assign(i3,7) assign(j3,7) assign(k3,3) assign(l3,8) assign(m3,14) assign(n3,9) assign(o3,12) assign(p3,15) assign(q3,11) assign(r3,2) assign(s3,12) assign(t3,15) assign(u3,5) assign(v3,1) assign(w3,6) assign(x3,10) assign(y3,15) assign(z3,13) assign(z4,1) assign(f4,2) assign(h4,2) assign(i4,2) assign(j4,2) assign(c4,3) assign(d4,3) assign(p4,3) assign(t4,3) assign(r4,4) assign(g4,6) assign(q4,6) assign(k4,7) assign(l4,7) assign(b4,11) assign(e4,11) assign(w4,12) assign(m4,13) assign(u4,13) assign(a4,14) assign(v4,14) assign(o4,15) assign(n4,16) assign(s4,16) assign(x4,16) assign(y4,16)
Optimization: -16
Answer: 9
assign(z1,4) assign(z2,4) assign(y1,15) assign(y2,15) assign(x1,10) assign(x2,10) assign(w1,7) assign(w2,7) assign(v1,11) assign(v2,11) assign(u1,5) assign(u2,5) assign(t1,15) assign(t2,15) assign(s1,12) assign(s2,12) assign(r1,16) assign(r2,16) assign(q1,11) assign(q2,11) assign(p1,15) assign(p2,15) assign(o1,12) assign(o2,12) assign(n1,9) assign(n2,9) assign(m1,14) assign(m2,14) assign(l1,8) assign(l2,8) assign(k1,8) assign(k2,8) assign(j1,1) assign(j2,1) assign(i1,5) assign(i2,5) assign(h1,16) assign(h2,16) assign(g1,3) assign(g2,3) assign(f1,7) assign(f2,7) assign(e1,9) assign(e2,9) assign(d1,10) assign(d2,10) assign(c1,10) assign(c2,10) assign(b1,8) assign(b2,8) assign(a1,5) assign(a2,5) assign(a3,5) assign(b3,8) assign(c3,10) assign(d3,10) assign(e3,9) assign(f3,1) assign(g3,4) assign(h3,16) assign(i3,5) assign(j3,1) assign(k3,8) assign(l3,8) assign(m3,14) assign(n3,9) assign(o3,12) assign(p3,15) assign(q3,11) assign(r3,2) assign(s3,12) assign(t3,15) assign(u3,5) assign(v3,11) assign(w3,4) assign(x3,10) assign(y3,15) assign(z3,4) assign(z4,1) assign(f4,2) assign(h4,2) assign(i4,2) assign(j4,2) assign(d4,3) assign(p4,3) assign(t4,3) assign(b4,6) assign(c4,6) assign(g4,6) assign(q4,6) assign(r4,6) assign(l4,7) assign(e4,11) assign(w4,12) assign(k4,13) assign(m4,13) assign(n4,13) assign(u4,13) assign(y4,13) assign(a4,14) assign(v4,14) assign(o4,15) assign(s4,16) assign(x4,16)
Optimization: -22
Answer: 10
assign(z1,4) assign(z2,4) assign(y1,15) assign(y2,15) assign(x1,10) assign(x2,10) assign(w1,7) assign(w2,7) assign(v1,11) assign(v2,11) assign(u1,5) assign(u2,5) assign(t1,15) assign(t2,15) assign(s1,12) assign(s2,12) assign(r1,2) assign(r2,2) assign(q1,11) assign(q2,11) assign(p1,15) assign(p2,15) assign(o1,12) assign(o2,12) assign(n1,9) assign(n2,9) assign(m1,14) assign(m2,14) assign(l1,8) assign(l2,8) assign(k1,8) assign(k2,8) assign(j1,1) assign(j2,1) assign(i1,5) assign(i2,5) assign(h1,16) assign(h2,16) assign(g1,3) assign(g2,3) assign(f1,7) assign(f2,7) assign(e1,9) assign(e2,9) assign(d1,10) assign(d2,10) assign(c1,10) assign(c2,10) assign(b1,8) assign(b2,8) assign(a1,5) assign(a2,5) assign(a3,5) assign(b3,8) assign(c3,10) assign(d3,10) assign(e3,9) assign(f3,1) assign(g3,4) assign(h3,16) assign(i3,5) assign(j3,1) assign(k3,8) assign(l3,8) assign(m3,14) assign(n3,9) assign(o3,12) assign(p3,15) assign(q3,11) assign(r3,2) assign(s3,12) assign(t3,15) assign(u3,5) assign(v3,11) assign(w3,4) assign(x3,10) assign(y3,15) assign(z3,4) assign(z4,1) assign(f4,2) assign(h4,2) assign(i4,2) assign(j4,2) assign(d4,3) assign(p4,3) assign(t4,3) assign(b4,6) assign(c4,6) assign(g4,6) assign(q4,6) assign(r4,6) assign(l4,7) assign(e4,11) assign(w4,12) assign(k4,13) assign(m4,13) assign(n4,13) assign(u4,13) assign(y4,13) assign(a4,14) assign(v4,14) assign(o4,15) assign(s4,16) assign(x4,16)
Optimization: -23
Answer: 11
assign(z1,4) assign(z2,4) assign(y1,1) assign(y2,1) assign(x1,10) assign(x2,10) assign(w1,7) assign(w2,7) assign(v1,11) assign(v2,11) assign(u1,5) assign(u2,5) assign(t1,15) assign(t2,15) assign(s1,12) assign(s2,12) assign(r1,2) assign(r2,2) assign(q1,11) assign(q2,11) assign(p1,15) assign(p2,15) assign(o1,12) assign(o2,12) assign(n1,9) assign(n2,9) assign(m1,14) assign(m2,14) assign(l1,8) assign(l2,8) assign(k1,8) assign(k2,8) assign(j1,1) assign(j2,1) assign(i1,5) assign(i2,5) assign(h1,16) assign(h2,16) assign(g1,3) assign(g2,3) assign(f1,1) assign(f2,1) assign(e1,9) assign(e2,9) assign(d1,10) assign(d2,10) assign(c1,10) assign(c2,10) assign(b1,8) assign(b2,8) assign(a1,5) assign(a2,5) assign(a3,5) assign(b3,8) assign(c3,10) assign(d3,10) assign(e3,9) assign(f3,1) assign(g3,4) assign(h3,16) assign(i3,5) assign(j3,1) assign(k3,8) assign(l3,8) assign(m3,14) assign(n3,9) assign(o3,12) assign(p3,15) assign(q3,11) assign(r3,2) assign(s3,12) assign(t3,15) assign(u3,5) assign(v3,11) assign(w3,4) assign(x3,10) assign(y3,1) assign(z3,4) assign(f4,2) assign(h4,2) assign(i4,2) assign(j4,2) assign(d4,3) assign(p4,3) assign(t4,3) assign(c4,6) assign(g4,6) assign(q4,6) assign(r4,6) assign(x4,6) assign(k4,7) assign(l4,7) assign(z4,7) assign(e4,11) assign(w4,12) assign(b4,13) assign(m4,13) assign(n4,13) assign(u4,13) assign(y4,13) assign(a4,14) assign(v4,14) assign(o4,16) assign(s4,16)
Optimization: -24
Answer: 12
assign(z1,4) assign(z2,4) assign(y1,14) assign(y2,14) assign(x1,10) assign(x2,10) assign(w1,7) assign(w2,7) assign(v1,11) assign(v2,11) assign(u1,5) assign(u2,5) assign(t1,15) assign(t2,15) assign(s1,12) assign(s2,12) assign(r1,2) assign(r2,2) assign(q1,11) assign(q2,11) assign(p1,15) assign(p2,15) assign(o1,12) assign(o2,12) assign(n1,13) assign(n2,13) assign(m1,14) assign(m2,14) assign(l1,8) assign(l2,8) assign(k1,8) assign(k2,8) assign(j1,1) assign(j2,1) assign(i1,5) assign(i2,5) assign(h1,16) assign(h2,16) assign(g1,10) assign(g2,10) assign(f1,16) assign(f2,16) assign(e1,9) assign(e2,9) assign(d1,11) assign(d2,11) assign(c1,10) assign(c2,10) assign(b1,8) assign(b2,8) assign(a1,5) assign(a2,5) assign(a3,5) assign(b3,8) assign(c3,10) assign(d3,11) assign(e3,9) assign(f3,16) assign(g3,10) assign(h3,16) assign(i3,5) assign(j3,1) assign(k3,8) assign(l3,8) assign(m3,14) assign(n3,13) assign(o3,12) assign(p3,15) assign(q3,11) assign(r3,2) assign(s3,12) assign(t3,15) assign(u3,5) assign(v3,11) assign(w3,7) assign(x3,10) assign(y3,14) assign(z3,4) assign(f4,1) assign(z4,1) assign(h4,2) assign(i4,2) assign(j4,2) assign(a4,3) assign(b4,3) assign(d4,3) assign(p4,3) assign(t4,3) assign(c4,4) assign(e4,4) assign(g4,6) assign(o4,6) assign(q4,6) assign(r4,6) assign(w4,6) assign(k4,7) assign(l4,7) assign(n4,9) assign(s4,9) assign(m4,13) assign(u4,13) assign(y4,13) assign(v4,14) assign(x4,16)
Optimization: -26

... using your preferred LLM to re-arrange the output:

Group 1:  j1, j2, j3, f4, z4  
Group 2:  r1, r2, r3, h4, i4, j4  
Group 3:  a4, b4, d4, p4, t4  
Group 4:  z1, z2, z3, c4, e4  
Group 5:  u1, u2, a1, a2, a3, i1, i2, i3, u3  
Group 6:  g4, o4, q4, r4, w4  
Group 7:  w1, w2, w3, k4, l4  
Group 8:  l1, l2, k1, k2, b1, b2, b3, k3, l3  
Group 9:  e1, e2, e3, n4, s4  
Group 10: x1, x2, g1, g2, c1, c2, c3, g3, x3  
Group 11: v1, v2, q1, q2, d1, d2, d3, q3, v3  
Group 12: s1, s2, o1, o2, o3, s3  
Group 13: n1, n2, n3, m4, u4, y4  
Group 14: y1, y2, m1, m2, m3, y3, v4  
Group 15: t1, t2, p1, p2, p3, t3  
Group 16: h1, h2, f1, f2, f3, h3, x4