Trình giải tổng hợp tuyến tính

Phần này mô tả về trình giải phép gán tổng tuyến tính, một trình giải toán chuyên dụng cho bài toán chỉ định đơn giản, có thể nhanh hơn trình giải MIP hoặc CP-SAT. Tuy nhiên, các trình phân giải MIP và CP-SAT có thể xử lý nhiều vấn đề hơn. Vì vậy, trong hầu hết trường hợp, chúng là lựa chọn tốt nhất.

Ma trận chi phí

Chi phí cho trình chạy và tác vụ được cho trong bảng dưới đây.

Worker	Nhiệm vụ 0	Nhiệm vụ 1	Nhiệm vụ 2	Nhiệm vụ 3
0	90	76	75	70
1	35	85	55	65
2	125	95	90	105
3	45	110	95	115

Các phần sau đây trình bày một chương trình Python giải quyết một bài tập về bài tập bằng cách sử dụng trình giải bài tập tổng tuyến tính.

Nhập thư viện

Mã nhập thư viện bắt buộc được hiển thị bên dưới.

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;

Xác định dữ liệu

Đoạn mã sau đây tạo dữ liệu cho chương trình.

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

Mảng này là ma trận chi phí, trong đó mục i, j là chi phí để trình thực thi i thực hiện tác vụ j. Có 4 worker tương ứng với các hàng của ma trận và 4 nhiệm vụ tương ứng với các cột.

Tạo trình giải

Chương trình này sử dụng trình giải toán phép gán tuyến tính, một trình giải toán chuyên dụng cho bài tập về bài tập.

Mã sau đây sẽ tạo trình giải.

Python

assignment = linear_sum_assignment.SimpleLinearSumAssignment()

C++

SimpleLinearSumAssignment assignment;

Java

LinearSumAssignment assignment = new LinearSumAssignment();

C#

LinearSumAssignment assignment = new LinearSumAssignment();

Lưu ý: Trình phân giải tổng tuyến tính chỉ chấp nhận giá trị số nguyên cho các trọng số và giá trị. Phần Sử dụng trình phân giải với dữ liệu không phải là số nguyên cho biết cách sử dụng trình phân giải nếu dữ liệu của bạn chứa các giá trị không phải là số nguyên.

Thêm các điều kiện ràng buộc

Mã sau đây thêm chi phí cho trình phân giải bằng cách lặp lại trình thực thi và tác vụ.

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

Gọi trình giải

Mã sau đây gọi trình giải.

Python

status = assignment.solve()

C++

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

Java

LinearSumAssignment.Status status = assignment.solve();

C#

LinearSumAssignment.Status status = assignment.Solve();

Hiện kết quả

Mã sau đây sẽ hiển thị giải pháp.

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

Kết quả dưới đây cho thấy cách chỉ định worker cho các nhiệm vụ một cách tối ưu.

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

Biểu đồ sau đây minh hoạ giải pháp dưới dạng các cạnh nét đứt trong biểu đồ. Các con số bên cạnh các cạnh nét đứt biểu thị chi phí của các giá trị này. Tổng thời gian chờ của chỉ định này là tổng chi phí cho các cạnh nét đứt là 265.

Trong lý thuyết biểu đồ, một tập hợp các cạnh trong biểu đồ hai bên khớp với mọi nút ở bên trái với đúng một nút ở bên phải được gọi là khớp hoàn hảo.

Toàn bộ chương trình

Sau đây là toàn bộ chương trình.

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

Giải pháp khi trình thực thi không thể thực hiện hết các tác vụ

Trong ví dụ trước, chúng ta giả định rằng tất cả worker đều có thể thực hiện tất cả các nhiệm vụ. Tuy nhiên, không phải lúc nào cũng như vậy – một trình thực thi có thể không thực hiện được một hoặc nhiều tác vụ vì nhiều lý do. Tuy nhiên, bạn có thể dễ dàng sửa đổi chương trình ở trên để xử lý việc này.

Ví dụ: giả sử worker 0 không thể thực hiện tác vụ 3. Để sửa đổi chương trình nhằm tính đến điều này, hãy thực hiện các thay đổi sau:

1. Thay đổi mục nhập 0, 3 của ma trận chi phí thành chuỗi 'NA'. (Mọi chuỗi đều được.)

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

2. Trong mục mã chỉ định chi phí cho trình giải, hãy thêm dòng if cost[worker][task] != 'NA':, như minh hoạ dưới đây.

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

   Dòng đã thêm này ngăn không cho bất kỳ cạnh nào có mục nhập trong ma trận chi phí là 'NA' được thêm vào trình phân giải.

Sau khi thực hiện những thay đổi này và chạy mã đã sửa đổi, bạn sẽ thấy kết quả sau:

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

Xin lưu ý rằng tổng chi phí hiện đã cao hơn so với vấn đề ban đầu. Điều này không có gì đáng ngạc nhiên vì trong vấn đề ban đầu, giải pháp tối ưu đã chỉ định trình thực thi 0 cho tác vụ 3, còn trong vấn đề đã sửa đổi thì bài tập đó không được phép.

Để xem điều gì sẽ xảy ra nếu thêm nhiều trình thực thi không thể thực hiện tác vụ, bạn có thể thay thế nhiều mục nhập của ma trận chi phí bằng 'NA' để biểu thị thêm trình thực thi không thể thực hiện một số tác vụ nhất định:

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

Khi chạy chương trình lần này, bạn nhận được một kết quả âm:

No assignment is possible.

Điều này có nghĩa là không có cách nào để chỉ định trình thực thi cho các tác vụ để mỗi trình thực thi thực hiện một tác vụ riêng. Bạn có thể hiểu lý do của vấn đề này bằng cách xem biểu đồ về vấn đề (trong đó không có cạnh nào tương ứng với giá trị của 'NA' trong ma trận chi phí).

Vì các nút cho 3 worker 0, 1 và 2 chỉ được kết nối với 2 nút cho nhiệm vụ 0 và 1, nên bạn không thể chỉ định các nhiệm vụ riêng biệt cho những worker này.

Định lý hôn nhân

Có một kết quả phổ biến trong lý thuyết đồ thị, gọi là Định lý hôn nhân, cho biết chính xác thời điểm bạn có thể gán từng nút bên trái cho một nút riêng biệt ở bên phải, trong biểu đồ hai bên như minh hoạ ở trên. Việc chỉ định như vậy được gọi là một kết hợp hoàn hảo. Tóm lại, định lý cho biết điều này có thể xảy ra nếu không có tập hợp con nút nào ở bên trái (như tập hợp con trong ví dụ trước) có các cạnh dẫn đến một tập hợp nút nhỏ hơn ở bên phải.

Chính xác hơn, định lý nói rằng một biểu đồ hai bên có độ trùng khớp hoàn hảo nếu và chỉ khi đối với bất kỳ tập hợp con S nào của các nút ở bên trái của biểu đồ, tập hợp các nút ở bên phải của biểu đồ được kết nối bởi một cạnh với một nút trong S ít nhất bằng S.