我的问题是关于最大权重 B 匹配问题。
二分匹配问题将二分图中的两组顶点配对。 最大加权二分匹配 (MWM) 被定义为匹配中边的值之和具有最大值的匹配。 MWM 的一个著名的多项式时间算法是匈牙利算法。
我感兴趣的是一种特定的最大加权二分匹配,称为权重二分 B 匹配问题。权重二分 B 匹配问题 (WBM) 寻求匹配顶点,以便每个顶点匹配的顶点不超过其容量 b
允许的数量。
此图(来自 Chen et al.)显示了 WBM 问题。输入图的得分为 2.2,即所有边权重的总和。在所有满足红色度约束的子图中,解 H 的蓝色边缘得分最高,为 1.6。
虽然最近有一些工作解决了 WBM 问题(this 和 this),但我找不到该算法的任何实现。有人知道 WBM 问题是否已经存在于像 networkX 这样的库中吗?
最佳答案
让我们尝试逐步执行此操作,编写我们自己的函数来解决问题中指定的 WBM 问题。
使用 pulp
,当我们给定两组节点(u 和 v,边权重和顶点容量)时,制定和求解加权二分匹配 (WBM) 并不难。
在下面的第 2 步中,您将找到一个(希望易于理解)函数,用于将 WBM 制定为 ILP 并使用 pulp 求解。
仔细检查它是否有帮助。 (你需要pip install pulp
)
第 1 步:设置二分图容量和边权重
import networkx as nx
from pulp import *
import matplotlib.pyplot as plt
from_nodes = [1, 2, 3]
to_nodes = [1, 2, 3, 4]
ucap = {1: 1, 2: 2, 3: 2} #u node capacities
vcap = {1: 1, 2: 1, 3: 1, 4: 1} #v node capacities
wts = {(1, 1): 0.5, (1, 3): 0.3,
(2, 1): 0.4, (2, 4): 0.1,
(3, 2): 0.7, (3, 4): 0.2}
#just a convenience function to generate a dict of dicts
def create_wt_doubledict(from_nodes, to_nodes):
wt = {}
for u in from_nodes:
wt[u] = {}
for v in to_nodes:
wt[u][v] = 0
for k,val in wts.items():
u,v = k[0], k[1]
wt[u][v] = val
return(wt)
第 2 步:求解 WBM(公式化为整数规划)
为了让后面的代码更容易理解,这里有一些说明:
- WBM 是分配问题的变体。
- 我们将 RHS 的节点“匹配”到 LHS。
- 边有权重
- 目标是最大化所选边的权重总和。
- 附加约束集:对于每个节点,所选边的数量必须小于其指定的“容量”。
- PuLP Documentation如果您不熟悉
puLP
.
def solve_wbm(from_nodes, to_nodes, wt):
''' A wrapper function that uses pulp to formulate and solve a WBM'''
prob = LpProblem("WBM Problem", LpMaximize)
# Create The Decision variables
choices = LpVariable.dicts("e",(from_nodes, to_nodes), 0, 1, LpInteger)
# Add the objective function
prob += lpSum([wt[u][v] * choices[u][v]
for u in from_nodes
for v in to_nodes]), "Total weights of selected edges"
# Constraint set ensuring that the total from/to each node
# is less than its capacity
for u in from_nodes:
for v in to_nodes:
prob += lpSum([choices[u][v] for v in to_nodes]) <= ucap[u], ""
prob += lpSum([choices[u][v] for u in from_nodes]) <= vcap[v], ""
# The problem data is written to an .lp file
prob.writeLP("WBM.lp")
# The problem is solved using PuLP's choice of Solver
prob.solve()
# The status of the solution is printed to the screen
print( "Status:", LpStatus[prob.status])
return(prob)
def print_solution(prob):
# Each of the variables is printed with it's resolved optimum value
for v in prob.variables():
if v.varValue > 1e-3:
print(f'{v.name} = {v.varValue}')
print(f"Sum of wts of selected edges = {round(value(prob.objective), 4)}")
def get_selected_edges(prob):
selected_from = [v.name.split("_")[1] for v in prob.variables() if v.value() > 1e-3]
selected_to = [v.name.split("_")[2] for v in prob.variables() if v.value() > 1e-3]
selected_edges = []
for su, sv in list(zip(selected_from, selected_to)):
selected_edges.append((su, sv))
return(selected_edges)
第 3 步:指定图形并调用 WBM 求解器
wt = create_wt_doubledict(from_nodes, to_nodes)
p = solve_wbm(from_nodes, to_nodes, wt)
print_solution(p)
这给出:
Status: Optimal
e_1_3 = 1.0
e_2_1 = 1.0
e_3_2 = 1.0
e_3_4 = 1.0
Sum of wts of selected edges = 1.6
第 4 步:可选地,使用 Networkx 绘制图形
selected_edges = get_selected_edges(p)
#Create a Networkx graph. Use colors from the WBM solution above (selected_edges)
graph = nx.Graph()
colors = []
for u in from_nodes:
for v in to_nodes:
edgecolor = 'blue' if (str(u), str(v)) in selected_edges else 'gray'
if wt[u][v] > 0:
graph.add_edge('u_'+ str(u), 'v_' + str(v))
colors.append(edgecolor)
def get_bipartite_positions(graph):
pos = {}
for i, n in enumerate(graph.nodes()):
x = 0 if 'u' in n else 1 #u:0, v:1
pos[n] = (x,i)
return(pos)
pos = get_bipartite_positions(graph)
nx.draw_networkx(graph, pos, with_labels=True, edge_color=colors,
font_size=20, alpha=0.5, width=3)
plt.axis('off')
plt.show()
print("done")
蓝色边缘是为 WBM 选择的边缘。希望这有助于您继续前进。
关于python - 求解最大权重二分 b 匹配,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50908267/