Esta seção descreve o solucionador de atribuição de soma linear, um solucionador especializado para problemas de atribuição simples, que pode ser mais rápido do que o solucionador MIP ou CP-SAT. No entanto, os solucionadores MIP e CP-SAT podem lidar com uma variedade muito maior de problemas. Portanto, na maioria dos casos, eles são a melhor opção.
Matriz de custos
Os custos para workers e tarefas são indicados na tabela abaixo.
intelectual | Tarefa 0 | Tarefa 1 | Tarefa 2 | Tarefa 3 |
---|---|---|---|---|
0 | 90 | 76 | 75 | 70 |
1 | 35 | 85 | 55 | 65 |
2 | 125 | 95 | 90 | 105 |
3 | 45 | 110 | 95 | 115 |
As seções a seguir apresentam um programa em Python que resolve um problema de atribuição usando o solucionador de atribuição de soma linear.
Importar as bibliotecas
O código que importa a biblioteca necessária é mostrado abaixo.
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;
Definir os dados
O código a seguir cria os dados para o programa.
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();
A matriz é a matriz de custo, em que a entrada i, j é o custo do worker i para executar a tarefa j. Há quatro workers, correspondentes às linhas da matriz, e quatro tarefas, correspondentes às colunas.
Criar o solucionador
O programa usa o solucionador de atribuição linear, um solucionador especializado para o problema de atribuição.
O código a seguir cria o solucionador.
Python
assignment = linear_sum_assignment.SimpleLinearSumAssignment()
C++
SimpleLinearSumAssignment assignment;
Java
LinearSumAssignment assignment = new LinearSumAssignment();
C#
LinearSumAssignment assignment = new LinearSumAssignment();
Adicione as restrições
O código a seguir adiciona os custos ao solucionador ao estabelecer loop sobre workers e tarefas.
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]); } } }
Invocar o solucionador
O código a seguir invoca o solucionador.
Python
status = assignment.solve()
C++
SimpleLinearSumAssignment::Status status = assignment.Solve();
Java
LinearSumAssignment.Status status = assignment.solve();
C#
LinearSumAssignment.Status status = assignment.Solve();
Mostrar os resultados
O código a seguir exibe a solução.
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}."); }
A saída abaixo mostra a melhor atribuição de workers a tarefas.
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
No gráfico a seguir, mostramos a solução como as bordas tracejadas. Os números ao lado das bordas tracejadas são os custos. O tempo de espera total dessa atribuição é a soma dos custos das bordas tracejadas, que é 265.
Na teoria dos grafos, um conjunto de arestas em um grafo bipartido que corresponde cada nó à esquerda a exatamente um à direita é chamado de correspondência perfeita.
Todo o programa
Confira o programa inteiro.
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}."); } } }
Solução quando os workers não podem executar todas as tarefas
No exemplo anterior, presumimos que todos os workers podem executar todas as tarefas. Mas esse nem sempre é o caso: um worker pode não conseguir executar uma ou mais tarefas por vários motivos. No entanto, é fácil modificar o programa acima para lidar com isso.
Como exemplo, suponha que o worker 0 não possa executar a tarefa 3. Para modificar o programa para levar isso em conta, faça as seguintes alterações:
- Mude as entradas 0 e 3 da matriz de custos para a string
'NA'
. Qualquer string funcionará.cost = [[90, 76, 75, 'NA'], [35, 85, 55, 65], [125, 95, 90, 105], [45, 110, 95, 115]]
- Na seção do código que atribui custos ao solucionador, adicione a linha
if cost[worker][task] != 'NA':
, conforme mostrado abaixo.for worker in range(0, rows): for task in range(0, cols): if cost[worker][task] != 'NA': assignment.AddArcWithCost(worker, task, cost[worker][task])
A linha adicionada impede que qualquer borda cuja entrada na matriz de custo seja'NA'
seja adicionada ao solucionador.
Depois de fazer essas alterações e executar o código modificado, você verá a seguinte saída:
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
Observe que o custo total é maior agora do que no problema original. Isso não é uma surpresa, já que no problema original a solução ideal atribuiu o worker 0 à tarefa 3, enquanto no problema modificado, a atribuição não é permitida.
Para ver o que acontece se mais workers não conseguirem executar tarefas, substitua mais entradas da matriz de custo por 'NA'
para indicar workers adicionais que não podem executar determinadas tarefas:
cost = [[90, 76, 'NA', 'NA'], [35, 85, 'NA', 'NA'], [125, 95, 'NA','NA'], [45, 110, 95, 115]]
Ao executar o programa desta vez, você obtém um resultado negativo:
No assignment is possible.
Isso significa que não é possível atribuir workers a tarefas para que cada um
execute uma tarefa diferente. Para entender por que isso acontece, observe o gráfico do problema, em que não há arestas correspondentes aos valores de 'NA'
na matriz de custo.
Como os nós dos três workers 0, 1 e 2 estão conectados apenas aos dois nós das tarefas 0 e 1, não é possível atribuir tarefas distintas a eles.
O teorema do casamento
Existe um resultado bem conhecido na teoria dos grafos, chamado O Teorema do Casamento, que nos diz exatamente quando é possível atribuir cada nó à esquerda a um nó distinto à direita, em um grafo bipartido como o acima. Essa atribuição é chamada de correspondência perfeita. Em resumo, o teorema afirma que isso é possível se não houver um subconjunto de nós à esquerda (como o do exemplo anterior) com arestas que levem a um conjunto menor de nós à direita.
Mais precisamente, o teorema diz que um gráfico bipartido tem uma correspondência perfeita se, e somente se, para qualquer subconjunto S dos nós no lado esquerdo do gráfico, o conjunto de nós no lado direito do gráfico que estão conectados por uma borda a um nó em S for pelo menos tão grande quanto S.