解决最大权二分图匹配问题

Question

我的问题涉及最大权重B匹配问题。

二分图匹配问题将二分图中的两组顶点进行配对。最大权重二分图匹配(MWM)被定义为一种匹配，其中匹配中边的值之和具有最大值。一个著名的MWM多项式时间算法是匈牙利算法。

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

这张图片（来自Chen et al.）展示了WBM问题。输入图的分数为2.2，即其所有边权重之和。解决方案H的蓝色边缘产生了最高分数1.6，满足红色度约束的所有子图中最高的得分。

虽然有一些近期的研究涉及到WBM问题（this 和 this），但我找不到任何算法实现。是否有人知道WBM问题是否已经存在于像networkX这样的库中？

- Sina

---

不确定WBM是否已经实现。如果您选择自行实现，此SO问题/答案应该会给您一些想法。 - Ram Narasimhan

谢谢，但不幸的是这并没有帮助。NetworkX有用于二分图的匹配算法，但对于这种特殊情况，它没有任何东西。 - Sina

匈牙利算法解决了匹配问题，而不考虑每个顶点的容量。 容量b表示可以连接到该顶点的边的数量。 我们可以说MWM是WBM的一个特例，其中每个顶点的容量为1。 使用顶点的容量对问题进行建模有助于解决一对多问题，例如一个评审人具有审阅b篇文章的能力。 - Sina

算了，我觉得只有当图是完全连接的时候它才变成了一个经典的背包问题。 - Paul Brodersen

是的，有很多老派的离散优化理论可以被优雅地表达为图问题，但并没有这样做。这并不意味着他们没有找出一两个问题。如果链接给你带来了新思路，我会很高兴。 - Paul Brodersen

Answer 1

让我们逐步尝试编写自己的函数来解决问题中指定的WBM问题。

使用pulp，当我们有两组节点（u和v，边权重和顶点容量）时，很容易制定和解决加权二分匹配（WBM）问题。

在下面的第2步中，您将找到一个（希望易于理解）的函数，将WBM制定为ILP并使用pulp求解。仔细阅读它，看看它是否有所帮助。（您需要pip安装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，请参考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)        

第三步：指定图表并调用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

第四步：可选地使用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的边缘。希望这可以帮助您继续前进。

- Ram Narasimhan

---

Ram，非常感谢您详细的解释。虽然您的解决方案非常有趣，但似乎忽略了问题的二分匹配特性。该问题不仅要优化参数，而且还要在考虑每个顶点的容量的同时保持图形二分匹配。否则，在不重视二分性的情况下，您的解决方案可能是完美的。只是为了澄清，如果我们将每个顶点的容量设置为1，则输出应该是一个匹配的二分图，而这并不是您的解决方案的情况。 - Sina

新浪，有些二分图（或二分匹配）的微妙属性我可能没有注意到。你能指出上面的例子违反了哪个属性以及为什么吗？我会修复它。 - Ram Narasimhan

Ram，请将顶点的容量设置为1。您的解决方案应该给出一个类似于匈牙利算法输出的二分图匹配图。您能否将您的解决方案应用于匈牙利算法的输出，以便优化是针对容量进行的？ - Sina