Doğrusal Toplam Atama Çözücü

Bu bölümde, basit ödev problemleri için özel bir çözücü olan ve MIP ya da CP-SAT çözücüden daha hızlı olabilen doğrusal toplam atama çözücü açıklanmaktadır. Bununla birlikte, MIP ve CP-SAT çözücüler çok daha fazla sayıda problemin üstesinden gelebilir. Bu nedenle çoğu durumda en iyi seçenektir.

Maliyet matrisi

Çalışanların ve görevlerin maliyetleri aşağıdaki tabloda verilmiştir.

Çalışan	Görev 0	Görev 1	Görev 2	Görev 3
0	90	76	75	70
1	35	85	55	65
2	125	95	90	105
3	45	110	95	115

Aşağıdaki bölümlerde, doğrusal toplam ödev çözücüyü kullanarak bir ödev problemini çözen bir Python programı sunulmaktadır.

Kitaplıkları içe aktarın

Gerekli kitaplığı içe aktaran kod aşağıda gösterilmektedir.

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;

Verileri tanımlama

Aşağıdaki kod, program verilerini oluşturur.

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

Dizi, maliyet matrisidir. Bu matrisin i ve j girişi, i çalışanının j görevini gerçekleştirmesinin maliyetidir. Matris satırlarına karşılık gelen dört çalışan ve sütunlara karşılık gelen dört görev vardır.

Çözme aracı oluşturma

Program, ödev problemi için özel bir çözücü olan doğrusal atama çözücüyü kullanır.

Aşağıdaki kod çözücüyü oluşturur.

Python

assignment = linear_sum_assignment.SimpleLinearSumAssignment()

C++

SimpleLinearSumAssignment assignment;

Java

LinearSumAssignment assignment = new LinearSumAssignment();

C#

LinearSumAssignment assignment = new LinearSumAssignment();

Not: Doğrusal toplam atama çözücü, ağırlıklar ve değerler için yalnızca tam sayı değerlerini kabul eder. Tam sayı olmayan verilerle çözücü kullanma bölümünde, verileriniz tam sayı olmayan değerler içeriyorsa çözücünün nasıl kullanılacağı gösterilmektedir.

Kısıtlamaları ekleme

Aşağıdaki kod, çalışanlar ve görevler döngüye alınarak çözücüye maliyetleri ekler.

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

Çözücüyü çağır

Aşağıdaki kod çözücüyü çağırır.

Python

status = assignment.solve()

C++

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

Java

LinearSumAssignment.Status status = assignment.solve();

C#

LinearSumAssignment.Status status = assignment.Solve();

Sonuçları görüntüleyin

Aşağıdaki kod çözümü gösterir.

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şağıdaki çıkış, çalışanların görevlere en uygun şekilde atanmasını gösterir.

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

Aşağıdaki grafikte çözüm, grafikteki kesikli kenarlar olarak gösterilmektedir. Kesikli kenarların yanındaki sayılar, maliyetleridir. Bu atamanın toplam bekleme süresi, kesik çizgili kenarların maliyetinin toplamıyla 265'tir.

Grafik teorisinde, iki parçalı bir grafikte her düğümle sağdaki tam olarak bir düğümle eşleşen kenar kümesine mükemmel eşleşme adı verilir.

Programın tamamı

Programın tamamını burada bulabilirsiniz.

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

Çalışanlar tüm görevleri gerçekleştiremediğinde ortaya çıkacak çözüm

Önceki örnekte, tüm çalışanların tüm görevleri yerine getirebileceğini varsayıyorduk. Ancak bu her zaman böyle değildir. Bir çalışan çeşitli nedenlerle bir veya daha fazla görevi gerçekleştiremeyebilir. Ancak, yukarıdaki programı bunu halledecek şekilde değiştirmek kolaydır.

Örneğin, 0 numaralı çalışanın 3. görevi gerçekleştiremediğini varsayalım. Programı bu durumu dikkate alarak değiştirmek için aşağıdaki değişiklikleri yapın:

1. Maliyet matrisinin 0, 3 girişini 'NA' dizesiyle değiştirin. (Tüm dizeler kullanılabilir.)

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

2. Kodun çözücüye maliyet atayan bölümünde if cost[worker][task] != 'NA': satırını aşağıda gösterildiği gibi ekleyin.

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

   Eklenen çizgi, maliyet matrisinde girişi 'NA' olan herhangi bir kenarın çözücüye eklenmesini engeller.

Bu değişiklikleri yaptıktan ve değiştirilen kodu çalıştırdıktan sonra aşağıdaki çıkışı görürsünüz:

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

Toplam maliyetin, orijinal sorun için olduğundan daha yüksek olduğuna dikkat edin. Bu şaşırtıcı değildir, çünkü orijinal problemde optimum çözüm, görev 0'a 0 çalışana atanırken, değiştirilmiş problemde bu atamaya izin verilmez.

Daha fazla çalışanın görevleri gerçekleştirememesi durumunda ne olacağını görmek için, maliyet matrisinde daha fazla girişi 'NA' ile değiştirebilirsiniz. Böylece, belirli görevleri gerçekleştiremeyen ek çalışanları ifade edebilirsiniz:

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

Programı bu kez çalıştırdığınızda negatif bir sonuç alırsınız:

No assignment is possible.

Bu, her çalışanın farklı bir görevi yerine getirmesi için çalışanlara görevler atamanın bir yolu olmadığı anlamına gelir. Sorunun (maliyet matrisinde 'NA' değerlerine karşılık gelen kenarlar olmadığı) grafiğe bakarak bunun nedenini görebilirsiniz.

0, 1 ve 2 numaralı üç çalışanın düğümleri yalnızca 0 ve 1 numaralı görevler için iki düğüme bağlı olduğundan bu çalışanlara farklı görevler atamak mümkün değildir.

Evlilik Teoremi

Grafik teorisinde Evlilik Teoremi adı verilen iyi bilinen bir sonuç vardır. Bu sonuç, yukarıdaki gibi iki parçalı bir grafikte soldaki her bir düğümü ne zaman sağdaki farklı bir düğüme atayabileceğinizi tam olarak gösterir. Böyle bir atamaya mükemmel eşleşme denir. Kısacası, teoreme göre solda, kenarları sağdaki daha küçük bir düğüm kümesine neden olan düğüm alt kümesi (önceki örnekte olduğu gibi) yoksa bunun mümkün olduğu belirtilmektedir.

Daha kesin olarak belirtmek gerekirse teorem, iki parçalı bir grafiğin yalnızca grafiğin sol tarafındaki düğümlerin herhangi bir S alt kümesi için bir kenarla S'deki bir düğüme bağlanan düğüm grubunun en az S kadar büyük olması durumunda mükemmel bir eşleşmeye sahip olduğunu söyler.