Problème d'affectation - Assignment problem

Le problème d'affectation est un problème d' optimisation combinatoire fondamental . Dans sa forme la plus générale, le problème est le suivant :

L'instance du problème a un certain nombre d' agents et un certain nombre de tâches . N'importe quel agent peut être affecté à n'importe quelle tâche, ce qui entraîne des coûts qui peuvent varier en fonction de l'affectation de la tâche de l'agent. Il est nécessaire d'effectuer autant de tâches que possible en affectant au plus un agent à chaque tâche et au plus une tâche à chaque agent, de manière à minimiser le coût total de la mission.

Sinon, en décrivant le problème à l'aide de la théorie des graphes :

Le problème d'affectation consiste à trouver, dans un graphe bipartite pondéré , un appariement d'une taille donnée, dans lequel la somme des poids des arêtes est minimale.

Si les nombres d'agents et de tâches sont égaux, alors le problème est appelé affectation équilibrée . Sinon, on parle d' affectation déséquilibrée . Si le coût total de l'affectation pour toutes les tâches est égal à la somme des coûts pour chaque agent (ou à la somme des coûts pour chaque tâche, ce qui est la même chose dans ce cas), alors le problème est appelé affectation linéaire . Généralement, lorsque l'on parle du problème d'affectation sans aucune qualification supplémentaire, on entend alors le problème d'affectation équilibrée linéaire .

Exemples

Supposons qu'une entreprise de taxis dispose de trois taxis (les agents) et de trois clients (les tâches) souhaitant être pris en charge dans les plus brefs délais. L'entreprise se targue d'avoir des ramassages rapides, donc pour chaque taxi, le "coût" de ramassage d'un client particulier dépendra du temps mis par le taxi pour atteindre le point de ramassage. Il s'agit d'un problème d' affectation équilibrée . Sa solution est quelle que soit la combinaison de taxis et de clients qui entraîne le moindre coût total.

Maintenant, supposons qu'il y ait quatre taxis disponibles, mais toujours seulement trois clients. Il s'agit d'un problème d' affectation déséquilibrée . Une façon de le résoudre est d'inventer une quatrième tâche fictive, peut-être appelée « rester assis sans rien faire », avec un coût de 0 pour le taxi qui lui est assigné. Cela réduit le problème à un problème d'affectation équilibré, qui peut ensuite être résolu de la manière habituelle et toujours donner la meilleure solution au problème.

Des ajustements similaires peuvent être effectués afin d'autoriser plus de tâches que d'agents, des tâches auxquelles plusieurs agents doivent être affectés (par exemple, un groupe de plus de clients qu'il n'y en a dans un taxi), ou de maximiser le profit plutôt que de minimiser les coûts.

Définition formelle

La définition formelle du problème d'affectation (ou problème d'affectation linéaire ) est

Étant donné deux ensembles, A et T , de taille égale, avec une fonction de poids C : A × T → R . Trouver une bijection f : A → T telle que la fonction de coût :

\sum _{a\in A}C(a,f(a))

est minimisé.

Habituellement, la fonction de pondération est considérée comme une matrice carrée à valeur réelle C , de sorte que la fonction de coût s'écrit comme suit :

\sum _{a\in A}C_{a,f(a)}

Le problème est "linéaire" car la fonction de coût à optimiser ainsi que toutes les contraintes ne contiennent que des termes linéaires.

Algorithmes

Une solution naïve au problème des affectations consiste à vérifier toutes les affectations et à calculer le coût de chacune. Cela peut être très inefficace car, avec n agents et n tâches, il y a n ! ( factorielle de n ) différentes affectations. Heureusement, il existe de nombreux algorithmes pour résoudre le problème en temps polynomial en n .

Le problème d'affectation est un cas particulier du problème de transport , qui est un cas particulier du problème de flux de coût minimum , qui à son tour est un cas particulier d'un programme linéaire . Bien qu'il soit possible de résoudre n'importe lequel de ces problèmes en utilisant l' algorithme du simplexe , chaque spécialisation a un petit espace de solution et donc des algorithmes plus efficaces conçus pour tirer parti de sa structure spéciale.

Affectation équilibrée

Dans le problème d'affectation équilibrée, les deux parties du graphe bipartite ont le même nombre de sommets, noté n .

L'un des premiers algorithmes en temps polynomial pour l'affectation équilibrée était l' algorithme hongrois . C'est un algorithme global - il est basé sur l'amélioration d'un appariement le long de chemins augmentants (chemins alternés entre des sommets non appariés). Sa complexité d'exécution, lors de l'utilisation des tas de Fibonacci , est , où m est un nombre d'arêtes. C'est actuellement le temps d'exécution le plus rapide d'un algorithme fortement polynomial pour ce problème. Si tous les poids sont des entiers, le temps d'exécution peut être amélioré à , mais l'algorithme résultant n'est que faiblement polynomial. Si les poids sont des nombres entiers et que tous les poids sont au plus C (où C > 1 est un nombre entier), alors le problème peut être résolu en un temps faiblement polynomial dans une méthode appelée mise à l'échelle des poids . $O(mn+n^{2}\log n)$ $O(mn+n^{2}\log \log n)$ $O(m{\sqrt {n}}\log(n\cdot C))$

En plus des méthodes globales, il existe des méthodes locales basées sur la recherche de mises à jour locales (plutôt que sur des chemins d'augmentation complets). Ces méthodes ont des garanties d'exécution asymptotiques pires, mais elles fonctionnent souvent mieux dans la pratique. Ces algorithmes sont appelés algorithmes d'enchères , algorithmes push-relabel ou algorithmes preflow-push. Certains de ces algorithmes se sont avérés équivalents.

Certaines méthodes locales supposent que le graphe admet un appariement parfait ; si ce n'est pas le cas, certaines de ces méthodes peuvent s'exécuter indéfiniment. Un moyen technique simple pour résoudre ce problème consiste à étendre le graphe d'entrée à un graphe bipartite complet, en ajoutant des arêtes artificielles avec des poids très importants. Ces poids doivent dépasser les poids de tous les appariements existants, pour éviter l'apparition d'arêtes artificielles dans la solution possible.

Comme l'ont montré Mulmuley, Vazirani et Vazirani, le problème de l'appariement parfait de poids minimum est converti pour trouver des mineurs dans la matrice d'adjacence d'un graphe. En utilisant le lemme d'isolement , un appariement parfait de poids minimum dans un graphique peut être trouvé avec une probabilité d'au moins ½. Pour un graphe à n sommets, cela prend du temps. $O(\log ^{2}(n))$

Affectation déséquilibrée

Dans le problème d'affectation déséquilibrée, la plus grande partie du graphe bipartite a n sommets et la plus petite partie a r < n sommets. Il existe également une constante s qui est au plus la cardinalité d'une correspondance maximale dans le graphe. L'objectif est de trouver une correspondance à coût minimum de taille exactement s . Le cas le plus courant est le cas où le graphe admet un appariement unilatéral parfait (c'est-à-dire un appariement de taille r ) et s = r .

Une affectation déséquilibrée peut être réduite à une affectation équilibrée. La réduction naïve consiste à ajouter de nouveaux sommets à la plus petite partie et à les connecter à la plus grande partie en utilisant des arêtes de coût 0. Cependant, cela nécessite de nouvelles arêtes. Une réduction plus efficace s'appelle la technique du doublement . Ici, un nouveau graphe G' est construit à partir de deux copies du graphe d'origine G : une copie avant Gf et une copie arrière Gb. La copie arrière est "retournée", de sorte que, de chaque côté de G' , il y a maintenant n + r sommets. Entre les copies, nous devons ajouter deux types d'arêtes de liaison : $nr$ ${\style d'affichage n(nr)}$

De grand à grand : à partir de chaque sommet dans la plus grande partie de Gf , ajoutez une arête à coût nul au sommet correspondant dans Gb .
De petit à petit : si le graphe d'origine n'a pas de correspondance parfaite unilatérale, alors à partir de chaque sommet de la plus petite partie de Gf , ajoutez une arête très coûteuse au sommet correspondant dans Gb .

Dans l'ensemble, tout au plus de nouvelles arêtes sont nécessaires. Le graphique résultant a toujours une correspondance parfaite de taille . Un appariement parfait à coût minimum dans ce graphe doit consister en des appariements de cardinalité maximum à coût minimum dans Gf et Gb. Le principal problème avec cette technique de doublage est qu'il n'y a pas de gain de vitesse lorsque . ${\style d'affichage n+r}$ ${\style d'affichage n+r}$ ${\style d'affichage r\ll n}$

Au lieu d'utiliser la réduction, le problème d'affectation déséquilibrée peut être résolu en généralisant directement les algorithmes existants pour l'affectation équilibrée. L' algorithme hongrois peut être généralisé pour résoudre le problème en temps fortement polynomial. En particulier, si s = r alors le temps d'exécution est . Si les poids sont des entiers, la méthode de Thorup peut être utilisée pour obtenir un runtime de . $O(ms+s^{2}\log r)$ $O(mr+r^{2}\log r)$ $O(ms+s^{2}\log \log r)$

Solution par programmation linéaire

Le problème d'affectation peut être résolu en le présentant comme un programme linéaire . Pour plus de commodité, nous allons présenter le problème de maximisation. Chaque arête $(i, j)$ , où i est dans A et j est dans T , a un poids . Pour chaque arête, nous avons une variable _.La variable est 1 si l'arête est contenue dans la correspondance et 0 sinon, nous définissons donc les contraintes de domaine : ${\textstyle w_{ij}}$ ${\style d'affichage (i,j)}$ ${\textstyle x_{ij}}$

0\leq x_{ij}\leq 1{\text{ pour }}i,j\in A,T,\,

x_{ij}\in \mathbb {Z} {\text{ for }}i,j\in A,T.

Le poids total de l'appariement est de : . Le but est de trouver une correspondance parfaite de poids maximum. $\sum _{(i,j)\in A\times T}w_{ij}x_{ij}$

Pour garantir que les variables représentent bien une correspondance parfaite, nous ajoutons des contraintes indiquant que chaque sommet est adjacent à exactement une arête dans la correspondance, c'est-à-dire,

\sum _{j\in T}x_{ij}=1{\text{ for }}i\in A,\,~~~\sum _{i\in A}x_{ij}=1 {\text{ for }}j\in T,\,

.

Dans l'ensemble, nous avons le LP suivant:

{\text{maximize}}~~\sum _{(i,j)\in A\times T}w_{ij}x_{ij}

{\text{subject to}}~~\sum _{j\in T}x_{ij}=1{\text{ for }}i\in A,\,~~~\sum _{i \in A}x_{ij}=1{\text{ pour }}j\in T

0\leq x_{ij}\leq 1{\text{ pour }}i,j\in A,T,\,

x_{ij}\in \mathbb {Z} {\text{ for }}i,j\in A,T.

Il s'agit d'un programme linéaire en nombres entiers. Cependant, nous pouvons le résoudre sans les contraintes d'intégralité (c'est-à-dire, supprimer la dernière contrainte), en utilisant des méthodes standard pour résoudre des programmes linéaires continus. Bien que cette formulation autorise également des valeurs de variables fractionnaires, dans ce cas particulier, le LP a toujours une solution optimale où les variables prennent des valeurs entières. En effet, la matrice de contraintes du PL fractionnaire est totalement unimodulaire – elle satisfait les quatre conditions de Hoffman et Gale.

Cela peut aussi être prouvé directement. Soit x une solution optimale du LP fractionnaire, son poids total et le nombre de variables non-intégrales. Si nous avons terminé. Sinon, il existe une variable fractionnaire, disons . Parce que la somme des variables adjacentes à est 1, ce qui dans un entier, il doit y avoir une autre variable adjacente à j ₂ avec une valeur fractionnaire, disons . Par des considérations similaires sur i ₃ , il doit y avoir une autre variable adjacente à i ₃ avec une valeur fractionnaire, disons . Par des considérations similaires, nous passons d'un sommet à un autre, collectant des arêtes avec des valeurs fractionnaires. Puisque le graphe est fini, à un moment donné, nous devons avoir un cycle. Sans perte de généralité, nous pouvons supposer que le cycle se termine au sommet i ₁ , donc la dernière variable fractionnaire du cycle est . Le nombre d'arêtes dans le cycle est donc de 2 m – il doit être pair puisque le graphe est bipartite. ${\style d'affichage w(x)}$ ${\style d'affichage k(x)}$ ${\style d'affichage k(x)=0}$ ${\textstyle x_{i_{1},j_{2}}}$ ${\style d'affichage j_{2}}$ ${\textstyle x_{i_{3},j_{2}}}$ ${\textstyle x_{i_{3},j_{4}}}$ ${\textstyle x_{i_{1},j_{2m}}}$

Supposons que nous ajoutions une certaine constante e à toutes les variables paires du cycle et que nous supprimions la même constante e de toutes les variables impaires du cycle. Pour tout e de ce type , la somme des variables près de chaque sommet reste la même (1), de sorte que les contraintes de sommet sont toujours satisfaites. De plus, si e est suffisamment petit, toutes les variables restent entre 0 et 1, donc les contraintes de domaine sont toujours également satisfaites. Il est facile de trouver un plus grand e qui maintient les contraintes de domaine : c'est soit la plus petite différence entre une variable impaire et 0, soit la plus petite différence entre une variable paire et 1. Maintenant, nous avons une variable fractionnaire de moins, donc k ( x ) diminue de 1. La valeur objective reste la même, car sinon on pourrait l'augmenter en choisissant e comme positif ou négatif, en contradiction avec l'hypothèse qu'elle est maximale.

En répétant le processus de suppression de cycle, nous arrivons, après au plus n étapes, à une solution dans laquelle toutes les variables sont intégrales.

Autres méthodes et algorithmes d'approximation

D'autres approches pour le problème d'affectation existent et sont examinées par Duan et Pettie (voir Tableau II). Leur travail propose un algorithme d'approximation pour le problème d'affectation (et le problème plus général d' appariement de poids maximum ), qui s'exécute en temps linéaire pour toute borne d'erreur fixe.

Généralisation

Lorsqu'il est formulé comme un problème de théorie des graphes, le problème d'affectation peut être étendu des graphes bipartis aux graphes arbitraires. Le problème correspondant, consistant à trouver un appariement dans un graphique pondéré où la somme des poids est maximisée, est appelé le problème d'appariement des poids maximum .

Voir également

Références et lectures complémentaires

Brualdi, Richard A. (2006). Classes matricielles combinatoires . Encyclopédie des mathématiques et de ses applications. 108 . Cambridge : Cambridge University Press . ISBN 978-0-521-86565-4. Zbl 1106.05001 .
Burkard, Rainer ; M. Dell'Amico ; S. Martello (2012). Problèmes d'affectation (réimpression révisée) . SIAM. ISBN 978-1-61197-222-1.
Bertsekas, Dimitri (1998). Optimisation du réseau : modèles continus et discrets . Athéna Scientifique. ISBN 978-1-886529-02-1.

Languages

In other projects