求解最大权二部匹配

Question

我的问题是关于最大权重的B-匹配问题。在

二部匹配问题对二部图中的两组顶点。最大加权二部匹配（MWM）被定义为匹配中的边值之和具有最大值的匹配。一个著名的多项式时间算法MWM是匈牙利算法。在

我感兴趣的是一个特定的最大加权二部匹配问题，称为加权二部B-匹配问题。权重二部B-匹配问题（WBM）寻求匹配顶点，使得每个顶点匹配的顶点不超过其容量b所允许的数量。在

这个图（来自Chen et al.）显示了WBM问题。输入图的分数为2.2，即所有边权重的总和。在满足红度约束的所有子图中，解H的蓝边得到的分数最高，为1.6。在

虽然最近有一些关于WBM问题（this和this）的工作，但我找不到该算法的任何实现。有人知道WBM问题在networkX这样的库中是否已经存在吗？在

Answer 1

让我们试着一步一步来做，编写我们自己的函数来解决问题中指定的WBM问题。在

当给定两组节点（u和v、边权值和顶点容量）时，用pulp构造和求解加权二部匹配（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是指派问题的一个变种。在
• 我们“匹配”了从右到左的节点。在
• 边缘有重量
• 目标是使选定边的权重之和最大化。在
• 附加约束集：对于每个节点，选定边的数量必须小于其指定的“容量”。在
• PuLP Documentation如果你不熟悉{}

一。在

^{pr2}$

步骤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选择的边。希望这能帮助你前进。在