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

• Tm: temps de calcul (secondes), val: valeur de la fonction objective
• La ligne supérieure correspond à la loi hongroise et la ligne inférieure correspond au solveur général.

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

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

• Le temps dans la partie inférieure de ce qui précède inclut à la fois la création de modèle mathématique et l'exécution du solveur à usage général.
• La création de modèles mathématiques utilise un modeleur appelé PuLP, et l'exécution du solveur à usage général utilise un solveur appelé cbc.

Référence: Python dans l'optimisation

Principaux points de correction

• Celui qui a pris du temps dans l'article original était ** Créer un modèle mathématique **. La raison est que j'ai utilisé «sum» au lieu de «lpSum». sum crée une mémoire gaspillée et est lent.
• Veuillez également vous référer à "Somme des variables dans le modèle mathématique".
• Les variables du modèle mathématique sont de 0 à 1 variables binaires, mais elles sont résolues en tant que variables continues. Comme la matrice adjacente du problème d'affectation est entièrement unimodulaire, la relaxation linéaire donne une solution entière. --Référence: https://www.weblio.jp/content/ Tout unimodularité

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.