Débit maximal et problème d'affectation linéaire

À correspondance maximale matching est un correspondance parfaite si tout pour nœud n dans G.setOfArcs il existe un arc a dans matching où a.fromNode == n or a.toNode == n.

Correspondance bipartite maximale

À correspondance bipartite maximale est un correspondance maximale dix un digraphe G lequel est bipartite .

Étant donné que G est bipartite , le problème de trouver un correspondance bipartite maximale peut être transformé en un problème de débit maximal résoluble avec le Edmonds-Karp l'algorithme puis le correspondance bipartite maximale peuvent être récupérés de la solution au problème de débit maximal .

Soit bipartition être un bipartition de G.

Pour ce faire, je dois générer un nouveau digraphe (H) avec de nouveaux nœuds (H.setOfNodes) et de nouveaux arcs (H.setOfArcs). H.setOfNodes contient tous les nœuds dans G.setOfNodes et deux de plus hochement de tête , s (à nœud source ) et t (une nœud terminal ).

H.setOfArcs contiendra un arc pour chaque G.setOfArcs. Si un arc a est dans G.setOfArcs et a.fromNode est dans bipartition.firstPart et a.toNode est dans bipartition.secondPart puis incluez a dans H (ajout d'un FlowArcDatum(1,0)).

Si a.fromNode est dans bipartition.secondPart et a.toNode est dans bipartition.firstPart, puis incluez Arc(a.toNode,a.fromNode,FlowArcDatum(1,0)) dans H.setOfArcs.

La définition d'un bipartite graphique garantit que non arc connecte tout nœuds où les deux nœuds sont dans la même partition. H.setOfArcs contient également un arc de nœud s pour chaque nœud dans bipartition.firstPart. Enfin, H.setOfArcs contient un arc chaque nœud dans bipartition.secondPart à nœud t. a.datum.capacity = 1 pour tous a dans H.setOfArcs.

Partitionnez d'abord le nœuds dans G.setOfNodes les deux disjoint définit (part1 et part2) tels que non arc dans G.setOfArcs est dirigé d'un ensemble vers le même ensemble (cette partition est possible car G est bipartite ). Ensuite, ajoutez tout arcs dans G.setOfArcs qui sont dirigés depuis part1 à part2 dans H.setOfArcs. Puis créez un single nœud source s et un seul nœud terminal t et créez-en plus arcs

Ensuite, construisez un maxFlowProblemState.

Couverture minimale des nœuds

Une couverture de nœud dans un digraphe G est un ensemble de nœuds (cover) à partir de G.setOfNodes tel que pour tout arc a de G.setOfArcs cela doit être vrai: (a.fromNode in cover) or (a.toNode in cover).

Une couverture de nœud minimale est le plus petit ensemble possible de nœuds dans le graphique qui est toujours un couverture de nœud . Le théorème de König stipule que dans un bipartite graphe, la taille du correspondance maximale sur ce graphique est égale à la taille de couverture de nœud minimal , et cela suggère comment le couverture de nœud peut récupérer d'un correspondance maximale :

Supposons que nous ayons le bipartition bipartition et le correspondance maximale matching. Définissez un nouveau digraphe H, H.setOfNodes=G.setOfNodes, le arcs dans H.setOfArcs sont l'union de deux ensembles.

Le premier ensemble est arcs a dans matching, avec le changement que si a.fromNode in bipartition.firstPart et a.toNode in bipartition.secondPart puis a.fromNode et a.toNode sont échangés dans le créé arc donner un tel arcs a a.datum.inMatching=True attribut pour indiquer qu'ils sont dérivés de arcs dans un correspondant à .

Le deuxième ensemble est arcs a PAS dans matching, avec le changement que si a.fromNode in bipartition.secondPart et a.toNode in bipartition.firstPart puis a.fromNode et a.toNode sont échangés dans le créé arc (donnez un tel arcs a a.datum.inMatching=False attribut).

Ensuite, exécutez un première recherche en profondeur ( DFS ) à partir de chaque nœud n dans bipartition.firstPart qui n'est ni n == a.fromNode ni n == a.toNodes pour toute arc a dans matching. Pendant le DFS, certains nœuds sont visités et certains ne le sont pas (stockez ces informations dans un champ n.datum.visited). La couverture minimale des nœuds est l'union du nœuds {a.fromNode for a in H.setOfArcs if ( (a.datum.inMatching) and (a.fromNode.datum.visited) ) } et le nœuds {a.fromNode for a in H.setOfArcs if (a.datum.inMatching) and (not a.toNode.datum.visited)}.

Cela peut être démontré à partir d'un correspondance maximale à un couverture de nœud minimal par un preuve par contradiction , prends en arc a qui n'a pas été prétendument couvert et examinez les quatre cas pour savoir si a.fromNode et a.toNode appartiennent (que ce soit en tant que toNode ou fromNode) à arc dans correspondant à matching. Chaque cas conduit à une contradiction en raison de l'ordre de visite de DFS nœuds et le fait que matching est un correspondance maximale .

Supposons que nous ayons une fonction pour exécuter ces étapes et renvoyer l'ensemble de nœuds comprenant le couverture de nœud minimal quand on lui donne le digraphe G, et le correspondance maximale matching:

Le problème d'affectation linéaire

Le problème d'affectation linéaire consiste à trouver une correspondance de poids maximum dans un graphe biparti pondéré.

Des problèmes comme celui du tout début de cet article peuvent être exprimés en problème d'affectation linéaire . Étant donné un ensemble de travailleurs, un ensemble de tâches et une fonction indiquant la rentabilité d'une affectation d'un travailleur à une tâche, nous voulons maximiser la somme de toutes les affectations que nous effectuons; c'est un problème d'affectation linéaire .

Supposons que le nombre de tâches et de travailleurs soit égal, même si je montrerai que cette hypothèse est facile à supprimer. Dans la mise en œuvre, je représente poids d'arc avec un attribut a.datum.weight pour un arc a.

Algorithme de Kuhn-Munkres

L'algorithme de Kuhn-Munkres résout le problème d'affectation linéaire . Une bonne implémentation peut prendre O(N^{4}) time, (où N est le nombre de nœuds dans le digraphe représentant le problème). Une implémentation plus simple à expliquer prend O(N^{5}) (pour une version qui régénère Graphiques ) et O(N^{4}) for (pour une version qui maintient Graphiques ). Ceci est similaire aux deux implémentations différentes du Edmonds-Karp algorithme.

Pour cette description, je travaille uniquement avec des graphes bipartis complets (ceux où la moitié nœuds sont dans une partie du bipartition et l'autre moitié dans la seconde partie). Chez le travailleur, la motivation des tâches signifie qu'il y a autant de travailleurs que de tâches.

Cela semble être une condition importante (et si ces ensembles ne sont pas égaux!) Mais il est facile de résoudre ce problème; Je parle de la façon de faire cela dans la dernière section.

La version de l'algorithme décrite ici utilise le concept utile de arcs de poids nul . Malheureusement, ce concept n'a de sens que lorsque nous résolvons un minimisation (si, plutôt que de maximiser les bénéfices de nos affectations de tâches, nous réduisions au contraire le coût de ces affectations).

Heureusement, il est facile de transformer un problème d'affectation linéaire maximum dans une problème d'affectation linéaire minimum en réglant chaque arc a poids à M-a.datum.weight où M=max({a.datum.weight for a in G.setOfArcs}). La solution à l'original maximiser le problème sera identique à la solution minimiser le problème après le arc les poids sont modifiés. Donc, pour le reste, supposons que nous apportons ce changement.

La Algorithme de Kuhn-Munkres résout correspondance de poids minimum dans un graphe biparti pondéré par une séquence de correspondances maximales en non pondéré bipartite graphiques. Si un nous trouvons un correspondance parfaite sur le digraphe représentation de la problème d'affectation linéaire , et si le poids de chaque arc dans le correspondant à est zéro, alors nous avons trouvé le correspondance de poids minimum puisque cette correspondance suggère que tout nœuds dans le digraphe a été apparié par un arc avec le coût le plus bas possible (aucun coût ne peut être inférieur à 0, sur la base des définitions antérieures).

Aucun autre arcs peut être ajouté au correspondant à (parce que tout nœuds sont déjà appariés) et non arcs doit être retiré du correspondant à car tout remplacement possible arc aura au moins une valeur pondérale aussi élevée.

Si nous trouvons un correspondance maximale du sous-graphe de G qui ne contient que arcs de poids nul , et ce n'est pas un correspondance parfaite , nous n'avons pas de solution complète (puisque le correspondant à n'est pas parfait ). Cependant, nous pouvons produire un nouveau digraphe H en changeant les poids de arcs dans G.setOfArcs d'une manière que le nouveau poids 0 arcs apparaissent et la solution optimale de H est la même que la solution optimale de G. Puisque nous garantissons qu'au moins un arc de poids nul est produit à chaque itération, nous garantissons que nous arriverons à un correspondance parfaite en pas plus de | G.setOfNodes | 2 = N 2 ces itérations.

Supposons que dans bipartition bipartition, bipartition.firstPart contient nœuds représentant les travailleurs, et bipartition.secondPart représente nœuds représentant des tâches.

L'algorithme commence par générer un nouveau digraphe H. H.setOfNodes = G.setOfNodes. Certains arcs dans H sont générés à partir de nœuds n dans bipartition.firstPart. Chacun de ces nœud n génère un arc b dans H.setOfArcs pour chaque arc a dans bipartition.G.setOfArcs où a.fromNode = n ou a.toNode = n, b=Arc(a.fromNode, a.toNode, a.datum.weight - z) où z=min(x.datum.weight for x in G.setOfArcs if ( (x.fromNode == n) or (x.toNode == n) )).

Plus arcs dans H sont générés à partir de nœuds n dans bipartition.secondPart. Chacun de ces nœud n génère un arc b dans H.setOfArcs pour chaque arc a dans bipartition.G.setOfArcs où a.fromNode = n ou a.toNode = n, b=Arc(a.fromNode, a.toNode, ArcWeightDatum(a.datum.weight - z)) où z=min(x.datum.weight for x in G.setOfArcs if ( (x.fromNode == n) or (x.toNode == n) )).

KMA: Ensuite, formez un nouveau digraphe K composé uniquement du arcs de poids nul de H, et le nœuds incident sur ceux arcs . Formez un bipartition sur le nœuds dans K, puis utilisez solve_mbm( bipartition ) pour obtenir un correspondance maximale (matching) sur K. Si matching est un correspondance parfaite dans H (la arcs dans matching sont incident en tout nœuds dans H.setOfNodes) puis le matching est une solution optimale au problème d'affectation linéaire .

Sinon, si matching n'est pas parfait , générer le couverture de nœud minimal de K en utilisant node_cover = get_min_node_cover(matching, bipartition(K)). Ensuite, définissez z=min({a.datum.weight for a in H.setOfArcs if a not in node_cover}). Définissez nodes = H.setOfNodes, arcs1 = {Arc(a.fromNode,a.toNode,ArcWeightDatum(a.datum.weigh-z)) for a in H.setOfArcs if ( (a.fromNode not in node_cover) and (a.toNode not in node_cover)}, arcs2 = {Arc(a.fromNode,a.toNode,ArcWeightDatum(a.datum.weigh)) for a in H.setOfArcs if ( (a.fromNode not in node_cover) != (a.toNode not in node_cover)}, arcs3 = {Arc(a.fromNode,a.toNode,ArcWeightDatum(a.datum.weigh+z)) for a in H.setOfArcs if ( (a.fromNode in node_cover) and (a.toNode in node_cover)}. Le != le symbole dans l'expression précédente agit comme un XOR opérateur. Puis arcs = arcs1.union(arcs2.union(arcs3)). Ensuite, H=DiGraph(nodes,arcs). Revenir à l'étiquette KMA . L'algorithme continue jusqu'à ce qu'un correspondance parfaite est produit. Cette correspondant à est aussi la solution au problème d'affectation linéaire .

Cette implémentation est O(N^{5}) car il génère un nouveau correspondance maximale matching à chaque itération; similaire aux deux implémentations précédentes de Edmonds-Karp cet algorithme peut être modifié pour garder une trace de l'appariement et l'adapter intelligemment à chaque itération. Lorsque cela est fait, la complexité devient O(N^{4}). Une version plus avancée et plus récente de cet algorithme (nécessitant des structures de données plus avancées) peut s'exécuter dans O(N^{3}). Les détails de l'implémentation plus simple ci-dessus et de l'implémentation plus avancée peuvent être trouvés sur ce post ce qui a motivé ce billet de blog.

Aucune des opérations sur arc les poids modifient l'affectation finale renvoyée par l'algorithme. Voici pourquoi: puisque nos graphiques d'entrée sont toujours graphes bipartis complets une solution doit cartographier chacun nœud d'une partition à l'autre nœud dans la deuxième partition, via le arc entre ces deux nœuds . Notez que les opérations effectuées sur le arc poids ne change jamais l'ordre (trié par poids) du arcs incident sur un nœud .

Ainsi, lorsque l'algorithme se termine à un correspondance bipartite complète parfaite chaque nœud se voit attribuer un arc de poids zéro , puisque l'ordre relatif des arcs à partir de ce nœud n'a pas changé pendant l'algorithme et depuis un arc de poids zéro est le moins cher possible arc et le correspondance bipartite complète parfaite garantit qu'un tel arc existe pour chacun nœud . Cela signifie que la solution générée est bien la même que la solution de l'original problème d'affectation linéaire sans aucune modification de arc poids.

Affectations déséquilibrées

Il semble que l'algorithme soit assez limité car, comme décrit, il ne fonctionne que sur graphes bipartis complets (ceux où la moitié du nœuds sont dans une partie du bipartition et l'autre moitié dans la seconde partie). Chez le travailleur, la motivation des tâches signifie qu'il y a autant de travailleurs que de tâches (cela semble assez limitatif).

Cependant, il existe une transformation facile qui supprime cette restriction. Supposons qu'il y ait moins de travailleurs que de tâches, nous ajoutons des travailleurs fictifs (assez pour faire du graphique résultant un graphe bipartite complet ). Chaque ouvrier factice a un arc dirigé du travailleur vers chacune des tâches. Chacun de ces arc a le poids 0 (le placer dans une correspondance ne donne aucun profit supplémentaire). Après ce changement, le graphique est un graphe bipartite complet pour laquelle nous pouvons résoudre. Aucune tâche affectée à un travailleur factice n'est lancée.

Supposons qu'il y ait plus de tâches que de travailleurs. Nous ajoutons quelques tâches factices (assez pour faire du graphique résultant un graphe bipartite complet ). Chaque tâche factice a un arc dirigé de chaque travailleur vers la tâche factice. Chacun de ces arc a un poids de 0 (le placer dans une correspondance ne donne aucun profit supplémentaire). Après ce changement, le graphique est un graphe bipartite complet pour laquelle nous pouvons résoudre. Tout travailleur affecté à une tâche factice n'est pas employé pendant la période.

Un exemple d'affectation linéaire

Enfin, faisons un exemple avec le code que j'utilise. Je vais modifier l'exemple de problème de Ici . Nous avons 3 tâches: nous devons nettoyer la salle de bain , Balayez le sol , et nettoyer les vitres .

Les travailleurs disponibles sont Alice , Bob , Charlie , et Diane . Chacun des travailleurs nous donne le salaire dont il a besoin par tâche. Voici les salaires par travailleur:

Si nous voulons payer le moins d'argent possible tout en réalisant toutes les tâches, qui devrait faire quelle tâche? Commencez par introduire une tâche factice pour rendre le digraphe représentant le problème biparti.

Supposons que le problème soit encodé dans un digraphe , alors kuhn_munkres( bipartition(G) ) résoudra le problème et retournera la mission. Il est facile de vérifier que l'attribution optimale (coût le plus bas) coûtera 5 USD.

Voici une visualisation de la solution générée par le code ci-dessus:

C'est ça. Vous savez maintenant tout ce que vous devez savoir sur le problème d'affectation linéaire.

Vous pouvez trouver tout le code de cet article sur GitHub .