Let's try and do this step by step, writing our own function to solve the WBM problem as specified in the question.
Using pulp it is not too difficult to formulate and solve a weighted bipartite matching (WBM), when we are given two sets of nodes (u and v, edge weights and vertex capacities.)
In Step 2 below, you'll find a (hopefully easy to follow) function to formulate WBM as an ILP and solve using pulp. Go through it to see if it helps. (You need to pip install pulp)
Step 1: Set up the bipartite graph capacities and edge weights
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)
Step 2: Solve the WBM (formulated as an integer program)
Here's some description to make the code that follows easier to understand:
- The WBM is a variation of the Assignment problem.
- We 'match' nodes from the RHS to the LHS.
- The edges have weights
- The objective is to maximize the sum of the weights of the selected edges.
- Additional set of constraints: For each node, the number of selected edges has to be less than its 'capacity' which is specified.
- PuLP Documentation if you are not familiar with
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)
Step 3: Specify graph and call the WBM solver
wt = create_wt_doubledict(from_nodes, to_nodes)
p = solve_wbm(from_nodes, to_nodes, wt)
print_solution(p)
This gives:
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
Step 4: Optionally, plot the graph using 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")
The blue edges are the ones that were selected for the WBM. Hope this helps you move forward.
bindicates how many edges can be connected to that vertex. We can say that MWM is a specific case of the WBM where the capacity of each vertex is 1. Modeling the problem using the capacity for the vertices helps us solving one-to-many problems, like 1 reviewer has the capacity of reviewingbarticles. – Sina