Pemecah Soal Penjumlahan Linear

Bagian ini menjelaskan pemecah masalah penetapan jumlah linear, yakni untuk menyelesaikan masalah tugas sederhana, yang bisa lebih cepat daripada Pemecah masalah MIP atau CP-SAT. Namun, pemecah masalah MIP dan CP-SAT dapat menangani banyak rangkaian masalah yang lebih luas, jadi dalam kebanyakan kasus itu adalah pilihan terbaik.

Matriks biaya

Biaya untuk pekerja dan tugas diberikan dalam tabel di bawah ini.

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

Bagian berikut ini menyajikan program Python yang menyelesaikan tugas menggunakan pemecah soal {i>SUM<i} penjumlahan linier.

Mengimpor library

Kode yang mengimpor library yang diperlukan ditunjukkan di bawah ini.

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;

Menentukan data

Kode berikut membuat data untuk program.

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

Array adalah matriks biaya, yang entri i, j-nya adalah biaya untuk pekerja i untuk menjalankan tugas j. Ada empat pekerja, sesuai dengan baris matriks, dan empat tugas, sesuai dengan kolom.

Membuat pemecah

Program ini menggunakan pemecah masalah penetapan linear, pemecah masalah khusus untuk soal penugasan.

Kode berikut membuat pemecah.

Python

assignment = linear_sum_assignment.SimpleLinearSumAssignment()

C++

SimpleLinearSumAssignment assignment;

Java

LinearSumAssignment assignment = new LinearSumAssignment();

C#

LinearSumAssignment assignment = new LinearSumAssignment();

Catatan: Pemecah soal penetapan jumlah linear hanya menerima nilai bilangan bulat untuk bobot dan nilai. Bagian ini Menggunakan pemecah masalah dengan data non-bilangan bulat menunjukkan cara menggunakan pemecah masalah jika data Anda berisi nilai non-bilangan bulat.

Menambahkan batasan

Kode berikut menambahkan biaya ke pemecah masalah dengan melakukan loop pekerja dan tugas klasifikasi.

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

Memanggil pemecah masalah

Kode berikut memanggil pemecah.

Python

status = assignment.solve()

C++

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

Java

LinearSumAssignment.Status status = assignment.solve();

C#

LinearSumAssignment.Status status = assignment.Solve();

Menampilkan hasil

Kode berikut menampilkan solusinya.

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

Output di bawah menunjukkan penetapan pekerja yang optimal untuk setiap tugas.

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

Grafik berikut menunjukkan solusinya sebagai tepi putus-putus dalam grafik. Tujuan angka di sebelah tepi putus-putus adalah biayanya. Total waktu tunggu untuk penugasan ini adalah jumlah biaya tepi putus-putus, yaitu 265.

Dalam teori graf, serangkaian tepi dalam grafik bipartit yang sesuai dengan setiap {i>node<i} pada sebelah kiri dengan satu simpul di sebelah kanan disebut pencocokan sempurna.

Seluruh program

Berikut ini adalah keseluruhan 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}.");
        }
    }
}

Solusi saat pekerja tidak dapat melakukan semua tugas

Pada contoh sebelumnya, kita mengasumsikan bahwa semua pekerja dapat melakukan semua tugas. Tapi tidak selalu demikian - pekerja mungkin tidak dapat melakukan satu atau beberapa tugas karena berbagai alasan. Namun, mudah untuk memodifikasi program di atas untuk ditangani ini.

Sebagai contoh, anggap saja pekerja 0 tidak dapat melakukan tugas 3. Untuk mengubah program untuk mempertimbangkan hal ini, buat perubahan berikut:

1. Ubah entri 0, 3 dari matriks biaya ke string 'NA'. (String apa pun bisa.)

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

2. Pada bagian kode yang menetapkan biaya ke pemecah masalah, tambahkan baris if cost[worker][task] != 'NA':, seperti yang ditunjukkan di bawah ini.

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

   Garis yang ditambahkan mencegah tepi yang entrinya dalam matriks biaya adalah 'NA' agar tidak ditambahkan ke pemecah soal.

Setelah melakukan perubahan ini dan menjalankan kode yang telah diubah, Anda akan melihat yang berikut {i>output<i}:

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

Perhatikan bahwa total biaya sekarang lebih tinggi daripada untuk masalah awal. Hal ini tidak mengherankan, karena dalam masalah awal, solusi yang optimal menugaskan pekerja 0 ke tugas 3, sementara dalam masalah yang dimodifikasi, tidak diizinkan.

Untuk melihat apa yang terjadi jika lebih banyak pekerja yang tidak dapat melakukan tugas, Anda dapat mengganti lebih banyak entri matriks biaya dengan 'NA', untuk menunjukkan pekerja tambahan yang tidak dapat melakukan tugas tertentu:

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

Ketika Anda menjalankan program kali ini, Anda mendapatkan hasil negatif:

No assignment is possible.

Ini berarti tidak ada cara untuk menetapkan pekerja ke tugas-tugas sehingga setiap pekerja melakukan tugas yang berbeda. Anda dapat mengetahui penyebabnya dengan melihat grafik untuk soal (di mana tidak ada tepi yang sesuai dengan nilai 'NA' dalam matriks biaya).

Karena simpul untuk tiga pekerja 0, 1, dan 2 hanya terhubung ke dua {i>node <i}untuk tugas 0 dan 1, tidak mungkin menetapkan tugas yang berbeda untuk pekerja.

Teorema Pernikahan

Ada sebuah hasil yang terkenal dalam teori graf, yang disebut Teorema Pernikahan, yang memberi tahu kita kapan tepatnya Anda bisa menetapkan setiap {i>node<i} di sebelah kiri ke node simpul di sebelah kanan, dalam grafik bipartit seperti di atas. Tugas seperti ini disebut pencocokan sempurna. Singkatnya, teorema itu mengatakan ini mungkin jika tidak ada subset node di sebelah kiri (seperti dalam contoh sebelumnya ) yang tepinya mengarah ke kumpulan node yang lebih kecil di sebelah kanan.

Lebih tepatnya, teorema tersebut mengatakan bahwa grafik bipartit memiliki kecocokan jika dan hanya jika untuk subset S dari node di sisi kiri grafik, kumpulan simpul di sisi kanan grafik yang dihubungkan dengan ujung ke ujung node di S setidaknya sebesar S.