Comparaison de la loi hongroise et des solveurs polyvalents pour les problèmes d'allocation

Qu'est-ce que c'est

Il y avait un article dans "Problème d'affectation, loi hongroise et problème de planification des nombres entiers" que le solveur à usage général était lent. Dans cet article, je vais vous montrer qu'il est plus rapide de modifier un peu le code et de "créer un modèle mathématique et de le résoudre avec un solveur générique".

Code Python

Le code est ci-dessous. Il nécessite pip install numpy pulp munkres pour fonctionner.

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

Résultat d'exécution

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

Comme vous pouvez le voir, le solveur polyvalent est plus rapide.

Référence: Python dans l'optimisation

Principaux points de correction

De côté

―― Le solveur à usage général utilisé cette fois-ci est un solveur gratuit appelé cbc. Ce sera plus rapide avec un solveur payant. ―― En pratique, une solution approximative est souvent suffisante. L'utilisation du solveur de solution approximative est un compromis avec la précision de la solution, mais ce sera encore plus rapide. ――Les données sont cette fois un graphique complet en deux parties, mais en pratique, les données sont souvent rares. Dans ce cas, ce sera encore plus rapide car il y a moins de variables. «Je pourrais résoudre le problème d'allocation avec NetworkX, mais c'était trop lent à comparer.

Recommended Posts

Comparaison de la loi hongroise et des solveurs polyvalents pour les problèmes d'allocation
Le problème des menteurs et de l'honnêteté
Le problème des menteurs et de l'honnêteté
Comparaison d'Apex et de Lamvery
Comparaison de gem, bundler et pip, venv
Comparaison des solutions aux problèmes d'appariement de poids
Comparaison de l'héritage de classe et de la description du constructeur
Comparaison de la régularisation L1 et Leaky Relu
Comparaison de vitesse de murmurhash3, md5 et sha1