लीनियर सम असाइनमेंट सॉल्वर

इस सेक्शन में लीनियर सम असाइनमेंट सॉल्वर के बारे में बताया गया है. यह असाइनमेंट के आसान सवालों को हल करने वाला एक विशेषज्ञ है. यह 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

नीचे दिए गए सेक्शन में एक Python प्रोग्राम दिया गया है. इसमें लीनियर सम असाइनमेंट सॉल्वर का इस्तेमाल करके, असाइनमेंट का सवाल हल किया जाता है.

लाइब्रेरी इंपोर्ट करना

ज़रूरी लाइब्रेरी को इंपोर्ट करने वाला कोड नीचे दिखाया गया है.

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;

डेटा तय करना

यह कोड, प्रोग्राम के लिए डेटा बनाता है.

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

अरे, लागत मैट्रिक्स होती है, जिसकी i, j एंट्री, वर्कर i टास्क j को पूरा करने की लागत होती है. यहां मैट्रिक्स की पंक्तियों के हिसाब से चार वर्कर हैं और कॉलम से जुड़े चार टास्क हैं.

सॉल्वर बनाएं

इस प्रोग्राम में लीनियर असाइनमेंट सॉल्वर का इस्तेमाल किया जाता है. यह असाइनमेंट के सवालों के लिए एक खास सॉल्वर है.

इन कोड से सॉल्वर बनता है.

Python

assignment = linear_sum_assignment.SimpleLinearSumAssignment()

C++

SimpleLinearSumAssignment assignment;

Java

LinearSumAssignment assignment = new LinearSumAssignment();

C#

LinearSumAssignment assignment = new LinearSumAssignment();

ध्यान दें: लीनियर सम असाइनमेंट सॉल्वर, सिर्फ़ वेट और वैल्यू के लिए पूर्णांक वाली वैल्यू स्वीकार करता है. बिना पूर्णांक वाले डेटा के साथ सॉल्वर का इस्तेमाल करना सेक्शन से पता चलता है कि अगर आपके डेटा में ऐसी वैल्यू हैं जो पूर्णांक नहीं हैं, तो सॉल्वर को कैसे इस्तेमाल किया जा सकता है.

पाबंदियां जोड़ें

नीचे दिया गया कोड, कर्मचारियों और टास्क पर लूप करके, सॉल्वर में लागत बढ़ाता है.

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

सॉल्वर को शुरू करें

यह कोड, सॉल्वर को शुरू करता है.

Python

status = assignment.solve()

C++

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

Java

LinearSumAssignment.Status status = assignment.solve();

C#

LinearSumAssignment.Status status = assignment.Solve();

नतीजे दिखाएं

यह कोड दिखाता है कि सलूशन क्या है.

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

नीचे दिया गया आउटपुट, टास्क के लिए कर्मचारियों का सबसे सही असाइनमेंट दिखाता है.

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 इंतज़ार का समय है.

ग्राफ़ थ्योरी के हिसाब से, एक दोपार्टिकुलेट ग्राफ़ में किनारों के ऐसे सेट को परफ़ेक्ट मैचिंग कहा जाता है जो बाईं ओर के हर नोड से मैच करता है.

पूरा कार्यक्रम

यहां पूरा कार्यक्रम दिया गया है.

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

कर्मचारी जब सभी टास्क पूरे नहीं कर सकते हैं, तो समाधान

पिछले उदाहरण में, हमने माना कि सभी वर्कर, सभी काम कर सकते हैं. लेकिन हमेशा ऐसा नहीं होता - हो सकता है कि कोई वर्कर कई वजहों से एक या उससे ज़्यादा टास्क पूरा न कर पाए. हालांकि, इसे मैनेज करने के लिए, ऊपर दिए गए प्रोग्राम में आसानी से बदलाव किया जा सकता है.

उदाहरण के तौर पर, मान लें कि वर्कर 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 होगा, तो