[PYTHON] Vergleich des ungarischen Rechts und der Allzwecklöser für Zuordnungsprobleme

Was ist das

Es gab einen Artikel in "Zuordnungsproblem, ungarisches Recht und ganzzahliges Planungsproblem", dass der Allzwecklöser langsam war. In diesem Artikel werde ich Ihnen zeigen, dass es schneller ist, den Code ein wenig zu ändern und "ein mathematisches Modell zu erstellen und es mit einem generischen Löser zu lösen".

Python-Code

Der Code ist unten. Zum Ausführen ist "pip install numpy pulp munkres" erforderlich.

import random
import time

import numpy as np
from munkres import Munkres
from pulp import PULP_CBC_CMD, LpProblem, LpVariable, lpDot, lpSum, value


class AssigmentProblem:
    def __init__(self, size, seed=0):
        self.size = size
        random.seed(seed)
        rng = range(self.size)
        self.weight = np.array([[random.randint(1, 100) for i in rng] for j in rng])

    def solve_hungarian(self):
        start_tm = time.time()
        m = Munkres()
        result = m.compute(self.weight.tolist())
        val = sum([self.weight[i, j] for i, j in result])
        tm = time.time() - start_tm
        print(f"hungarian {tm = :.2f} {val = }")

    def solve_pulp(self):
        m = LpProblem("AssignmentProblem")
        rng = range(self.size)
        x = np.array(LpVariable.matrix('x', (rng, rng), cat='Binary'))
        m += lpDot(self.weight.flatten(), x.flatten())
        start_tm = time.time()
        for i in rng:
            m += lpSum(x[i]) == 1
            m += lpSum(x[:, i]) == 1
        m.solve(PULP_CBC_CMD(mip=False, msg=False))
        val = value(m.objective)
        tm = time.time() - start_tm
        print(f"pulp      {tm = :.2f} {val = }")


if __name__ == "__main__":
    p1 = AssigmentProblem(300)
    p1.solve_hungarian()
    p1.solve_pulp()

Ausführungsergebnis

• Tm: Berechnungszeit (Sekunden), val: Zielfunktionswert
• Die obere Reihe ist das ungarische Gesetz und die untere Reihe ist der Allzwecklöser.

hungarian tm = 2.43 val = 352
pulp      tm = 1.94 val = 352.0

Wie Sie sehen können, ist der Allzwecklöser schneller.

• Die Zeit im unteren Teil des obigen Abschnitts umfasst sowohl die Erstellung eines mathematischen Modells als auch die Ausführung eines Allzwecklösers.
• Bei der mathematischen Modellerstellung wird ein Modellierer namens PuLP verwendet, und bei der Ausführung von Allzwecklösern wird ein Löser namens cbc verwendet.

Referenz: Python in Optimierung

Hauptkorrekturpunkte

• Im Originalartikel hat es einige Zeit gedauert **, ein mathematisches Modell zu erstellen **. Der Grund ist, dass ich "sum" anstelle von "lpSum" verwendet habe. sum schafft verschwendeten Speicher und ist langsam.
• Bitte beziehen Sie sich auch auf "Summe der Variablen im mathematischen Modell".
• Die Variablen im mathematischen Modell sind 0-1-Binärvariablen, werden jedoch als kontinuierliche Variablen gelöst. Da die benachbarte Matrix des Zuordnungsproblems alle unimodular ist, ergibt die lineare Relaxation eine ganzzahlige Lösung.
• Referenz: https://www.weblio.jp/content/ Alle Unimodularität

Beiseite

――Der diesmal verwendete Allzwecklöser ist ein freier Löser namens cbc. Mit einem bezahlten Löser wird es schneller. ――In der Praxis ist häufig eine ungefähre Lösung ausreichend. Die Verwendung des ungefähren Lösungslösers ist ein Kompromiss mit der Genauigkeit der Lösung, der jedoch noch schneller ist. ――Die Daten sind diesmal ein vollständiges zweiteiliges Diagramm, aber in der Praxis sind die Daten oft spärlich. In diesem Fall ist es sogar noch schneller, da weniger Variablen vorhanden sind. ――Ich konnte das Zuordnungsproblem mit NetworkX lösen, aber es war zu langsam, um es zu vergleichen.