Cette section décrit le résolveur d'attribution de somme linéaire, spécialisé dans les problèmes d'attribution simple, qui peut être plus rapide que le résolveur MIP ou CP-SAT. Toutefois, les résolveurs MIP et CP-SAT peuvent gérer un plus large éventail de problèmes. Ils constituent donc dans la plupart des cas la meilleure option.
Matrice des coûts
Les coûts des workers et des tâches sont indiqués dans le tableau ci-dessous.
Nœud de calcul | Tâche 0 | Tâche 1 | Tâche 2 | Tâche 3 |
---|---|---|---|---|
0 | 90 | 76 | 75 | 70 |
1 | 35 | 85 | 55 | 65 |
2 | 125 | 95 | 90 | 105 |
3 | 45 | 110 | 95 | 115 |
Les sections suivantes présentent un programme Python qui résout un problème d'attribution à l'aide de la solution d'attribution de somme linéaire.
Importer les bibliothèques
Vous trouverez ci-dessous le code qui importe la bibliothèque requise.
Python
import numpy as np from ortools.graph.python import linear_sum_assignment
C++
#include "ortools/graph/assignment.h" #include <cstdint> #include <numeric> #include <string> #include <vector>
Java
import com.google.ortools.Loader; import com.google.ortools.graph.LinearSumAssignment; import java.util.stream.IntStream;
C#
using System; using System.Collections.Generic; using System.Linq; using Google.OrTools.Graph;
Définir les données
Le code suivant crée les données pour le programme.
Python
costs = np.array( [ [90, 76, 75, 70], [35, 85, 55, 65], [125, 95, 90, 105], [45, 110, 95, 115], ] ) # Let's transform this into 3 parallel vectors (start_nodes, end_nodes, # arc_costs) end_nodes_unraveled, start_nodes_unraveled = np.meshgrid( np.arange(costs.shape[1]), np.arange(costs.shape[0]) ) start_nodes = start_nodes_unraveled.ravel() end_nodes = end_nodes_unraveled.ravel() arc_costs = costs.ravel()
C++
const int num_workers = 4; std::vector<int> all_workers(num_workers); std::iota(all_workers.begin(), all_workers.end(), 0); const int num_tasks = 4; std::vector<int> all_tasks(num_tasks); std::iota(all_tasks.begin(), all_tasks.end(), 0); const std::vector<std::vector<int>> costs = {{ {{90, 76, 75, 70}}, // Worker 0 {{35, 85, 55, 65}}, // Worker 1 {{125, 95, 90, 105}}, // Worker 2 {{45, 110, 95, 115}}, // Worker 3 }};
Java
final int[][] costs = { {90, 76, 75, 70}, {35, 85, 55, 65}, {125, 95, 90, 105}, {45, 110, 95, 115}, }; final int numWorkers = 4; final int numTasks = 4; final int[] allWorkers = IntStream.range(0, numWorkers).toArray(); final int[] allTasks = IntStream.range(0, numTasks).toArray();
C#
int[,] costs = { { 90, 76, 75, 70 }, { 35, 85, 55, 65 }, { 125, 95, 90, 105 }, { 45, 110, 95, 115 }, }; int numWorkers = 4; int[] allWorkers = Enumerable.Range(0, numWorkers).ToArray(); int numTasks = 4; int[] allTasks = Enumerable.Range(0, numTasks).ToArray();
Le tableau correspond à la matrice des coûts, dont l'entrée i, j correspond au coût d'exécution de la tâche j par le nœud de calcul i. Il y a quatre nœuds de calcul, correspondant aux lignes de la matrice, et quatre tâches, correspondant aux colonnes.
Créer le résolveur
Le programme utilise le résolveur d'attribution linéaire, un résolveur spécialisé pour le problème d'attribution.
Le code suivant crée le résolveur.
Python
assignment = linear_sum_assignment.SimpleLinearSumAssignment()
C++
SimpleLinearSumAssignment assignment;
Java
LinearSumAssignment assignment = new LinearSumAssignment();
C#
LinearSumAssignment assignment = new LinearSumAssignment();
Ajouter les contraintes
Le code suivant ajoute les coûts au résolveur en exécutant une boucle sur les nœuds de calcul et les tâches.
Python
assignment.add_arcs_with_cost(start_nodes, end_nodes, arc_costs)
C++
for (int w : all_workers) { for (int t : all_tasks) { if (costs[w][t]) { assignment.AddArcWithCost(w, t, costs[w][t]); } } }
Java
// Add each arc. for (int w : allWorkers) { for (int t : allTasks) { if (costs[w][t] != 0) { assignment.addArcWithCost(w, t, costs[w][t]); } } }
C#
// Add each arc. foreach (int w in allWorkers) { foreach (int t in allTasks) { if (costs[w, t] != 0) { assignment.AddArcWithCost(w, t, costs[w, t]); } } }
Appeler le résolveur
Le code suivant appelle le résolveur.
Python
status = assignment.solve()
C++
SimpleLinearSumAssignment::Status status = assignment.Solve();
Java
LinearSumAssignment.Status status = assignment.solve();
C#
LinearSumAssignment.Status status = assignment.Solve();
Afficher les résultats
Le code suivant affiche la solution.
Python
if status == assignment.OPTIMAL: print(f"Total cost = {assignment.optimal_cost()}\n") for i in range(0, assignment.num_nodes()): print( f"Worker {i} assigned to task {assignment.right_mate(i)}." + f" Cost = {assignment.assignment_cost(i)}" ) elif status == assignment.INFEASIBLE: print("No assignment is possible.") elif status == assignment.POSSIBLE_OVERFLOW: print("Some input costs are too large and may cause an integer overflow.")
C++
if (status == SimpleLinearSumAssignment::OPTIMAL) { LOG(INFO) << "Total cost: " << assignment.OptimalCost(); for (int worker : all_workers) { LOG(INFO) << "Worker " << std::to_string(worker) << " assigned to task " << std::to_string(assignment.RightMate(worker)) << ". Cost: " << std::to_string(assignment.AssignmentCost(worker)) << "."; } } else { LOG(INFO) << "Solving the linear assignment problem failed."; }
Java
if (status == LinearSumAssignment.Status.OPTIMAL) { System.out.println("Total cost: " + assignment.getOptimalCost()); for (int worker : allWorkers) { System.out.println("Worker " + worker + " assigned to task " + assignment.getRightMate(worker) + ". Cost: " + assignment.getAssignmentCost(worker)); } } else { System.out.println("Solving the min cost flow problem failed."); System.out.println("Solver status: " + status); }
C#
if (status == LinearSumAssignment.Status.OPTIMAL) { Console.WriteLine($"Total cost: {assignment.OptimalCost()}."); foreach (int worker in allWorkers) { Console.WriteLine($"Worker {worker} assigned to task {assignment.RightMate(worker)}. " + $"Cost: {assignment.AssignmentCost(worker)}."); } } else { Console.WriteLine("Solving the linear assignment problem failed."); Console.WriteLine($"Solver status: {status}."); }
Le résultat ci-dessous montre l'affectation optimale des workers aux tâches.
Total cost = 265 Worker 0 assigned to task 3. Cost = 70 Worker 1 assigned to task 2. Cost = 55 Worker 2 assigned to task 1. Cost = 95 Worker 3 assigned to task 0. Cost = 45 Time = 0.000147 seconds
Le graphique suivant présente la solution sous forme d'arêtes en pointillés. Les chiffres figurant à côté des arêtes en pointillés correspondent aux coûts. Le temps d'attente total de cette attribution correspond à la somme des coûts pour les arêtes en pointillés, soit 265.
En théorie des graphes, un ensemble d'arêtes d'un graphe bipartite qui correspond à chaque nœud de gauche et à un seul nœud à droite est appelé correspondance parfaite.
L'ensemble du programme
Voici le programme complet.
Python
"""Solve assignment problem using linear assignment solver.""" import numpy as np from ortools.graph.python import linear_sum_assignment def main(): """Linear Sum Assignment example.""" assignment = linear_sum_assignment.SimpleLinearSumAssignment() costs = np.array( [ [90, 76, 75, 70], [35, 85, 55, 65], [125, 95, 90, 105], [45, 110, 95, 115], ] ) # Let's transform this into 3 parallel vectors (start_nodes, end_nodes, # arc_costs) end_nodes_unraveled, start_nodes_unraveled = np.meshgrid( np.arange(costs.shape[1]), np.arange(costs.shape[0]) ) start_nodes = start_nodes_unraveled.ravel() end_nodes = end_nodes_unraveled.ravel() arc_costs = costs.ravel() assignment.add_arcs_with_cost(start_nodes, end_nodes, arc_costs) status = assignment.solve() if status == assignment.OPTIMAL: print(f"Total cost = {assignment.optimal_cost()}\n") for i in range(0, assignment.num_nodes()): print( f"Worker {i} assigned to task {assignment.right_mate(i)}." + f" Cost = {assignment.assignment_cost(i)}" ) elif status == assignment.INFEASIBLE: print("No assignment is possible.") elif status == assignment.POSSIBLE_OVERFLOW: print("Some input costs are too large and may cause an integer overflow.") if __name__ == "__main__": main()
C++
#include "ortools/graph/assignment.h" #include <cstdint> #include <numeric> #include <string> #include <vector> namespace operations_research { // Simple Linear Sum Assignment Problem (LSAP). void AssignmentLinearSumAssignment() { SimpleLinearSumAssignment assignment; const int num_workers = 4; std::vector<int> all_workers(num_workers); std::iota(all_workers.begin(), all_workers.end(), 0); const int num_tasks = 4; std::vector<int> all_tasks(num_tasks); std::iota(all_tasks.begin(), all_tasks.end(), 0); const std::vector<std::vector<int>> costs = {{ {{90, 76, 75, 70}}, // Worker 0 {{35, 85, 55, 65}}, // Worker 1 {{125, 95, 90, 105}}, // Worker 2 {{45, 110, 95, 115}}, // Worker 3 }}; for (int w : all_workers) { for (int t : all_tasks) { if (costs[w][t]) { assignment.AddArcWithCost(w, t, costs[w][t]); } } } SimpleLinearSumAssignment::Status status = assignment.Solve(); if (status == SimpleLinearSumAssignment::OPTIMAL) { LOG(INFO) << "Total cost: " << assignment.OptimalCost(); for (int worker : all_workers) { LOG(INFO) << "Worker " << std::to_string(worker) << " assigned to task " << std::to_string(assignment.RightMate(worker)) << ". Cost: " << std::to_string(assignment.AssignmentCost(worker)) << "."; } } else { LOG(INFO) << "Solving the linear assignment problem failed."; } } } // namespace operations_research int main() { operations_research::AssignmentLinearSumAssignment(); return EXIT_SUCCESS; }
Java
package com.google.ortools.graph.samples; import com.google.ortools.Loader; import com.google.ortools.graph.LinearSumAssignment; import java.util.stream.IntStream; /** Minimal Linear Sum Assignment problem. */ public class AssignmentLinearSumAssignment { public static void main(String[] args) { Loader.loadNativeLibraries(); LinearSumAssignment assignment = new LinearSumAssignment(); final int[][] costs = { {90, 76, 75, 70}, {35, 85, 55, 65}, {125, 95, 90, 105}, {45, 110, 95, 115}, }; final int numWorkers = 4; final int numTasks = 4; final int[] allWorkers = IntStream.range(0, numWorkers).toArray(); final int[] allTasks = IntStream.range(0, numTasks).toArray(); // Add each arc. for (int w : allWorkers) { for (int t : allTasks) { if (costs[w][t] != 0) { assignment.addArcWithCost(w, t, costs[w][t]); } } } LinearSumAssignment.Status status = assignment.solve(); if (status == LinearSumAssignment.Status.OPTIMAL) { System.out.println("Total cost: " + assignment.getOptimalCost()); for (int worker : allWorkers) { System.out.println("Worker " + worker + " assigned to task " + assignment.getRightMate(worker) + ". Cost: " + assignment.getAssignmentCost(worker)); } } else { System.out.println("Solving the min cost flow problem failed."); System.out.println("Solver status: " + status); } } private AssignmentLinearSumAssignment() {} }
C#
using System; using System.Collections.Generic; using System.Linq; using Google.OrTools.Graph; public class AssignmentLinearSumAssignment { static void Main() { LinearSumAssignment assignment = new LinearSumAssignment(); int[,] costs = { { 90, 76, 75, 70 }, { 35, 85, 55, 65 }, { 125, 95, 90, 105 }, { 45, 110, 95, 115 }, }; int numWorkers = 4; int[] allWorkers = Enumerable.Range(0, numWorkers).ToArray(); int numTasks = 4; int[] allTasks = Enumerable.Range(0, numTasks).ToArray(); // Add each arc. foreach (int w in allWorkers) { foreach (int t in allTasks) { if (costs[w, t] != 0) { assignment.AddArcWithCost(w, t, costs[w, t]); } } } LinearSumAssignment.Status status = assignment.Solve(); if (status == LinearSumAssignment.Status.OPTIMAL) { Console.WriteLine($"Total cost: {assignment.OptimalCost()}."); foreach (int worker in allWorkers) { Console.WriteLine($"Worker {worker} assigned to task {assignment.RightMate(worker)}. " + $"Cost: {assignment.AssignmentCost(worker)}."); } } else { Console.WriteLine("Solving the linear assignment problem failed."); Console.WriteLine($"Solver status: {status}."); } } }
Solution utilisée lorsque les nœuds de calcul ne peuvent pas effectuer toutes les tâches
Dans l'exemple précédent, nous avons supposé que tous les nœuds de calcul pouvaient effectuer toutes les tâches. Mais ce n'est pas toujours le cas. Un nœud de calcul peut ne pas être en mesure d'effectuer une ou plusieurs tâches pour diverses raisons. Cependant, il est facile de modifier le programme ci-dessus pour gérer cela.
Par exemple, supposons que le nœud de calcul 0 ne puisse pas effectuer la tâche 3. Pour modifier le programme en tenant compte de cela, apportez les modifications suivantes:
- Remplacez l'entrée 0, 3 de la matrice des coûts par la chaîne
'NA'
. (N'importe quelle chaîne est acceptée.)cost = [[90, 76, 75, 'NA'], [35, 85, 55, 65], [125, 95, 90, 105], [45, 110, 95, 115]]
- Dans la section du code qui attribue des coûts au résolveur, ajoutez la ligne
if cost[worker][task] != 'NA':
, comme indiqué ci-dessous.for worker in range(0, rows): for task in range(0, cols): if cost[worker][task] != 'NA': assignment.AddArcWithCost(worker, task, cost[worker][task])
La ligne ajoutée empêche l'ajout au résolveur de toute arête dont l'entrée dans la matrice des coûts est'NA'
.
Une fois ces modifications effectuées et exécuté le code modifié, la sortie suivante s'affiche:
Total cost = 276 Worker 0 assigned to task 1. Cost = 76 Worker 1 assigned to task 3. Cost = 65 Worker 2 assigned to task 2. Cost = 90 Worker 3 assigned to task 0. Cost = 45
Notez que le coût total est désormais plus élevé que pour le problème d'origine. Cela n'est pas surprenant, car dans le problème d'origine, la solution optimale a attribué le nœud de calcul 0 à la tâche 3, tandis que dans le problème modifié, cette attribution n'est pas autorisée.
Pour voir ce qui se passe si davantage de nœuds de calcul ne peuvent pas effectuer de tâches, vous pouvez remplacer plus d'entrées de la matrice des coûts par 'NA'
afin d'identifier les nœuds de calcul supplémentaires qui ne peuvent pas effectuer certaines tâches:
cost = [[90, 76, 'NA', 'NA'], [35, 85, 'NA', 'NA'], [125, 95, 'NA','NA'], [45, 110, 95, 115]]
Lorsque vous exécutez le programme cette fois, vous obtenez un résultat négatif:
No assignment is possible.
Cela signifie qu'il n'existe aucun moyen d'affecter des nœuds de calcul à des tâches de sorte que chacun effectue une tâche différente. Vous pouvez en comprendre la raison en examinant le graphique du problème (dans lequel il n'y a pas d'arêtes correspondant aux valeurs de 'NA'
dans la matrice des coûts).
Étant donné que les nœuds des trois nœuds de calcul 0, 1 et 2 ne sont connectés qu'aux deux nœuds des tâches 0 et 1, il est impossible de leur attribuer des tâches distinctes.
Le théorème du mariage
Il existe un résultat bien connu dans la théorie des graphes, appelé théorème du mariage, qui nous indique exactement à quel moment vous pouvez affecter chaque nœud situé à gauche à un nœud distinct à droite, dans un graphique bipartite comme celui présenté ci-dessus. Ce type d'attribution s'appelle une correspondance parfaite. En résumé, le théorème indique que c'est possible s'il n'y a pas de sous-ensemble de nœuds à gauche (comme dans l'exemple précédent) dont les arêtes conduisent à un plus petit ensemble de nœuds à droite.
Plus précisément, le théorème affirme qu'un graphique bipartite présente une correspondance parfaite si et seulement si, pour tout sous-ensemble S des nœuds situés à gauche du graphique, l'ensemble de nœuds situés à droite du graphique reliés par une arête à un nœud dans S est au moins aussi grand que S.