Python Ortools CP -SAT Решение для оптимизации группы - код слишком неуклюжий? ⇐ Python

[Anonymous]

У меня есть группа людей, которых мне нужно разделить на подгруппы. Подгруппы не должны быть одинакового размера, но могут быть не меньше, чем 5, и не более 10. Я создал матрицу (в Excel), где каждому возможным спариванию двух индивидов присваивается сродство от 0 до 5. Люди с оценкой 5 должны находиться в одной и той же группе (например, для супругов/партнеров), в то время как люди, которые имеют оценку 0, не могут быть в том же подгруппе в любом подгруппе. Мне нужна оптимизированная конфигурация подгрупп. Предыдущие итерации двигались очень медленно, и когда я ctrl+c'd терминал, решение настаивала на том, чтобы сделать подгруппы только одного размера (19 групп 5), когда это был набор из 95 человек. С тех пор я сократил людей до 93 и изменил код, поэтому я не уверен, не может ли код обработать число, которое не делится на равное количество подгрупп, или есть другие проблемы. Мне также интересно, будет ли мякоть лучше для этого, а не для Ortools. Вот сценарий: < /p>
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[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)) = 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 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.")
< /code>
Вот образец данных: < /p>



< /th>
cb < /th>


pd < /br /th>

pd < /br /th>. /> mp < /th>
rs < /th>
me < /th>
pd+1 < /th>
< /tr>
< /theade>


cb < /td>
/> 4 < /td>
3.5,5
4 < /td>
4 < /td>
4 < /td>
2 < /td>
< /tr>


< /td> < /br /> < /tr>

/> 4 < /td>
< /td>
4 < /td>
3.75> 3 < /td>
2 < /td>
5 < /td>
< /td>
5 < /td>
< /tr>

/> ni < /td>
3.5,5
4 < /td>
< /td>
3.3.75> 3 < /td>
3 < /td>
3 < /td>
3 < /td>
. />

mp
4
3.75
3.75

3
3
2.5
< /tr>

rs < /td>
4 < /td>
3 < /td>
3 < /td>
3

3 < /td>
3

3 < /td>
3
/> 4 < /td>
2.2.5>> < /tr>

me < /td>
4 < /td>
2 < /td>
3
2 < /td>
3
/> 4 < /td>
< /td>
3 < /td>
< /tr>

pd+1 < /td>
2 < /td>
5
< /td>
5
> . />2.2.5
2.2.5> 3 3





Подробнее здесь: https://stackoverflow.com/questions/795 ... too-clunky