what is this

We compared the calculation times of the two solutions of Maximum weight matching problem.

Calculation

`python`


import time, numpy as np, networkx as nx
from pulp import *
from ortoolpy import addbinvars
np.random.seed(1)
Average order= 3
for N in [10,100,200,500,1000,2000,5000]:
    #Graph creation
    g = nx.fast_gnp_random_graph(N,Average order/(N-1))
    for r,(i,j) in zip(np.random.rand(g.number_of_edges()),g.edges_iter()):
        g.edge[i][j]['weight'] = r

    #General-purpose solver(cbc)Calculated with
    m = LpProblem(sense=LpMaximize)
    x = addbinvars(g.number_of_edges())
    for v,(i,j) in zip(x, g.edges()):
        g[i][j]['Var'] = v
    m += lpDot([g[i][j]['weight'] for i,j in g.edges()], x)
    for nd in g.nodes():
        m += lpSum(d['Var'] for d in g[nd].values()) <= 1
    t1s = time.clock()
    m.solve()
    n1 = len([i for i,v in enumerate(x) if value(v) > 0.5])
    t1e = time.clock()

    #Edmonds method
    t2s = time.clock()
    n2 = len(nx.max_weight_matching(g))//2
    t2e = time.clock()
    assert n1==n2
    print(N,t1e-t1s,t2e-t2s)
>>>
10 0.02683257321768906 0.004652122559491545
100 0.038709433923941106 0.041949099861085415
200 0.046430152317043394 0.1253287561412435
500 0.08796162778162397 1.2250798634777311
1000 0.15964821091620252 4.0942329679674
2000 0.3348240090563195 20.510134776166524
5000 0.9361551560868975 159.31649612302135

Visualization

`jupyter`


%matplotlib inline
%config InlineBackend.figure_format = 'retina'
import matplotlib.pyplot as plt
plt.rcParams['font.family'] = 'IPAexGothic'
plt.xlabel('Number of nodes')
plt.ylabel('Calculation time(Seconds)')
plt.plot([10,100,200,500,1000,2000,5000],[0.0268,0.0387,0.0464,0.0879,0.1596,0.3348,0.9361], label='General-purpose solver')
plt.plot([10,100,200,500,1000],[0.0046,0.0419,0.1253,1.2250,4.0942], label='Edmonds method')
plt.legend();

Consideration

--In general, the dedicated solver is expected to have better performance than the general-purpose solver. ([No free lunch theorem-Wikipedia](https://ja.wikipedia.org/wiki/%E3%83%8E%E3%83%BC%E3%83%95%E3%83%AA%E3%83] % BC% E3% 83% A9% E3% 83% B3% E3% 83% 81% E5% AE% 9A% E7% 90% 86)) ――Both are seeking an exact solution. --The default for the generic solver is free cbc. --The general-purpose solver is a method based on the branch-and-bound method that does not guarantee a polynomial order, but the calculation time is close to the linear order, and even 5000 nodes take less than 1 second. --The Edmonds method, which is a dedicated algorithm, is said to be an efficient method, but since the calculation time is not on a linear order, 5000 nodes are 170 times longer than the general-purpose solver.

that's all

Comparison of solutions in weight matching problems