Linearer Summenzuweisungslöser

In diesem Abschnitt wird der Belöser für lineare Summenzuweisungen beschrieben, ein spezialisierter Löser für einfache Zuweisungsprobleme, der schneller als der MIP- oder CP-SAT-Belöser sein kann. Die MIP- und CP-SAT-Beheber können jedoch ein viel größeres Spektrum an Problemen bewältigen. Daher sind sie in den meisten Fällen die beste Option.

Kostenmatrix

Die Kosten für Worker und Aufgaben sind in der folgenden Tabelle aufgeführt.

Worker	Aufgabe 0	Aufgabe 1	Aufgabe 2	Aufgabe 3
0	90	76	75	70
1	35	85	55	65
2	125	95	90	105
3	45	110	95	115

In den folgenden Abschnitten wird ein Python-Programm vorgestellt, das ein Zuweisungsproblem mithilfe des Rechners für lineare Summenzuweisungen löst.

Bibliotheken importieren

Unten sehen Sie den Code, mit dem die erforderliche Bibliothek importiert wird.

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;

Daten definieren

Mit dem folgenden Code werden die Daten für das Programm erstellt.

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();

Das Array ist die Kostenmatrix, deren Eintrag i, j die Kosten für den Worker i zum Ausführen der Aufgabe j sind. Es gibt vier Worker, die den Zeilen der Matrix entsprechen, und vier Aufgaben, die den Spalten entsprechen.

Matherechner erstellen

Das Programm verwendet den Lösungsverarbeiter Lineare Zuweisung, ein spezieller Matherechner.

Mit dem folgenden Code wird der Solver erstellt.

Python

assignment = linear_sum_assignment.SimpleLinearSumAssignment()

C++

SimpleLinearSumAssignment assignment;

Java

LinearSumAssignment assignment = new LinearSumAssignment();

C#

LinearSumAssignment assignment = new LinearSumAssignment();

Hinweis: Der Matherechner akzeptiert nur ganzzahlige Werte für die Gewichtungen und Werte. Im Abschnitt Einen Solver mit Daten, die keine Ganzzahlen sind, verwenden wird gezeigt, wie Sie den Solver verwenden, wenn Ihre Daten Werte enthalten, die keine ganzen Zahlen enthalten.

Einschränkungen hinzufügen

Durch den folgenden Code werden die Kosten für den Solver erhöht, indem Worker und Aufgaben in Schleifen ausgeführt werden.

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]);
        }
    }
}

Den Solver aufrufen

Der folgende Code ruft den Solver auf.

Python

status = assignment.solve()

C++

SimpleLinearSumAssignment::Status status = assignment.Solve();

Java

LinearSumAssignment.Status status = assignment.solve();

C#

LinearSumAssignment.Status status = assignment.Solve();

Ergebnisse anzeigen

Der folgende Code zeigt die Lösung an.

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}.");
}

Die folgende Ausgabe zeigt die optimale Zuweisung von Workern zu Aufgaben.

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

Das folgende Diagramm zeigt die Lösung als gestrichelte Kanten im Diagramm. Die Zahlen neben den gestrichelten Kanten sind ihre Kosten. Die Gesamtwartezeit dieser Zuweisung ist die Summe der Kosten für die gestrichelten Kanten, also 265.

In der Grafiktheorie wird eine Reihe von Kanten in einer zweiteiligen Grafik, die jeden Knoten auf der linken Seite mit genau einem Knoten auf der rechten Seite vergleicht, als perfekte Übereinstimmung bezeichnet.

Das gesamte Programm

Hier ist das gesamte Programm.

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}.");
        }
    }
}

Lösung, wenn Mitarbeiter nicht alle Aufgaben ausführen können

Im vorherigen Beispiel wurde davon ausgegangen, dass alle Worker alle Aufgaben ausführen können. Dies ist jedoch nicht immer der Fall. Ein Worker kann eine oder mehrere Aufgaben aus verschiedenen Gründen nicht ausführen. Sie können das obige Programm jedoch einfach entsprechend anpassen.

Angenommen, Worker 0 kann Aufgabe 3 nicht ausführen. Nehmen Sie die folgenden Änderungen vor, um das Programm entsprechend zu ändern:

1. Ändern Sie den Eintrag 0, 3 der Kostenmatrix in den String 'NA'. Es kann ein beliebiger String verwendet werden.

   cost = [[90, 76, 75, 'NA'],
       [35, 85, 55, 65],
       [125, 95, 90, 105],
       [45, 110, 95, 115]]

2. Fügen Sie im Codeabschnitt, der dem Solver Kosten zuweist, die Zeile if cost[worker][task] != 'NA': hinzu, wie unten dargestellt.

   for worker in range(0, rows):
   for task in range(0, cols):
     if cost[worker][task] != 'NA':
       assignment.AddArcWithCost(worker, task, cost[worker][task])

   Die hinzugefügte Zeile verhindert, dass jede Kante, deren Eintrag in der Kostenmatrix 'NA' ist, dem Matherechner hinzugefügt wird.

Nachdem Sie diese Änderungen vorgenommen und den geänderten Code ausgeführt haben, wird die folgende Ausgabe angezeigt:

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

Beachten Sie, dass die Gesamtkosten jetzt höher sind als für die ursprüngliche Aufgabe. Dies ist nicht überraschend, da im ursprünglichen Problem die optimale Lösung Worker 0 der Aufgabe 3 zugewiesen hat, während im geänderten Problem diese Zuweisung nicht zulässig ist.

Um zu sehen, was passiert, wenn mehr Worker Aufgaben nicht ausführen können, können Sie weitere Einträge der Kostenmatrix durch 'NA' ersetzen, um zusätzliche Worker anzugeben, die bestimmte Aufgaben nicht ausführen können:

cost = [[90, 76, 'NA', 'NA'],
        [35, 85, 'NA', 'NA'],
        [125, 95, 'NA','NA'],
        [45, 110, 95, 115]]

Wenn Sie das Programm diesmal ausführen, erhalten Sie ein negatives Ergebnis:

No assignment is possible.

Das bedeutet, dass es keine Möglichkeit gibt, Worker Aufgaben zuzuweisen, sodass jeder Worker eine andere Aufgabe ausführt. Sie können den Grund dafür in der Grafik für das Problem sehen (in dem es keine Kanten gibt, die den Werten von 'NA' in der Kostenmatrix entsprechen).

Da die Knoten für die drei Worker 0, 1 und 2 nur mit den beiden Knoten für die Aufgaben 0 und 1 verbunden sind, ist es nicht möglich, diesen Workern unterschiedliche Aufgaben zuzuweisen.

Der Ehesatz

Es gibt ein bekanntes Ergebnis in der Grafiktheorie, das Ehesatz genannt wird. Es gibt genau an, wann jeder Knoten auf der linken Seite einem bestimmten Knoten auf der rechten Seite in einer zweiteiligen Grafik wie dem obigen zugeordnet werden kann. Eine solche Zuweisung wird als perfekte Zuordnung bezeichnet. Kurz gesagt besagt der Satz, dass dies möglich ist, wenn auf der linken Seite keine Teilmenge von Knoten vorhanden ist (wie der im vorherigen Beispiel), deren Ränder zu einer kleineren Gruppe von Knoten auf der rechten Seite führen.

Genauer gesagt besagt der Satz, dass ein zweiteiliger Graph eine perfekte Übereinstimmung aufweist, wenn und nur wenn für eine Teilmenge S der Knoten auf der linken Seite der Grafik der Satz von Knoten auf der rechten Seite der Grafik, die durch eine Kante mit einem Knoten in S verbunden sind, mindestens so groß ist wie S.