Comparaison des solutions aux problèmes d'appariement de poids

Qu'est-ce que c'est

Nous avons comparé les temps de calcul des deux solutions de Maximum Weight Matching Problem.

Calcul

python

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

    #Solveur polyvalent(cbc)Calculé avec
    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()

    #Méthode Edmonds
    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

Visualisation

jupyter

%matplotlib inline
%config InlineBackend.figure_format = 'retina'
import matplotlib.pyplot as plt
plt.rcParams['font.family'] = 'IPAexGothic'
plt.xlabel('Nombre de nœuds')
plt.ylabel('Temps de calcul(Secondes)')
plt.plot([10,100,200,500,1000,2000,5000],[0.0268,0.0387,0.0464,0.0879,0.1596,0.3348,0.9361], label='Solveur polyvalent')
plt.plot([10,100,200,500,1000],[0.0046,0.0419,0.1253,1.2250,4.0942], label='Méthode Edmonds')
plt.legend();

Considération

• En général, le solveur dédié devrait avoir de meilleures performances que le solveur à usage général. ([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)) «Les deux recherchent une solution exacte.
• La valeur par défaut pour les solveurs génériques est free cbc. --Le solveur à usage général est une méthode basée sur la méthode de limitation de branche qui ne garantit pas un ordre polymorphe, mais le temps de calcul est proche de l'ordre linéaire, et même 5000 nœuds prennent moins d'une seconde.
• La méthode Edmonds, qui est un algorithme dédié, est considérée comme une méthode efficace, mais comme le temps de calcul n'est pas de l'ordre linéaire, 5000 nœuds sont 170 fois plus longs que le solveur général.

c'est tout