[PYTHON] Vergleich von Lösungen bei Gewichtsanpassungsproblemen

Was ist das

Wir haben die Berechnungszeiten der beiden Lösungen von Maximum Weight Matching Problem verglichen.

Berechnung

python

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

    #Allzwecklöser(cbc)Berechnet mit
    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-Methode
    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

Visualisierung

jupyter

%matplotlib inline
%config InlineBackend.figure_format = 'retina'
import matplotlib.pyplot as plt
plt.rcParams['font.family'] = 'IPAexGothic'
plt.xlabel('Anzahl der Knoten')
plt.ylabel('Berechnungszeit(Sekunden)')
plt.plot([10,100,200,500,1000,2000,5000],[0.0268,0.0387,0.0464,0.0879,0.1596,0.3348,0.9361], label='Allzwecklöser')
plt.plot([10,100,200,500,1000],[0.0046,0.0419,0.1253,1.2250,4.0942], label='Edmonds-Methode')
plt.legend();

Erwägung

• Im Allgemeinen wird erwartet, dass der dedizierte Solver eine bessere Leistung aufweist als der Allzwecklöser. ([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)) ――Beide suchen nach einer genauen Lösung.
• Die Standardeinstellung für generische Löser ist free cbc.
• Der Allzwecklöser ist eine Methode, die auf der Verzweigungsbegrenzungsmethode basiert und keine polymorphe Ordnung garantiert, aber die Berechnungszeit liegt nahe an der linearen Ordnung, und selbst 5000 Knoten benötigen weniger als 1 Sekunde.
• Die Edmonds-Methode, bei der es sich um einen dedizierten Algorithmus handelt, wird als effiziente Methode bezeichnet. Da die Berechnungszeit jedoch nicht in der linearen Größenordnung liegt, sind 5000 Knoten 170-mal länger als der Allzwecklöser.

das ist alles