En esta sección, se describe el solucionador de asignaciones de suma lineal, un agente de resolución especializado para el problema de asignación simple, que puede ser más rápido que el solucionador de problemas MIP o CP-SAT. Sin embargo, los solucionadores de MIP y CP-SAT pueden manejar una variedad más amplia de problemas, por lo que en la mayoría de los casos son la mejor opción.
Matriz de costos
Los costos de los trabajadores y las tareas se indican en la siguiente tabla.
Trabajador | Tarea 0 | Tarea 1 | Tarea 2 | Tarea 3 |
---|---|---|---|---|
0 | 90 | 76 | 75 | 70 |
1 | 35 | 85 | 55 | 65 |
2 | 125 | 95 | 90 | 105 |
3 | 45 | 110 | 95 | 115 |
En las siguientes secciones, se presenta un programa de Python que resuelve un problema de asignación con el solucionador de asignaciones de sumas lineales.
Importa las bibliotecas
A continuación, se muestra el código que importa la biblioteca requerida.
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;
Define los datos
El siguiente código crea los datos para el 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();
El array es la matriz de costos, cuya entrada i, j es el costo del trabajador i para realizar la tarea j. Hay cuatro trabajadores, que corresponden a las filas de la matriz, y cuatro tareas, que corresponden a las columnas.
Crea el solucionador
El programa usa el solucionador de asignación lineal, un solucionador especializado para problemas de asignaciones.
El siguiente código crea el solucionador.
Python
assignment = linear_sum_assignment.SimpleLinearSumAssignment()
C++
SimpleLinearSumAssignment assignment;
Java
LinearSumAssignment assignment = new LinearSumAssignment();
C#
LinearSumAssignment assignment = new LinearSumAssignment();
Agrega las restricciones
Con el siguiente código, se agregan los costos a la resolución mediante la repetición de los trabajadores y las tareas.
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]); } } }
Cómo invocar el solucionador
El siguiente código invoca el solucionador.
Python
status = assignment.solve()
C++
SimpleLinearSumAssignment::Status status = assignment.Solve();
Java
LinearSumAssignment.Status status = assignment.solve();
C#
LinearSumAssignment.Status status = assignment.Solve();
Muestra los resultados
El siguiente código muestra la solución.
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}."); }
En el siguiente resultado, se muestra la asignación óptima de trabajadores a las tareas.
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
En el siguiente gráfico, se muestra la solución como los bordes discontinuos en el gráfico. Los números que aparecen junto a los bordes discontinuos son sus costos. El tiempo de espera total de esta asignación es la suma de los costos de las aristas punteadas, que es 265.
En la teoría de grafos, un conjunto de aristas en un gráfico bipartito que coincide con cada nodo de la izquierda con exactamente un nodo del lado derecho se denomina coincidencia perfecta.
Todo el programa
Aquí está el programa completo.
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}."); } } }
Solución cuando los trabajadores no pueden realizar todas las tareas
En el ejemplo anterior, suponemos que todos los trabajadores pueden realizar todas las tareas. Sin embargo, este no siempre es el caso: es posible que un trabajador no pueda realizar una o más tareas por varias razones. Sin embargo, es fácil modificar el programa anterior para controlar esto.
Como ejemplo, supongamos que el trabajador 0 no puede realizar la tarea 3. Si deseas modificar el programa para que tenga esto en cuenta, realiza los siguientes cambios:
- Cambia la entrada 0, 3 de la matriz de costos a la cadena
'NA'
. (cualquier string funcionará).cost = [[90, 76, 75, 'NA'], [35, 85, 55, 65], [125, 95, 90, 105], [45, 110, 95, 115]]
- En la sección del código que asigna costos a la resolución, agrega la línea
if cost[worker][task] != 'NA':
, como se muestra a continuación.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 línea agregada evita que cualquier arista cuya entrada en la matriz de costos sea'NA'
se agregue al solucionador.
Después de realizar estos cambios y ejecutar el código modificado, verás el siguiente resultado:
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
Observa que ahora el costo total es más alto que el del problema original. Esto no es de extrañar, ya que, en el problema original, la solución óptima asignó al trabajador 0 a la tarea 3, mientras que en el problema modificado, esa asignación no está permitida.
Para ver qué sucede si más trabajadores no pueden realizar tareas, puedes reemplazar más entradas de la matriz de costos por 'NA'
para indicar trabajadores adicionales que no pueden realizar ciertas tareas:
cost = [[90, 76, 'NA', 'NA'], [35, 85, 'NA', 'NA'], [125, 95, 'NA','NA'], [45, 110, 95, 115]]
Cuando ejecutas el programa esta vez, obtienes un resultado negativo:
No assignment is possible.
Esto significa que no hay forma de asignar trabajadores a tareas, de modo que cada trabajador realice una tarea diferente. Puedes ver por qué es así si observas el grafo del problema (en el que no hay aristas correspondientes a los valores de 'NA'
en la matriz de costos).
Debido a que los nodos de los tres trabajadores 0, 1 y 2 solo están conectados a los dos nodos para las tareas 0 y 1, no es posible asignar tareas distintas a estos trabajadores.
Teorema del matrimonio
Existe un resultado conocido en la teoría de gráficos, llamado El teorema del matrimonio, que nos indica exactamente cuándo puedes asignar cada nodo de la izquierda a un nodo distinto del lado derecho, en un grafo bipartito como el anterior. Esta asignación se denomina coincidencia perfecta. En pocas palabras, el teorema indica que esto es posible si no hay un subconjunto de nodos a la izquierda (como el del ejemplo anterior) cuyos bordes conducen a un conjunto más pequeño de nodos en el lado derecho.
Más precisamente, el teorema dice que un grafo bipartito tiene una coincidencia perfecta si y solo si para cualquier subconjunto S de los nodos en el lado izquierdo del grafo, el conjunto de nodos en el lado derecho del grafo que están conectados por un borde a un nodo en S es al menos tan grande como S.