我正在处理一个优化问题,我有一组需要分配的配对,每个配对都有相关的成本。
到目前为止,我一直在使用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]])
# Define the threshold for the average value in secondary_matrix
average_threshold = 6.0
在这个简单的例子中,cost_matrix
是一个方阵(很少有这种情况),其中costs[i][j]表示配对pairs[i]和pairs[j]的成本。secondary_matrix
是相同形状的矩阵,其中importance_values[i][j]对应于配对pairs[i]和pairs[j]的次级成本。average_threshold设置所选对的最大允许平均二级成本值。
仅使用scipy.optimize.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_matrix = cost_matrix[row_indices, col_indices].sum()
selected_pairs_average = np.mean(secondary_matrix[row_indices, col_indices])
return total_cost_matrix + max(0, selected_pairs_average - average_threshold)
# Initial guess for the optimization variable x
x0 = np.zeros_like(cost_matrix).flatten()
# Solve the optimization problem
result = minimize(combined_objective, x0, method="COBYLA")
# Extract the optimal assignments
row_indices, col_indices = linear_sum_assignment(cost_matrix + result.x.reshape(cost_matrix.shape))
return row_indices, col_indices
在这种方法中,当次矩阵的选定值的平均值高于平均阈值时,我会对成本进行惩罚
它似乎适用于小矩阵,但对于我的问题,我需要处理具有数千个元素的矩阵,当我有一个大于255个列元素的矩阵时,我会得到一个python segfault。
我是优化的初学者,所以我不确定我是否在正确的轨道上。
我的match_minimize方法是否合理?有没有一种方法可以让它适用于更大的矩阵?或者我应该使用不同的方法吗?
所有的建议和意见非常感谢。谢谢
1条答案
按热度按时间b4lqfgs41#
相当简单的LP构造;不过,您需要一个权重参数来确定平均误差相对于主要分配成本的重要性。尝试将下面的
mean_err_weight
在0.5和1.0之间更改,以观察差异。