带约束矩阵的成本矩阵最优配对：Scipy方法优化与大矩阵适配问询

问题背景 #

我正在处理一个优化分配问题：需要为一组配对分配对象，每个配对对应相关成本，此前一直使用scipy.optimize.linear_sum_assignment求解。现在要增加问题复杂度，通过额外的约束矩阵控制选中的配对——目标仍是最小化选中配对的总成本，但需满足约束：选中配对在第二个矩阵中的平均值需接近指定阈值。

示例数据（使用NumPy数组）：

import numpy as np

cost_matrix = np.array([[3.1, 3.0], [3.0, 3.1]])
secondary_matrix = np.array([[1.0, 10.0], [10.0, 1.0]])
average_threshold = 6.0  # 次级矩阵选中值的平均阈值

其中：

• cost_matrix[i][j]表示将配对i与j组合的成本（实际场景中很少是方阵）
• secondary_matrix[i][j]对应配对i与j组合的次级指标值
• average_threshold是次级指标平均值的最大允许值

仅使用linear_sum_assignment会得到配对[0,1]和[1,0]，但加入约束后最优配对应为对角线元素，这是我想要实现的优化目标。

现有实现 #

我尝试了带惩罚项的优化方法：当下级指标平均值超过阈值时，为总成本添加惩罚项。代码如下：

import numpy as np
from scipy.optimize import linear_sum_assignment, minimize

def match_minimize(cost_matrix, constraint_matrix, average_threshold):
    def combined_objective(x):
        row_indices, col_indices = linear_sum_assignment(cost_matrix + x.reshape(cost_matrix.shape))
        total_cost = cost_matrix[row_indices, col_indices].sum()
        selected_avg = np.mean(secondary_matrix[row_indices, col_indices])
        return total_cost + max(0, selected_avg - average_threshold)

    # 优化变量初始猜测
    x0 = np.zeros_like(cost_matrix).flatten()
    # 求解优化问题
    result = minimize(combined_objective, x0, method="COBYLA")
    # 提取最优分配结果
    row_indices, col_indices = linear_sum_assignment(cost_matrix + result.x.reshape(cost_matrix.shape))
    return row_indices, col_indices

遇到的问题 #

该方法在小矩阵上可行，但我的问题需要处理包含数千个元素的矩阵，当矩阵列数超过255时会出现Python段错误。

寻求建议 #

我是优化领域的初学者，不确定当前方向是否正确，希望得到以下问题的指导：

• 现有match_minimize方法是否合理？
• 有没有办法使其适配大矩阵？
• 或者应该采用其他更高效的方法？

内容的提问来源于stack exchange，提问作者acleveronlinename