Решение двудольного b-сопоставления с максимальным весом

Давайте попробуем сделать это шаг за шагом, написав нашу собственную функцию для решения проблемы WBM, как указано в вопросе.

Используя pulp, не так сложно сформулировать и решить взвешенное двудольное сопоставление (WBM), когда нам даны два набора узлов (u и v, веса ребер и емкости вершин).

На шаге 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, если вы не знакомы с 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. Надеюсь, это поможет вам двигаться вперед.