Liniowe rozwiązanie do przypisywania sum linearnych

W tej sekcji opisujemy narzędzie do rozwiązywania problemów z sumą liniową, czyli specjalistyczną funkcję do prostego zadania z przydziałem. Może to być szybsze niż Rozwiązanie MIP lub CP-SAT. Rozwiązania MIP i CP-SAT potrafią jednak są bardziej przydatne i w większości przypadków są najlepszym rozwiązaniem.

Macierz kosztów

Koszty instancji roboczych i zadań zostały przedstawione w tabeli poniżej.

Zasób roboczy	Zadanie 0	Zadanie 1	Zadanie 2	Zadanie 3
0	90	76	75	70
1	35	85	55	65
2	125	95	90	105
3	45	110	95	115

W poniższych sekcjach przedstawiamy program w Pythonie, który rozwiązuje zadanie zadania za pomocą narzędzia do rozwiązywania problemów z sumą liniową.

Zaimportuj biblioteki

Poniżej znajduje się kod, który importuje wymaganą bibliotekę.

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;

Zdefiniuj dane

Poniższy kod tworzy dane dla programu.

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

Tablica jest macierzą kosztów, w której pozycja i, j to koszt instancji roboczej i. aby wykonać zadanie j. Istnieją 4 instancje robocze odpowiadające wierszom i 4 zadania odpowiadające kolumnom.

Tworzenie rozwiązania

Program wykorzystuje rozwiązanie przypisania liniowego, specjalistyczne rozwiązanie zadania.

Ten kod tworzy rozwiązanie.

Python

assignment = linear_sum_assignment.SimpleLinearSumAssignment()

C++

SimpleLinearSumAssignment assignment;

Java

LinearSumAssignment assignment = new LinearSumAssignment();

C#

LinearSumAssignment assignment = new LinearSumAssignment();

Uwaga: narzędzie do rozwiązywania problemów z przypisaniem sumy liniowej akceptuje tylko wartości całkowite dla wag i wartości. Sekcja Używanie rozwiązania z danymi niebędącymi liczbą całkowitą pokazuje, jak używać rozwiązania, jeśli dane zawierają wartości niecałkowite.

Dodaj ograniczenia

Poniższy kod dodaje koszty rozwiązania do rozwiązania przez zapętlenie instancji roboczych i zadania.

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

Wywołaj rozwiązanie

Następujący kod wywołuje rozwiązanie.

Python

status = assignment.solve()

C++

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

Java

LinearSumAssignment.Status status = assignment.solve();

C#

LinearSumAssignment.Status status = assignment.Solve();

Wyświetl wyniki

Poniższy kod wyświetla rozwiązanie.

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

Dane wyjściowe poniżej pokazują optymalne przypisanie instancji roboczych do zadań.

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

Wykres poniżej przedstawia rozwiązanie w postaci przerywanych krawędzi na wykresie. obok przerywanych krawędzi, to ich koszty. Łączny czas oczekiwania tego przypisania to suma kosztów przerywane krawędzie, czyli 265.

W teorii grafu zbiór krawędzi na grafie dwuczęściowym, który pasuje do każdego węzła na ale tylko jeden węzeł po prawej stronie jest nazywany idealnym dopasowaniem.

Cały program

Oto cały program.

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

Rozwiązanie, gdy instancje robocze nie mogą wykonywać wszystkich zadań

W poprzednim przykładzie założyliśmy, że wszyscy pracownicy mogą wykonywać wszystkie zadania. Ale nie zawsze tak jest – pracownik może nie być w stanie wykonać jednego lub kilku zadań z różnych powodów. Można jednak łatwo zmodyfikować powyższy program pod kątem obsługi to osiągnąć.

Załóżmy na przykład, że instancja robocza 0 nie jest w stanie wykonać zadania 3. Aby zmienić uwzględnij to, wprowadź następujące zmiany:

1. Zmień wpis macierzy kosztów 0, 3 na ciąg 'NA'. (każdy ciąg znaków zadziała).

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

2. W sekcji kodu, który przypisuje koszty do rozwiązania, dodaj wiersz if cost[worker][task] != 'NA':, jak pokazano poniżej.

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

   Dodany wiersz zapobiega każdej krawędzi, której wpis w macierzy kosztów to 'NA' nie zostaną dodane do rozwiązania.

Po wprowadzeniu tych zmian i uruchomieniu zmodyfikowanego kodu zobaczysz następujące wyniki: dane wyjściowe:

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

Warto zauważyć, że łączny koszt jest teraz wyższy niż w przypadku pierwotnego problemu. Nie jest to nic dziwnego, ponieważ w pierwotnym problemie optymalne rozwiązanie przypisano instancję roboczą 0 do zadania 3, podczas gdy w zmodyfikowanym problemie przypisanie niedozwolone.

Aby sprawdzić, co się stanie, gdy więcej pracowników nie będzie w stanie wykonywać zadań, możesz zastąpić zmienną więcej wpisów macierzy kosztów z parametrem 'NA', aby wskazać dodatkowych instancji roboczych, nie może wykonywać niektórych zadań:

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

Po uruchomieniu programu tym razem uzyskasz negatywny wynik:

No assignment is possible.

Oznacza to, że nie ma możliwości przypisywania pracowników do zadań, wykonuje inne zadanie. Aby dowiedzieć się, dlaczego tak jest, spójrz na wykres dla zadania (gdy nie ma krawędzi odpowiadających wartościom 'NA' w tabeli kosztów).

Węzły trzech instancji roboczych 0, 1 i 2 są połączone tylko z dwoma węzłów dla zadań 0 i 1, nie można przypisać do nich różnych zadań pracowników.

Twierdzenie o małżeństwie

W teorii grafów występuje dobrze znany wynik, nazywany Twierdzenie o małżeństwie, który informuje nas dokładnie, kiedy można przypisać każdy węzeł po lewej stronie do osobnego po prawej stronie, na wykresie dwudzielnym, takim jak pokazany powyżej. Takie przypisanie jest nazywane dopasowaniem idealnym. W skrócie, twierdzenie stanowi, że jest to możliwe jeśli po lewej stronie nie ma podzbioru węzłów (jak w poprzednim przykładzie), ), których krawędzie prowadzą do mniejszego zestawu węzłów po prawej stronie.

Dokładniej mówiąc, twierdzenie stanowi, że graf dwustronny ma idealne dopasowanie jeśli i tylko wtedy, dla dowolnego podzbioru S węzłów po lewej stronie grafu, zestaw węzłów po prawej stronie grafu, które są połączone krawędzią węzeł w węźle S jest co najmniej tak duży, jak S.