如何用Python的PuLP构建并求解元素配对最大化和优化问题

问题描述 #

输入 #

• 两个元素列表 list_1 和 list_2
• 权值函数 foo(el1, el2)：接收来自两个列表的各一个元素，返回非负数值。该函数可转化为一个形状为 (len(list_1), len(list_2)) 的非负矩阵 A，其中 A[i][j] = foo(list_1[i], list_2[j])

任务 #

在每个列表中的元素仅能被使用一次的约束下，找到 list_1 与 list_2 的元素配对方案，使得所有配对的 foo 返回值总和最大。若某一列表长度更长，多余元素无法配对，对应贡献为0。

示例 #

给定：

• list_1 = [l1_0, l1_1, l1_2]
• list_2 = [l2_0, l2_1, l2_2, l2_3]

对应的权值矩阵：

A = [
    [0.0, 1.5, 2.4, 0.8],
    [3.1, 0.5, 0.0, 0.0],
    [0.0, 1.3, 2.5, 1.0]
]

该示例的最优结果：

• 最大总和 = 3.1 + 1.5 + 2.5 + 0 = 7.1
• 对应配对：[(l1_1, l2_0), (l1_0, l2_1), (l1_2, l2_2), (None, l2_3)]

解决方案 #

这个问题本质是带权二分图的最大权匹配问题，当两个列表长度不同时，可通过补虚拟节点转化为标准分配问题求解：

1. 确定两个列表的长度 m = len(list_1)，n = len(list_2)
2. 若 m < n：给 list_1 添加 n - m 个虚拟元素，这些元素与 list_2 任意元素配对的权值为0；若 n < m：给 list_2 添加 m - n 个虚拟元素，权值同样为0
3. 使用**匈牙利算法（Kuhn-Munkres算法）**求解转化后方阵的最大权匹配，即可得到最优配对方案和最大总和

代码实现示例 #

以Python为例，借助scipy库简化实现（注意该库默认求解最小权匹配，需将权值矩阵取反后计算）：

import numpy as np
from scipy.optimize import linear_sum_assignment

# 构造权值矩阵
A = np.array([
    [0.0, 1.5, 2.4, 0.8],
    [3.1, 0.5, 0.0, 0.0],
    [0.0, 1.3, 2.5, 1.0]
])

m, n = A.shape
# 补全为方阵，补0
if m < n:
    A = np.vstack([A, np.zeros((n - m, n))])
elif n < m:
    A = np.hstack([A, np.zeros((m, m - n))])

# 取反后求解最小权匹配，等价于原问题的最大权匹配
row_ind, col_ind = linear_sum_assignment(-A)
max_sum = A[row_ind, col_ind].sum()

# 生成配对结果
list_1_extended = list(list_1) + [None]*(max(m,n)-m)
list_2_extended = list(list_2) + [None]*(max(m,n)-n)
pairings = []
for r, c in zip(row_ind, col_ind):
    el1 = list_1_extended[r]
    el2 = list_2_extended[c]
    if el1 is not None or el2 is not None:
        pairings.append((el1, el2))

print(f"最大总和: {max_sum}")
print(f"对应配对: {pairings}")

运行后输出结果与示例一致：

最大总和: 7.1
对应配对: [(l1_1, l2_0), (l1_0, l2_1), (l1_2, l2_2), (None, l2_3)]

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