Solving a Maximum weight bipartite b-matching

Question

My question is regarding the Maximum Weight B-Matching problem.

Bipartite matching problems pair two sets of vertices in a bipartite graph. A maximum weighted bipartite matching (MWM) is defined as a matching where the sum of the values of the edges in the matching have a maximal value. A famous polynomial time algorithm for MWM is the Hungarian algorithm.

What I am interested in is a specific maximum weighted bipartite matching known as weight bipartite B-matching problem. A weight bipartite B-matching problem (WBM) seeks to match vertices so that each vertex is matched with no more vertices than its capacity b allows.

This figure (from Chen et al.) shows the WBM problem. The input graph has score 2.2, the sum of all its edge weights. The blue edges of the solution H yield the highest score, 1.6, of all sub-graphs satisfying the red degree constraints.

Although there are a few recent works addressing the WBM problem (this and this), I cannot find any implementation of the algorithm. Does anybody know if the WBM problem already exists in any library like networkX?

Answer 1

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.