লিনিয়ার সাম অ্যাসাইনমেন্ট সলভার

এই বিভাগে লিনিয়ার যোগ অ্যাসাইনমেন্ট সলভার বর্ণনা করা হয়েছে, সাধারণ অ্যাসাইনমেন্ট সমস্যার জন্য একটি বিশেষ সমাধানকারী, যা MIP বা CP-SAT সমাধানকারীর চেয়ে দ্রুত হতে পারে। যাইহোক, MIP এবং CP-SAT সমাধানকারীরা অনেক বিস্তৃত সমস্যা মোকাবেলা করতে পারে, তাই বেশিরভাগ ক্ষেত্রে তারাই সেরা বিকল্প।

খরচ ম্যাট্রিক্স

কর্মীদের এবং কাজের জন্য খরচ নীচের টেবিলে দেওয়া আছে.

কর্মী	টাস্ক 0	টাস্ক 1	টাস্ক 2	টাস্ক 3
0	90	76	75	70
1	35	85	55	65
2	125	95	90	105
3	45	110	95	115

নিম্নলিখিত বিভাগগুলি একটি পাইথন প্রোগ্রাম উপস্থাপন করে যা লিনিয়ার যোগ অ্যাসাইনমেন্ট সলভার ব্যবহার করে একটি অ্যাসাইনমেন্ট সমস্যার সমাধান করে।

লাইব্রেরি আমদানি করুন

প্রয়োজনীয় লাইব্রেরি আমদানি করে এমন কোডটি নীচে দেখানো হয়েছে।

পাইথন

import numpy as np

from ortools.graph.python import linear_sum_assignment

সি++

#include "ortools/graph/assignment.h"

#include <cstdint>
#include <numeric>
#include <string>
#include <vector>

জাভা

import com.google.ortools.Loader;
import com.google.ortools.graph.LinearSumAssignment;
import java.util.stream.IntStream;

সি#

using System;
using System.Collections.Generic;
using System.Linq;
using Google.OrTools.Graph;

ডেটা সংজ্ঞায়িত করুন

নিম্নলিখিত কোড প্রোগ্রামের জন্য ডেটা তৈরি করে।

পাইথন

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

সি++

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

জাভা

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

সি#

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

অ্যারে হল খরচ ম্যাট্রিক্স , যার i , j এন্ট্রি হল ওয়ার্কার i এর টাস্ক j করার জন্য খরচ। ম্যাট্রিক্সের সারিগুলির সাথে সম্পর্কিত চারটি কর্মী এবং কলামগুলির সাথে সম্পর্কিত চারটি কাজ রয়েছে৷

সমাধানকারী তৈরি করুন

প্রোগ্রামটি লিনিয়ার অ্যাসাইনমেন্ট সলভার ব্যবহার করে, অ্যাসাইনমেন্ট সমস্যার জন্য একটি বিশেষ সমাধানকারী।

নিম্নলিখিত কোড সমাধানকারী তৈরি করে।

পাইথন

assignment = linear_sum_assignment.SimpleLinearSumAssignment()

সি++

SimpleLinearSumAssignment assignment;

জাভা

LinearSumAssignment assignment = new LinearSumAssignment();

সি#

LinearSumAssignment assignment = new LinearSumAssignment();

দ্রষ্টব্য: লিনিয়ার যোগ অ্যাসাইনমেন্ট সমাধানকারী শুধুমাত্র ওজন এবং মানের জন্য পূর্ণসংখ্যা মান গ্রহণ করে। অ-পূর্ণসংখ্যা ডেটা সহ একটি সমাধানকারী ব্যবহার করা বিভাগটি দেখায় যে কীভাবে আপনার ডেটাতে অ-পূর্ণসংখ্যার মান থাকে তবে কীভাবে সমাধান করতে হয়।

সীমাবদ্ধতা যোগ করুন

নিম্নোক্ত কোডটি কর্মী এবং কাজগুলির উপর লুপ করে সমাধানকারীর খরচ যোগ করে।

পাইথন

assignment.add_arcs_with_cost(start_nodes, end_nodes, arc_costs)

সি++

for (int w : all_workers) {
  for (int t : all_tasks) {
    if (costs[w][t]) {
      assignment.AddArcWithCost(w, t, costs[w][t]);
    }
  }
}

জাভা

// Add each arc.
for (int w : allWorkers) {
  for (int t : allTasks) {
    if (costs[w][t] != 0) {
      assignment.addArcWithCost(w, t, costs[w][t]);
    }
  }
}

সি#

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

সমাধানকারীকে আহ্বান করুন

নিম্নলিখিত কোডটি সমাধানকারীকে আহ্বান করে।

পাইথন

status = assignment.solve()

সি++

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

জাভা

LinearSumAssignment.Status status = assignment.solve();

সি#

LinearSumAssignment.Status 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 (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.";
}

জাভা

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

সি#

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

নীচের আউটপুটটি কাজের জন্য কর্মীদের সর্বোত্তম নিয়োগ দেখায়।

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

নিচের গ্রাফটি গ্রাফে ড্যাশ করা প্রান্ত হিসাবে সমাধানটি দেখায়। ড্যাশ করা প্রান্তের পাশের সংখ্যাগুলি তাদের খরচ। এই অ্যাসাইনমেন্টের মোট অপেক্ষার সময় হল ড্যাশ করা প্রান্তগুলির জন্য খরচের সমষ্টি, যা হল 265৷

গ্রাফ তত্ত্বে, একটি দ্বিপক্ষীয় গ্রাফে প্রান্তের একটি সেট যা বাম দিকের প্রতিটি নোডের সাথে ডানদিকে একটি নোডের সাথে মিলে যায় তাকে নিখুঁত ম্যাচিং বলা হয়।

পুরো প্রোগ্রাম

এখানে সম্পূর্ণ প্রোগ্রাম.

পাইথন

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

সি++

#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;
}

জাভা

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() {}
}

সি#

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

সমাধান যখন কর্মীরা সমস্ত কাজ সম্পাদন করতে পারে না

পূর্ববর্তী উদাহরণে, আমরা ধরে নিয়েছিলাম যে সমস্ত কর্মীরা সমস্ত কাজ সম্পাদন করতে পারে। তবে এটি সবসময় হয় না - একজন কর্মী বিভিন্ন কারণে এক বা একাধিক কাজ সম্পাদন করতে অক্ষম হতে পারে। যাইহোক, এটি পরিচালনা করার জন্য উপরের প্রোগ্রামটি পরিবর্তন করা সহজ।

একটি উদাহরণ হিসাবে, ধরুন যে কর্মী 0 টাস্ক 3 সম্পাদন করতে অক্ষম। এটি বিবেচনায় নেওয়ার জন্য প্রোগ্রামটি পরিবর্তন করতে, নিম্নলিখিত পরিবর্তনগুলি করুন:

1. কস্ট ম্যাট্রিক্সের 0, 3 এন্ট্রিকে 'NA' স্ট্রিংয়ে পরিবর্তন করুন। (যে কোনো স্ট্রিং কাজ করবে।)

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

2. কোডের বিভাগে যেটি সমাধানকারীকে খরচ নির্ধারণ করে, লাইনটি যোগ করুন if cost[worker][task] != 'NA': , নীচে দেখানো হয়েছে।

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

   যোগ করা রেখাটি যেকোন প্রান্তকে বাধা দেয় যার খরচ ম্যাট্রিক্সে এন্ট্রি 'NA' হয় সলভারে যোগ করা থেকে।

এই পরিবর্তনগুলি করার পরে এবং পরিবর্তিত কোড চালানোর পরে, আপনি নিম্নলিখিত আউটপুট দেখতে পাবেন:

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

লক্ষ্য করুন যে মূল সমস্যাটির তুলনায় মোট খরচ এখন বেশি। এটি আশ্চর্যজনক নয়, কারণ মূল সমস্যাটিতে সর্বোত্তম সমাধানটি কর্মী 0 কে টাস্ক 3 এ বরাদ্দ করে, যখন পরিবর্তিত সমস্যাটিতে যে অ্যাসাইনমেন্ট অনুমোদিত নয়।

আরও কর্মী কাজ সম্পাদন করতে অক্ষম হলে কী হবে তা দেখতে, আপনি 'NA' দিয়ে খরচ ম্যাট্রিক্সের আরও এন্ট্রি প্রতিস্থাপন করতে পারেন, অতিরিক্ত কর্মীদের বোঝাতে যারা নির্দিষ্ট কাজ সম্পাদন করতে পারে না:

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

আপনি যখন এই সময় প্রোগ্রামটি চালান, আপনি একটি নেতিবাচক ফলাফল পাবেন:

No assignment is possible.

এর মানে কর্মীদের কাজের জন্য অর্পণ করার কোন উপায় নেই যাতে প্রতিটি কর্মী একটি ভিন্ন কাজ সম্পাদন করে। আপনি সমস্যার জন্য গ্রাফ দেখে দেখতে পারেন কেন এটি এমন হয় (যেটিতে খরচ ম্যাট্রিক্সে 'NA' এর মানগুলির সাথে কোন প্রান্ত নেই)।

যেহেতু 0, 1, এবং 2 তিনটি কর্মীদের জন্য নোডগুলি শুধুমাত্র 0 এবং 1 কাজের জন্য দুটি নোডের সাথে সংযুক্ত, তাই এই কর্মীদের আলাদা কাজ বরাদ্দ করা সম্ভব নয়।

বিবাহ উপপাদ্য

গ্রাফ থিওরিতে একটি সুপরিচিত ফলাফল রয়েছে, যাকে দ্য ম্যারেজ থিওরেম বলা হয়, যা আমাদেরকে ঠিক কখন বাম দিকের প্রতিটি নোডকে ডানদিকের একটি স্বতন্ত্র নোডে বরাদ্দ করতে পারে, উপরের মত একটি দ্বিপক্ষীয় গ্রাফে। এই ধরনের একটি নিয়োগ একটি নিখুঁত ম্যাচিং বলা হয়. সংক্ষেপে, উপপাদ্যটি বলে যে এটি সম্ভব যদি বাম দিকে নোডের কোনো উপসেট না থাকে (আগের উদাহরণের মতো) যার প্রান্ত ডানদিকে নোডের একটি ছোট সেটের দিকে নিয়ে যায়।

আরও স্পষ্টভাবে, উপপাদ্যটি বলে যে একটি দ্বিপক্ষীয় গ্রাফের একটি নিখুঁত মিল রয়েছে যদি এবং শুধুমাত্র যদি গ্রাফের বাম দিকে নোডগুলির যে কোনও উপসেট S এর জন্য, গ্রাফের ডানদিকে নোডগুলির সেট যা একটি প্রান্ত দ্বারা সংযুক্ত থাকে। S-এর একটি নোডের অন্তত S এর মতো বড়।