Comparison of solutions in weight matching problems

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();

image.png

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

Recommended Posts

Comparison of solutions in weight matching problems
[Tips] Problems and solutions in the development of python + kivy
Comparison of Japanese conversion module in Python3
Test of uniqueness in paired comparison method
About problems and solutions of OpenPyXL (Ver 3.0 version)
Old openssl causes problems in various parts of python
○○ Solving problems in the Department of Mathematics by optimization
Comparison of online classifiers
Comparison of fitting programs
Comparison of exponential moving average (EMA) code written in Python
Comparison of how to use higher-order functions in Python 2 and 3
Comparison of color detection methods in OpenCV inRange, numpy, cupy
Comparison of Hungarian law and general-purpose solver for allocation problems
Problems and solutions when asked for MySQL db in Python 3
Comparison of data frame handling in Python (pandas), R, Pig