PythonOrtools MILP解决方案用于组优化 - 代码太笨拙？

Question

我有一群人需要分为小组。这些小组的规模不一定相同，但不得小于5，不超过10个。我创建了一个矩阵（在Excel中），在该矩阵中，每个可能的配对两个人都会分配为0到5的亲和力分数。具有5分的个体必须在同一组中（例如，配偶/派对的个体），而在同一组中的分数则不得在同一组中。我需要分组的优化配置。

贝洛（Below）是生产的代码CHATGPT的最新迭代，到目前为止，该迭代未能产生任何解决方案（实际上，甚至每120秒甚至没有提供一次请求的状态更新）。以前的迭代移动非常缓慢，当我ctrl+c'd终端时，解决方案坚持要在95人组合时仅组成一个大小（19组5）。从那以后，我将人们减少到93并更改了代码，因此我不确定代码是否无法处理不分为相等数量的组的数字，或者是否还有其他问题正在玩。我也想知道纸浆是否会更好，而不是Ortools。这是脚本：

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.")

Answer 1

由于您没有提供输入数据的示例，我就编造了 因此，您必须根据您的需求调整代码（如果对您有用）。

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 ))

要做的第一件事是计算子组的数量及其容量。

然后，我们通过与

Sortbyaffinity的亲和力对人进行分类，我实现了泡沫算法，因为它是最容易写的，您应该用您认为最方便的人代替它。

next，我们使用

divideByaffinity将有序列表分为具有相同亲和力的人的子组。该方法接收到有序列表，并且通过它，将具有相同亲和力的项目加载到辅助列表中。当一个出现的情况下，它会将辅助列表加载到输出列表中，更新aaffitiation值并继续。

在此之后，我们只需要创建子组，我们就可以使用

Createsubgroups 在此方法中，我们首先创建必须返回的列表，然后将空子组加载到其中。 然后我们分配了

data

（其中包含具有亲和力“ 5”的人）的最后一个sublist，我们将其与for一起进行，然后将每个项目加载在

OUTER

的第一个子组中，使所有人都必须在同一子组中。

一旦完成，我们将继续进入具有亲和力“ 0”的人，他们必须在不同的群体中。为此，我们将

gps的第一个子组的内容加载到data中并通过它，检查是否可以添加到第一个子组（如果不是，我们增加“ k”），然后将每个项目加载到其他子组中。 最终，我们必须输入其余部分，使用第一个ffor，我们通过gps的子组，不包括第一个和最后一个，第二个遍历了它们中的数据，第三个迭代在输出列表上迭代，寻找不满的子组，并继续将数据添加到它们。 不必说，可以优化此代码；这只是我希望可以帮助您获得所需的指南。