Problème d'affectation

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

Le problème comporte plusieurs agents et plusieurs tâches . Chaque agent peut être affecté à n'importe quelle tâche, ce qui engendre un coût variable selon l'affectation. L'objectif est d'effectuer le maximum de tâches en affectant au plus un agent par tâche et au plus une tâche par agent, de manière à minimiser le coût total de l'affectation.

Autre possibilité : décrire le problème à l’aide de la théorie des graphes :

Le problème d'affectation consiste à trouver, dans un graphe biparti pondéré , un couplage de taille maximale dans lequel la somme des poids des arêtes est minimale.

Si le nombre d'agents et de tâches est égal, le problème est appelé affectation équilibrée , et sa version en théorie des graphes est appelée couplage parfait à coût minimal . Sinon, il est appelé 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 revient au même dans ce cas), alors le problème est appelé affectation linéaire . Généralement, lorsqu'on parle du problème d'affectation sans autre précision, on fait référence au problème d'affectation linéaire équilibrée .

Exemples

Supposons qu'une compagnie de taxis dispose de trois taxis (les agents) et de trois clients (les courses) souhaitant être pris en charge au plus vite. La compagnie mise sur la rapidité des prises en charge ; par conséquent, le « coût » de chaque taxi pour la prise en charge d'un client dépend du temps de trajet jusqu'au point de prise en charge. Il s'agit d'un problème d'affectation équilibrée . La solution est la combinaison de taxis et de clients qui minimise le coût total.

Supposons maintenant qu'il y ait quatre taxis disponibles, mais seulement trois clients. Il s'agit d'un problème d'affectation déséquilibré . Une solution consiste à créer une quatrième tâche fictive, par exemple « rester assis sans rien faire », dont le coût pour le taxi affecté est nul. Cela ramène le problème à un problème d'affectation équilibré, qui peut alors être résolu de manière classique et qui reste la meilleure solution.

Des ajustements similaires peuvent être effectués afin de permettre plus de tâches que d'agents, des tâches auxquelles plusieurs agents doivent être affectés (par exemple, un groupe de clients plus nombreux que ne peut tenir un seul taxi), ou de maximiser les profits 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 , et une fonction de pondération C : A × T → R , trouver une bijection f : A → T telle que la fonction de coût :

{\displaystyle \sum _{a\in A}C(a,f(a)) <semantics><mrow><mstyle><munder><mo>∑</mo><mrow><mi>un</mi><mo>∈</mo><mi>UN</mi></mrow></munder><mi>C</mi><mo>(</mo><mi>un</mi><mo>,</mo><mi>f</mi><mo>(</mo><mi>un</mi><mo>)</mo><mo>)</mo></mstyle></mrow><annotation>{\displaystyle \sum _{a\in A}C(a,f(a))}</annotation></semantics></math></span><img src=

est minimisée.

Généralement, la fonction de pondération est considérée comme une matrice carrée à valeurs réelles C , de sorte que la fonction de coût s'écrit comme suit :

{\displaystyle \sum _{a\in A}C_{a,f(a) <semantics><mrow><mstyle><munder><mo>∑</mo><mrow><mi>un</mi><mo>∈</mo><mi>UN</mi></mrow></munder><msub><mi>C</mi><mrow><mi>un</mi><mo>,</mo><mi>f</mi><mo>(</mo><mi>un</mi><mo>)</mo></mrow></msub></mstyle></mrow><annotation>{\displaystyle \sum _{a\in A}C_{a,f(a)}}</annotation></semantics></math></span><img src=

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 d'affectation consiste à examiner toutes les affectations et à calculer le coût de chacune. Cette méthode peut s'avérer très inefficace car, avec n agents et n tâches, il existe n ! ( factorielle de n ) affectations différentes.

Une autre solution naïve consiste à attribuer d'abord, de manière gloutonne, la paire de sommets ayant le coût le plus faible, puis à supprimer les sommets non associés ; ensuite, parmi les sommets restants, à attribuer la paire ayant le coût le plus faible ; et ainsi de suite. Cet algorithme peut aboutir à une solution non optimale. Par exemple, supposons qu'il y ait deux tâches et deux agents dont les coûts sont les suivants :

Alice : Tâche 1 = 1, Tâche 2 = 2.
George : Tâche 1 = 5, Tâche 2 = 8.

L' algorithme glouton attribuerait la tâche 1 à Alice et la tâche 2 à George, pour un coût total de 9, mais l'attribution inverse a un coût total de 7.

Heureusement, de nombreux algorithmes permettent de trouver l'affectation optimale en temps polynomial en n . Le problème d'affectation est un cas particulier du problème de transport , lui-même un cas particulier du problème de flot à coût minimal , qui est à son tour un cas particulier de programme linéaire . Bien qu'il soit possible de résoudre chacun de ces problèmes à l'aide de l' algorithme du simplexe , ou, dans le pire des cas, en temps polynomial à l'aide de la méthode de l'ellipsoïde , chaque spécialisation possède un espace de solutions plus restreint et, par conséquent, des algorithmes plus efficaces conçus pour tirer parti de sa structure particulière.

Affectation équilibrée

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

L'un des premiers algorithmes polynomiaux pour l'affectation équilibrée est l' algorithme hongrois . C'est un algorithme global , basé sur l'amélioration d'un couplage le long de chemins augmentants (chemins alternés entre les sommets non appariés). Sa complexité temporelle, avec les tas de Fibonacci , est O(m) , où m est le nombre d'arêtes. Il s'agit actuellement du temps d'exécution le plus rapide pour un algorithme fortement polynomial sur ce problème. Certaines variantes de l'algorithme hongrois bénéficient également du calcul parallèle , notamment de l'accélération GPU. Si tous les poids sont des entiers, le temps d'exécution peut être amélioré à O(m) , mais l'algorithme résultant est alors faiblement polynomial . Si les poids sont des entiers et que tous les poids sont au plus égaux à C (où C > 1 est un entier), le problème peut être résolu en temps faiblement polynomial par une méthode appelée mise à l'échelle des poids . ${\displaystyle O(mn+n^{2}\log n) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mi>m</mi><mi>n</mi><mo>+</mo><msup><mi>n</mi><mrow><mn>2</mn></mrow></msup><mi>enregistrer</mi><mo>⁡</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{ displaystyle O (mn + n ^ {2} log n)}</annotation></semantics></math><img src=$ ${\displaystyle O(mn+n^{2}\log \log n) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mi>m</mi><mi>n</mi><mo>+</mo><msup><mi>n</mi><mrow><mn>2</mn></mrow></msup><mi>enregistrer</mi><mo>⁡</mo><mi>enregistrer</mi><mo>⁡</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(mn+n^{2}\log \log n)}</annotation></semantics></math><img src=$ ${\displaystyle O(m{\sqrt {n}}\log(n\cdot C)) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mi>m</mi><mrow><msqrt><mi>n</mi></msqrt></mrow><mi>enregistrer</mi><mo>⁡</mo><mo>(</mo><mi>n</mi><mo>⋅</mo><mi>C</mi><mo>)</mo><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(m{\sqrt {n}}\log(n\cdot C))}</annotation></semantics></math><img src=$

Outre les méthodes globales, il existe des méthodes locales qui reposent sur la recherche de mises à jour locales (plutôt que sur des chemins d'augmentation complets). Ces méthodes présentent des garanties de complexité asymptotique moins bonnes, mais elles sont souvent plus performantes en pratique. Ces algorithmes sont appelés algorithmes d'enchères , algorithmes de push-relabel ou algorithmes de pré-flux-push. Il a été démontré que certains de ces algorithmes sont équivalents.

Certaines méthodes locales supposent que le graphe admet un couplage parfait ; si ce n'est pas le cas, certaines de ces méthodes peuvent s'exécuter indéfiniment. Une solution technique simple à ce problème consiste à étendre le graphe d'entrée à un graphe biparti complet, en ajoutant des arêtes artificielles de poids très élevés. Ces poids doivent être supérieurs à ceux de tous les couplages existants, afin d'éviter l'apparition d'arêtes artificielles dans la solution possible.

Comme l'ont montré Mulmuley, Vazirani et Vazirani le problème du couplage parfait de poids minimal se ramène à la recherche des mineurs dans la matrice d'adjacence d'un graphe. Grâce au lemme d'isolation , un couplage parfait de poids minimal peut être trouvé dans un graphe avec une probabilité d'au moins 1/2 . Pour un graphe à n sommets, la résolution temporelle est de l'ordre de O(n ^n ) . ${\displaystyle O(\log ^{2}(n)) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><msup><mi>enregistrer</mi><mrow><mn>2</mn></mrow></msup><mo>⁡</mo><mo>(</mo><mi>n</mi><mo>)</mo><mo>)</mo></mstyle></mrow><annotation>{ displaystyle O (log ^ {2} (n))}</annotation></semantics></math><img src=$

Affectation déséquilibrée

Dans le problème d'affectation déséquilibrée, la plus grande partie du graphe biparti possède n sommets et la plus petite partie en possède r < n . On introduit également une constante s, inférieure ou égale à la cardinalité d'un couplage maximal du graphe. L'objectif est de trouver un couplage de coût minimal de cardinalité exactement s . Le cas le plus fréquent est celui où le graphe admet un couplage parfait unilatéral (c'est-à-dire un couplage de cardinalité r ), et où 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 relier à la plus grande partie par des arêtes de coût 0. Cependant, cela nécessite de nouvelles arêtes. Une réduction plus efficace est appelée la technique de duplication . Ici, un nouveau graphe G' est construit à partir de deux copies du graphe original G : une copie directe Gf et une copie inverse Gb. La copie inverse est « inversée », de sorte que, dans 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 : ${\displaystyle n-r <semantics><mrow><mstyle><mi>n</mi><mo>−</mo><mi>r</mi></mstyle></mrow><annotation>{\displaystyle nr}</annotation></semantics></math><img src=$ ${\displaystyle n(n-r) <semantics><mrow><mstyle><mi>n</mi><mo>(</mo><mi>n</mi><mo>−</mo><mi>r</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle n(nr)}</annotation></semantics></math><img src=$

De grand à grand : de chaque sommet de la plus grande partie de Gf , ajoutez une arête de coût nul au sommet correspondant dans Gb .
Petit à petit : si le graphe d'origine ne possède pas d'appariement parfait unilatéral, alors à partir de chaque sommet de la plus petite partie de Gf , ajoutez une arête à coût très élevé au sommet correspondant dans Gb .

En définitive, au plus nouvelles arêtes sont nécessaires. Le graphe résultant possède toujours un couplage parfait de taille . Un couplage parfait de coût minimal dans ce graphe doit être constitué de couplages de cardinalité maximale de coût minimal dans Gf et Gb. Le principal problème de cette technique de doublement est qu'elle n'apporte aucun gain de vitesse lorsque . ${\displaystyle n+r <semantics><mrow><mstyle><mi>n</mi><mo>+</mo><mi>r</mi></mstyle></mrow><annotation>{\displaystyle n+r}</annotation></semantics></math><img src=$ ${\displaystyle n+r <semantics><mrow><mstyle><mi>n</mi><mo>+</mo><mi>r</mi></mstyle></mrow><annotation>{\displaystyle n+r}</annotation></semantics></math><img src=$ ${\displaystyle r\ll n <semantics><mrow><mstyle><mi>r</mi><mo>≪</mo><mi>n</mi></mstyle></mrow><annotation>{\displaystyle r\ll n}</annotation></semantics></math><img src=$

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 O (n² ). Si les poids sont des entiers, alors la méthode de Thorup peut être utilisée pour obtenir un temps d'exécution O(n²) . ${\displaystyle O(ms+s^{2}\log r) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mi>m</mi><mi>s</mi><mo>+</mo><msup><mi>s</mi><mrow><mn>2</mn></mrow></msup><mi>enregistrer</mi><mo>⁡</mo><mi>r</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(ms+s^{2}\log r)}</annotation></semantics></math><img src=$ ${\displaystyle O(mr+r^{2}\log r) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mi>m</mi><mi>r</mi><mo>+</mo><msup><mi>r</mi><mrow><mn>2</mn></mrow></msup><mi>enregistrer</mi><mo>⁡</mo><mi>r</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(mr+r^{2}\log r)}</annotation></semantics></math><img src=$ ${\displaystyle O(ms+s^{2}\log \log r) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mi>m</mi><mi>s</mi><mo>+</mo><msup><mi>s</mi><mrow><mn>2</mn></mrow></msup><mi>enregistrer</mi><mo>⁡</mo><mi>enregistrer</mi><mo>⁡</mo><mi>r</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(ms+s^{2}\log \log r)}</annotation></semantics></math><img src=$

Solution par programmation linéaire

Le problème d'affectation peut être résolu en le présentant comme un programme linéaire . Par commodité, nous présenterons le problème de maximisation. Chaque arête ( i , j ) , où i appartient à A et j à T , est pondérée . Pour chaque arête , nous avons une variable _. Cette variable vaut 1 si l'arête est incluse dans l'appariement et 0 sinon. Nous définissons donc les contraintes du domaine : ${ extstyle w_{ij <semantics><mrow><mstyle><msub><mi>w</mi><mrow><mi>je</mi><mi>j</mi></mrow></msub></mstyle></mrow><annotation>{ extstyle w_{ij}}</annotation></semantics></math><img src=$ ${\displaystyle (i,j) <semantics><mrow><mstyle><mo>(</mo><mi>je</mi><mo>,</mo><mi>j</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle (i,j)}</annotation></semantics></math><img src=$ ${ extstyle x_{ij <semantics><mrow><mstyle><msub><mi>x</mi><mrow><mi>je</mi><mi>j</mi></mrow></msub></mstyle></mrow><annotation>{ extstyle x_{ij}}</annotation></semantics></math><img src=$ ${\displaystyle 0\leq x_{ij}\leq 1{ ext{ for }}i,j\in A,T,\, <semantics><mrow><mstyle><mn>0</mn><mo>≤</mo><msub><mi>x</mi><mrow><mi>je</mi><mi>j</mi></mrow></msub><mo>≤</mo><mn>1</mn><mrow><mtext> pour </mtext></mrow><mi>je</mi><mo>,</mo><mi>j</mi><mo>∈</mo><mi>UN</mi><mo>,</mo><mi>T</mi><mo>,</mo><mspace></mspace></mstyle></mrow><annotation>{\displaystyle 0\leq x_{ij}\leq 1{ ext{ pour }}i,j\in A,T,\,}</annotation></semantics></math><img src=$ ${\displaystyle x_{ij}\in \mathbb {Z} { ext{ for }}i,j\in A,T. <semantics><mrow><mstyle><msub><mi>x</mi><mrow><mi>je</mi><mi>j</mi></mrow></msub><mo>∈</mo><mrow><mi>Z</mi></mrow><mrow><mtext> pour </mtext></mrow><mi>je</mi><mo>,</mo><mi>j</mi><mo>∈</mo><mi>UN</mi><mo>,</mo><mi>T</mi><mo>.</mo></mstyle></mrow><annotation>{\displaystyle x_{ij}\in \mathbb {Z} { ext{ pour }}i,j\in A,T.}</annotation></semantics></math><img src=$

Le poids total de l'appariement est : . L'objectif est de trouver un appariement parfait de poids maximal. ${\displaystyle \sum _{(i,j)\in A imes T}w_{ij}x_{ij <semantics><mrow><mstyle><munder><mo>∑</mo><mrow><mo>(</mo><mi>je</mi><mo>,</mo><mi>j</mi><mo>)</mo><mo>∈</mo><mi>UN</mi><mo>×</mo><mi>T</mi></mrow></munder><msub><mi>w</mi><mrow><mi>je</mi><mi>j</mi></mrow></msub><msub><mi>x</mi><mrow><mi>je</mi><mi>j</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle \sum _{(i,j)\in A imes T}w_{ij}x_{ij}}</annotation></semantics></math><img src=$

Pour garantir que les variables représentent bien une correspondance parfaite, nous ajoutons des contraintes stipulant que chaque sommet est adjacent à exactement une arête de la correspondance, c'est-à-dire, ${\displaystyle {\begin{aligned}\sum _{j\in T}x_{ij}&=1{ ext{ for }}i\in A\\\sum _{i\in A}x_{ij}&=1{ ext{ for }}j\in T\end{aligned <semantics><mrow><mstyle><mrow><mtable><mtr><mtd><munder><mo>∑</mo><mrow><mi>j</mi><mo>∈</mo><mi>T</mi></mrow></munder><msub><mi>x</mi><mrow><mi>je</mi><mi>j</mi></mrow></msub></mtd><mtd><mi></mi><mo>=</mo><mn>1</mn><mrow><mtext> pour </mtext></mrow><mi>je</mi><mo>∈</mo><mi>UN</mi></mtd></mtr><mtr><mtd><munder><mo>∑</mo><mrow><mi>je</mi><mo>∈</mo><mi>UN</mi></mrow></munder><msub><mi>x</mi><mrow><mi>je</mi><mi>j</mi></mrow></msub></mtd><mtd><mi></mi><mo>=</mo><mn>1</mn><mrow><mtext> pour </mtext></mrow><mi>j</mi><mo>∈</mo><mi>T</mi></mtd></mtr></mtable></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{aligned}\sum _{j\in T}x_{ij}&=1{ ext{ pour }}i\in A\\\sum _{i\in A}x_{ij}&=1{ ext{ pour }}j\in T\end{aligned}}}</annotation></semantics></math><img src=$

Au final, nous avons le LP suivant :

${\displaystyle {\begin{aligned}{ ext{maximize}}&\sum _{(i,j)\in A imes T}w_{ij}x_{ij}\\{ ext{subject to}}&\sum _{j\in T}x_{ij}=1{ ext{ for }}i\in A,\,\sum _{i\in A}x_{ij}=1{ ext{ for }}j\in T\\&0\leq x_{ij}\leq 1{ ext{ for }}i,j\in A,T\\&x_{ij}\in \mathbb {Z} { ext{ for }}i,j\in A,T\end{aligned <semantics><mrow><mstyle><mrow><mtable><mtr><mtd><mrow><mtext>maximiser</mtext></mrow></mtd><mtd><mi></mi><munder><mo>∑</mo><mrow><mo>(</mo><mi>je</mi><mo>,</mo><mi>j</mi><mo>)</mo><mo>∈</mo><mi>UN</mi><mo>×</mo><mi>T</mi></mrow></munder><msub><mi>w</mi><mrow><mi>je</mi><mi>j</mi></mrow></msub><msub><mi>x</mi><mrow><mi>je</mi><mi>j</mi></mrow></msub></mtd></mtr><mtr><mtd><mrow><mtext>sous réserve de</mtext></mrow></mtd><mtd><mi></mi><munder><mo>∑</mo><mrow><mi>j</mi><mo>∈</mo><mi>T</mi></mrow></munder><msub><mi>x</mi><mrow><mi>je</mi><mi>j</mi></mrow></msub><mo>=</mo><mn>1</mn><mrow><mtext> pour </mtext></mrow><mi>je</mi><mo>∈</mo><mi>UN</mi><mo>,</mo><mspace></mspace><munder><mo>∑</mo><mrow><mi>je</mi><mo>∈</mo><mi>UN</mi></mrow></munder><msub><mi>x</mi><mrow><mi>je</mi><mi>j</mi></mrow></msub><mo>=</mo><mn>1</mn><mrow><mtext> pour </mtext></mrow><mi>j</mi><mo>∈</mo><mi>T</mi></mtd></mtr><mtr><mtd></mtd><mtd><mn>0</mn><mo>≤</mo><msub><mi>x</mi><mrow><mi>je</mi><mi>j</mi></mrow></msub><mo>≤</mo><mn>1</mn><mrow><mtext> pour </mtext></mrow><mi>je</mi><mo>,</mo><mi>j</mi><mo>∈</mo><mi>UN</mi><mo>,</mo><mi>T</mi></mtd></mtr><mtr><mtd></mtd><mtd><msub><mi>x</mi><mrow><mi>je</mi><mi>j</mi></mrow></msub><mo>∈</mo><mrow><mi>Z</mi></mrow><mrow><mtext> pour </mtext></mrow><mi>je</mi><mo>,</mo><mi>j</mi><mo>∈</mo><mi>UN</mi><mo>,</mo><mi>T</mi></mtd></mtr></mtable></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{aligned}{ ext{maximiser}}&\sum _{(i,j)\in A imes T}w_{ij}x_{ij}\\{ ext{sous contrainte}}&\sum _{j\in T}x_{ij}=1{ ext{ pour }}i\in A,\,\sum _{i\in A}x_{ij}=1{ ext{ pour }}j\in T\\&0\leq x_{ij}\leq 1{ ext{ pour }}i,j\in A,T\\&x_{ij}\in \mathbb {Z} { ext{ pour }}i,j\in A,T\end{aligned}}}</annotation></semantics></math><img src=$

Autres méthodes et algorithmes d'approximation

D'autres approches du problème d'affectation existent et sont présentées par Duan et Pettie (voir tableau II). Leurs travaux proposent un algorithme d'approximation pour le problème d'affectation (et le problème plus général d'appariement de poids maximal ), qui s'exécute en temps linéaire pour toute borne d'erreur fixée.

Affectation plusieurs-à-plusieurs

Dans le problème d'affectation simple, chaque agent est affecté à au plus une tâche et chaque tâche est affectée à au plus un agent. Dans le problème d'affectation plusieurs-à-plusieurs , chaque agent i peut prendre en charge jusqu'à c _i tâches ( c _i étant appelée la capacité de l'agent ), et chaque tâche j peut être prise en charge simultanément par au plus d _j agents ( d _j étant appelée la capacité de la tâche ). Si la somme des capacités est égale de part et d'autre (ci = dj ), le problème est équilibré , et l'objectif est de trouver une affectation parfaite (affecter exactement c _i tâches à chaque agent i et exactement d _j agents à chaque tâche j ) de sorte que le coût total soit minimal. ${\displaystyle \sum _{i}c_{i}=\sum _{j}d_{j <semantics><mrow><mstyle><munder><mo>∑</mo><mrow><mi>je</mi></mrow></munder><msub><mi>c</mi><mrow><mi>je</mi></mrow></msub><mo>=</mo><munder><mo>∑</mo><mrow><mi>j</mi></mrow></munder><msub><mi>d</mi><mrow><mi>j</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle \sum _{i}c_{i}=\sum _{j}d_{j}}</annotation></semantics></math><img src=$

Le problème peut être résolu par réduction au problème de flux de réseau à coût minimal . Construisez un réseau de flux avec les couches suivantes :

Couche 1 : Un nœud source s .
Couche 2 : un nœud pour chaque agent. Il existe un arc de s à chaque agent i , avec un coût 0 et une capacité c _i .
Niveau 3 : un nœud par tâche. Il existe un arc reliant chaque agent i à chaque tâche j , avec le coût correspondant et une capacité de 1.
Niveau 4 : Un nœud puits t . Il existe un arc de chaque tâche vers t , avec un coût 0 et une capacité d _j .

On peut trouver un flot maximal intégral de coût minimal en temps polynomial ; voir le problème du flot dans un réseau . Tout flot maximal intégral de ce réseau correspond à un appariement où au plus c _i tâches sont affectées à chaque agent i et au plus d _j agents sont affectés à chaque tâche j (dans le cas équilibré, exactement c _i tâches sont affectées à i et exactement d _j agents sont affectés à j ). Un flot maximal de coût minimal correspond à une affectation de coût minimal.

Généralisation

Formulé comme un problème de théorie des graphes, le problème d'affectation peut être étendu des graphes bipartis à des graphes quelconques. Le problème correspondant, qui consiste à trouver un couplage dans un graphe pondéré où la somme des poids est maximisée, est appelé problème de couplage de poids maximal .

Une autre généralisation du problème d'affectation consiste à étendre le nombre d'ensembles à apparier de deux à plusieurs. Ainsi, au lieu d'associer des agents à des tâches, le problème consiste à associer des agents à des tâches, à des intervalles de temps et à des lieux. On obtient alors le problème d'affectation multidimensionnelle .