Liniowe rozwiązanie do przypisywania sum linearnych

W tej sekcji opisujemy narzędzie do rozwiązywania problemów z sumami liniowymi, czyli specjalistyczne narzędzie do rozwiązywania prostych zadań związanych z przypisywaniem. Może ono być szybsze niż rozwiązanie MIP lub CP-SAT. Jednak rozwiązania MIP i CP-SAT obsługują znacznie większą liczbę problemów, więc w większości przypadków są najlepszym rozwiązaniem.

Tabela kosztów

Koszty pracowników i zadań znajdują się w tabeli poniżej.

Instancja robocza	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 kolejnych sekcjach przedstawiamy program w Pythonie, który rozwiązuje problem z projektem przy użyciu narzędzia do rozwiązywania problemów z sumami liniowymi.

Zaimportuj biblioteki

Poniżej znajduje się kod importujący 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;

Definiowanie danych

Poniższy kod tworzy dane 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 macierzy kosztów, której wpis i, j to koszt wykonania zadania j przez instancję roboczą i. Są 4 instancje robocze odpowiadające wierszom macierzy i 4 zadania odpowiadające kolumnom.

Tworzenie rozwiązania

Program używa rozwiązania do przypisywania liniowych, czyli specjalistycznego rozwiązania do rozwiązywania problemów z projektem.

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 przypisywaniem sum liniowych akceptuje tylko wartości całkowite dla wag i wartości. Z sekcji Korzystanie z rozwiązań opartych na danych niecałkowitych dowiesz się, jak używać rozwiązania, jeśli dane zawierają wartości inne niż całkowite.

Dodaj ograniczenia

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

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ływanie rozwiązania

Poniższy 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

Poniższy wykres przedstawia rozwiązanie jako przerywane krawędzie na wykresie. Liczby obok przerywanych krawędzi wskazują ich koszty. Całkowity czas oczekiwania w tym przypisaniu to suma kosztów poniesionych na przerywane krawędzie, która wynosi 265.

W teorii grafów zbiór krawędzi na wykresie dwustronnym, które pasują do każdego węzła po lewej stronie i dokładnie 1 węzła po prawej, jest nazywany dopasowaniem idealnym.

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ą wykonać wszystkich zadań

W poprzednim przykładzie założyliśmy, że wszyscy pracownicy mogą wykonywać wszystkie zadania. Jednak nie zawsze tak jest – pracownik może nie być w stanie wykonać jednego lub większej liczby zadań z różnych powodów. Można jednak łatwo zmodyfikować wspomniany program, aby rozwiązać ten problem.

Załóżmy na przykład, że instancja robocza 0 nie może wykonać zadania 3. Aby wprowadzić do programu te zmiany, wprowadź następujące zmiany:

1. Zmień pozycję 0, 3 w macierzy kosztów na ciąg 'NA'. (Może to być dowolny ciąg znaków).

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

2. W sekcji kodu, która 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])

   Dodana linia zapobiega dodaniu do rozwiązania krawędzi, których wpis w tablicy kosztów to 'NA'.

Po wprowadzeniu tych zmian i uruchomieniu zmodyfikowanego kodu zobaczysz takie wyniki:

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

Zwróć uwagę, że łączny koszt jest teraz wyższy niż w przypadku pierwotnego problemu. Nie jest to zaskakujące, ponieważ w pierwotnym problemie optymalne rozwiązanie przypisało instancję roboczą 0 do zadania 3, podczas gdy w zmodyfikowanym zadaniu przypisanie jest niedozwolone.

Aby sprawdzić, co się stanie, jeśli więcej instancji roboczych nie będzie w stanie wykonywać zadań, możesz zastąpić więcej wpisów w tabeli kosztów wartością 'NA', by wskazać dodatkowe instancje robocze, które nie mogą wykonywać określonych zadań:

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

Jeśli uruchomisz program tym razem, uzyskasz negatywny wynik:

No assignment is possible.

Oznacza to, że nie można przypisywać instancji roboczych do zadań, tak aby każda z nich wykonała inne zadanie. Aby się tego dowiedzieć, spójrz na wykres danego problemu (w którym nie ma krawędzi odpowiadających wartościom 'NA' w tablicy kosztów).

Węzły 3 instancji roboczych 0, 1 i 2 są połączone tylko z 2 węzłami zadań 0 i 1, dlatego nie można przypisać do tych instancji roboczych różnych zadań.

Twierdzenie małżeńskie

Osiągnęliśmy dobrze znany wynik w teorii grafów, zwany Twierdzeniem małżeńskim, który dokładnie informuje, kiedy można przypisać każdy węzeł po lewej stronie do innego węzła po prawej stronie na wykresie dwustronnym takim jak ten powyżej. Taki projekt nazywamy doskonałym dopasowaniem. Mówiąc w skrócie, twierdzenie mówi, ż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.

Mówiąc dokładniej, twierdzenie dwustronne mówi, że wykres dwustronny jest identyczny tylko wtedy, gdy w przypadku dowolnego podzbioru S węzłów po lewej stronie wykresu zestaw węzłów po prawej stronie wykresu, które są połączone krawędzią z węzłem w S, jest co najmniej taki jak S.