cost matrix assignment problem

Index Assignment problem Hungarian algorithm Solve online

Solve an assignment problem online

Fill in the cost matrix of an assignment problem and click on 'Solve'. The optimal assignment will be determined and a step by step explanation of the hungarian algorithm will be given.

Fill in the cost matrix ( random cost matrix ):

Don't show the steps of the Hungarian algorithm Maximize the total cost

Hungarian Method

The Hungarian method is a computational optimization technique that addresses the assignment problem in polynomial time and foreshadows following primal-dual alternatives. In 1955, Harold Kuhn used the term “Hungarian method” to honour two Hungarian mathematicians, Dénes Kőnig and Jenő Egerváry. Let’s go through the steps of the Hungarian method with the help of a solved example.

Hungarian Method to Solve Assignment Problems

The Hungarian method is a simple way to solve assignment problems. Let us first discuss the assignment problems before moving on to learning the Hungarian method.

What is an Assignment Problem?

A transportation problem is a type of assignment problem. The goal is to allocate an equal amount of resources to the same number of activities. As a result, the overall cost of allocation is minimised or the total profit is maximised.

Because available resources such as workers, machines, and other resources have varying degrees of efficiency for executing different activities, and hence the cost, profit, or loss of conducting such activities varies.

Assume we have ‘n’ jobs to do on ‘m’ machines (i.e., one job to one machine). Our goal is to assign jobs to machines for the least amount of money possible (or maximum profit). Based on the notion that each machine can accomplish each task, but at variable levels of efficiency.

Hungarian Method Steps

Check to see if the number of rows and columns are equal; if they are, the assignment problem is considered to be balanced. Then go to step 1. If it is not balanced, it should be balanced before the algorithm is applied.

Step 1 – In the given cost matrix, subtract the least cost element of each row from all the entries in that row. Make sure that each row has at least one zero.

Step 2 – In the resultant cost matrix produced in step 1, subtract the least cost element in each column from all the components in that column, ensuring that each column contains at least one zero.

Step 3 – Assign zeros

Analyse the rows one by one until you find a row with precisely one unmarked zero. Encircle this lonely unmarked zero and assign it a task. All other zeros in the column of this circular zero should be crossed out because they will not be used in any future assignments. Continue in this manner until you’ve gone through all of the rows.
Examine the columns one by one until you find one with precisely one unmarked zero. Encircle this single unmarked zero and cross any other zero in its row to make an assignment to it. Continue until you’ve gone through all of the columns.

Step 4 – Perform the Optimal Test

The present assignment is optimal if each row and column has exactly one encircled zero.
The present assignment is not optimal if at least one row or column is missing an assignment (i.e., if at least one row or column is missing one encircled zero). Continue to step 5. Subtract the least cost element from all the entries in each column of the final cost matrix created in step 1 and ensure that each column has at least one zero.

Step 5 – Draw the least number of straight lines to cover all of the zeros as follows:

(a) Highlight the rows that aren’t assigned.

(b) Label the columns with zeros in marked rows (if they haven’t already been marked).

(d) Continue with (b) and (c) until no further marking is needed.

(f) Simply draw the lines through all rows and columns that are not marked. If the number of these lines equals the order of the matrix, then the solution is optimal; otherwise, it is not.

Step 6 – Find the lowest cost factor that is not covered by the straight lines. Subtract this least-cost component from all the uncovered elements and add it to all the elements that are at the intersection of these straight lines, but leave the rest of the elements alone.

Step 7 – Continue with steps 1 – 6 until you’ve found the highest suitable assignment.

Hungarian Method Example

Use the Hungarian method to solve the given assignment problem stated in the table. The entries in the matrix represent each man’s processing time in hours.

$\begin{array}{l}\begin{bmatrix} & I & II & III & IV & V \\1 & 20 & 15 & 18 & 20 & 25 \\2 & 18 & 20 & 12 & 14 & 15 \\3 & 21 & 23 & 25 & 27 & 25 \\4 & 17 & 18 & 21 & 23 & 20 \\5 & 18 & 18 & 16 & 19 & 20 \\\end{bmatrix}\end{array} $

With 5 jobs and 5 men, the stated problem is balanced.

$\begin{array}{l}A = \begin{bmatrix}20 & 15 & 18 & 20 & 25 \\18 & 20 & 12 & 14 & 15 \\21 & 23 & 25 & 27 & 25 \\17 & 18 & 21 & 23 & 20 \\18 & 18 & 16 & 19 & 20 \\\end{bmatrix}\end{array} $

Subtract the lowest cost element in each row from all of the elements in the given cost matrix’s row. Make sure that each row has at least one zero.

$\begin{array}{l}A = \begin{bmatrix}5 & 0 & 3 & 5 & 10 \\6 & 8 & 0 & 2 & 3 \\0 & 2 & 4 & 6 & 4 \\0 & 1 & 4 & 6 & 3 \\2 & 2 & 0 & 3 & 4 \\\end{bmatrix}\end{array} $

Subtract the least cost element in each Column from all of the components in the given cost matrix’s Column. Check to see if each column has at least one zero.

$\begin{array}{l}A = \begin{bmatrix}5 & 0 & 3 & 3 & 7 \\6 & 8 & 0 & 0 & 0 \\0 & 2 & 4 & 4 & 1 \\0 & 1 & 4 & 4 & 0 \\2 & 2 & 0 & 1 & 1 \\\end{bmatrix}\end{array} $

When the zeros are assigned, we get the following:

The present assignment is optimal because each row and column contain precisely one encircled zero.

Where 1 to II, 2 to IV, 3 to I, 4 to V, and 5 to III are the best assignments.

Hence, z = 15 + 14 + 21 + 20 + 16 = 86 hours is the optimal time.

Practice Question on Hungarian Method

Use the Hungarian method to solve the following assignment problem shown in table. The matrix entries represent the time it takes for each job to be processed by each machine in hours.

$\begin{array}{l}\begin{bmatrix}J/M & I & II & III & IV & V \\1 & 9 & 22 & 58 & 11 & 19 \\2 & 43 & 78 & 72 & 50 & 63 \\3 & 41 & 28 & 91 & 37 & 45 \\4 & 74 & 42 & 27 & 49 & 39 \\5 & 36 & 11 & 57 & 22 & 25 \\\end{bmatrix}\end{array} $

Stay tuned to BYJU’S – The Learning App and download the app to explore all Maths-related topics.

Frequently Asked Questions on Hungarian Method

What is hungarian method.

The Hungarian method is defined as a combinatorial optimization technique that solves the assignment problems in polynomial time and foreshadowed subsequent primal–dual approaches.

What are the steps involved in Hungarian method?

The following is a quick overview of the Hungarian method: Step 1: Subtract the row minima. Step 2: Subtract the column minimums. Step 3: Use a limited number of lines to cover all zeros. Step 4: Add some more zeros to the equation.

What is the purpose of the Hungarian method?

When workers are assigned to certain activities based on cost, the Hungarian method is beneficial for identifying minimum costs.

MATHS Related Links

Register with BYJU'S & Download Free PDFs

Cost matrix: How to construct and use it in assignment problems

1. introduction to assignment problems, 2. understanding the cost matrix, 3. constructing the cost matrix, 4. interpreting the cost matrix, 5. solving assignment problems using the cost matrix, 6. optimizing the cost matrix, 7. real-life applications of assignment problems, 8. limitations and challenges of cost matrix, 9. conclusion and further resources.

The process of assigning tasks or duties to a group of individuals or machines can be a daunting and time-consuming task. This is especially true when there are multiple tasks to be completed with different requirements and varying levels of expertise required. However, there is a solution to this problem: the assignment problem. The assignment problem is a fundamental problem in optimization theory and operations research that deals with the optimization of the allocation of resources to different tasks. In this section, we will introduce the assignment problem, discuss its importance and applications, and provide an overview of the different methods used to solve it.

1. Definition of Assignment Problem: The assignment problem is a combinatorial optimization problem that involves finding the best matching between two sets of items. In the context of resource allocation, it involves assigning a set of tasks to a group of individuals or machines with the objective of minimizing the total cost or maximizing the total profit.

2. Applications of Assignment Problem: The assignment problem has a wide range of applications in different fields such as transportation, logistics, scheduling, and economics. For example, in transportation, the problem can be used to assign delivery routes to trucks with the objective of minimizing the total distance traveled or the total time taken.

3. cost matrix : The cost matrix is a key component in solving the assignment problem. It is a matrix that represents the cost or profit of assigning each task to each individual or machine. The rows of the matrix represent the tasks, while the columns represent the individuals or machines. The values in the matrix represent the cost or profit of assigning each task to each individual or machine.

4. Methods to Solve Assignment Problems: There are several methods to solve the assignment problem, including the Hungarian algorithm, the shortest path algorithm, and the auction algorithm. Each method has its own advantages and disadvantages, and the choice of method depends on the specific problem and the available resources.

The assignment problem is a fundamental problem in optimization theory and operations research that deals with the optimization of resource allocation . The cost matrix is a key component in solving the problem, and there are several methods available to solve it. Understanding the assignment problem and its applications is essential for any organization that needs to allocate resources efficiently .

Introduction to Assignment Problems - Cost matrix: How to construct and use it in assignment problems

When it comes to solving assignment problems , cost matrix plays a crucial role in finding the optimal solution . The cost matrix is a table that contains the cost of assigning a particular task to a particular agent. Understanding the cost matrix is essential to construct and use it effectively in assignment problems. From a mathematical perspective, the cost matrix represents the objective function, which is the function that needs to be optimized. From a practical perspective, the cost matrix represents the real-world constraints and limitations.

Here are some in-depth insights on understanding the cost matrix:

1. The cost matrix can be asymmetric, which means the cost of assigning a task to an agent may not be the same as the cost of assigning the same task to another agent. For example, let's say we have three tasks and three agents. The cost of assigning task 1 to agent 1 may be different from the cost of assigning task 1 to agent 2. This asymmetry can occur due to several factors, such as skill level, availability, and distance.

2. The cost matrix can have infinite values, which means some tasks cannot be assigned to certain agents. For example, let's say we have four tasks and two agents. Task 1 and task 2 require a particular skill that agent 1 does not possess. Therefore, the cost of assigning task 1 or task 2 to agent 1 is infinite. This infinite value indicates that assigning these tasks to agent 1 is not feasible.

3. The cost matrix can include negative values, which means some tasks are profitable to assign. For example, let's say we have two tasks and two agents. Assigning task 1 to agent 1 results in a profit of $10, whereas assigning task 2 to agent 2 results in a profit of $5. In this case, the cost matrix includes negative values, which means we can maximize the profit by assigning tasks to the appropriate agents.

Understanding the cost matrix is crucial to construct and use it effectively in assignment problems. By considering the insights mentioned above, we can create an accurate cost matrix that reflects the real-world constraints and limitations.

Understanding the Cost Matrix - Cost matrix: How to construct and use it in assignment problems

When it comes to solving assignment problems, constructing the cost matrix is an essential step. The cost matrix represents the costs of assigning a certain worker to a specific task. The matrix can be constructed in different ways, depending on the type of the assignment problem. There are two main types of assignment problems: the balanced assignment problem, where the number of workers is equal to the number of tasks, and the unbalanced assignment problem, where the number of workers is not equal to the number of tasks. Each type of assignment problem requires a different approach in constructing the cost matrix.

Here are some insights about constructing the cost matrix:

1. For the balanced assignment problem, the cost matrix is a square matrix, where the number of rows and columns are equal to the number of workers or tasks. The cost of assigning a worker to a task is placed in the corresponding cell of the matrix. For example, consider a scenario where there are three workers and three tasks. The cost matrix would look like this:

|Worker 1| 2 | 5 | 1 |

|Worker 2| 3 | 2 | 6 |

|Worker 3| 4 | 1 | 7 |

2. For the unbalanced assignment problem, the cost matrix is a rectangular matrix, where the number of rows and columns are not equal. In this case, a dummy row or column is added to make the matrix square. The cost of assigning a worker to a task is placed in the corresponding cell of the matrix, and the cost of assigning a worker to the dummy task or a task to the dummy worker is set to infinity. For example, consider a scenario where there are three workers and two tasks. The cost matrix would look like this:

|Worker 1| 2 | 5 | |

|Worker 2| 3 | 2 | |

|Worker 3| 4 | 1 | |

3. The cost matrix can also be constructed using distance measures, such as Euclidean distance or Manhattan distance . In this case, the cost represents the distance between the worker and the task. For example, consider a scenario where the workers and tasks are located in a two-dimensional space. The cost matrix can be constructed using the Euclidean distance between the worker and the task. The cost of assigning a worker to a task is then placed in the corresponding cell of the matrix.

Constructing the cost matrix is a crucial step in solving assignment problems. It determines the cost of assigning a worker to a task and provides the necessary information for finding the optimal solution. Different types of assignment problems require different approaches in constructing the cost matrix. By following the insights provided above, one can construct the cost matrix effectively and efficiently.

Constructing the Cost Matrix - Cost matrix: How to construct and use it in assignment problems

The cost matrix is an essential component in assignment problems. It is a square matrix that contains the costs of assigning each element in the row to each element in the column. The cost matrix can be interpreted in different ways, depending on the problem at hand. In this section, we will discuss how to interpret the cost matrix in assignment problems.

1. Interpretation as a distance matrix

One way to interpret the cost matrix is as a distance matrix. This is particularly useful when the assignment problem involves finding the shortest distance between two points. In this case, the cost matrix would contain the distances between each point. For example, consider a delivery company that needs to find the shortest route between several locations. The cost matrix would contain the distances between each location, and the assignment problem would involve finding the shortest route that visits each location once.

2. Interpretation as a similarity matrix

Another way to interpret the cost matrix is as a similarity matrix. This is useful when the assignment problem involves finding the best match between two sets of objects. In this case, the cost matrix would contain the similarities between each object. For example, consider a dating app that needs to match users based on their interests. The cost matrix would contain the similarities between each user's interests, and the assignment problem would involve finding the best match for each user.

3. Interpretation as a cost matrix

The most common interpretation of the cost matrix is as a cost matrix . This is useful when the assignment problem involves minimizing the total cost of assigning elements from one set to another. In this case, the cost matrix would contain the costs of assigning each element in the row to each element in the column. For example, consider a company that needs to assign employees to projects. The cost matrix would contain the costs of assigning each employee to each project, and the assignment problem would involve minimizing the total cost of assigning all employees to a project.

The cost matrix can be interpreted in different ways depending on the problem at hand. It can be interpreted as a distance matrix, a similarity matrix, or a cost matrix. Understanding the different interpretations of the cost matrix is crucial in constructing and solving assignment problems.

Interpreting the Cost Matrix - Cost matrix: How to construct and use it in assignment problems

When solving an assignment problem, the cost matrix plays a crucial role. It helps to identify the optimal assignment, where the sum of the costs is minimized. The cost matrix is constructed using the costs associated with each task and each agent. Assigning a task to an agent results in a cost that is entered into the matrix. When the matrix is complete, optimization algorithms can be used to identify the optimal assignment. Here are some key points to keep in mind when solving assignment problems using the cost matrix:

1. The cost matrix should be constructed with care. It is important to ensure that each cost is accurately reflected in the matrix. One way to do this is to double-check the costs before entering them into the matrix. For example, if the cost of assigning task A to agent X is $5, make sure that this cost is correct before entering it into the matrix.

2. The optimal assignment can be identified using optimization algorithms. The Hungarian algorithm and the auction algorithm are two common algorithms used to find the optimal assignment. These algorithms take the cost matrix as input and output the optimal assignment.

3. The optimal assignment may not always be unique. In some cases, there may be multiple assignments that result in the same minimum cost. When this happens, any of the optimal assignments can be chosen.

4. The cost matrix can be used to solve a variety of assignment problems. For example, it can be used to assign tasks to employees, to assign vehicles to routes, and to assign machines to production tasks.

5. The cost matrix can be modified to reflect changing costs. If the cost of assigning a task to an agent changes, the cost matrix can be updated accordingly. This allows for the optimal assignment to be recalculated based on the new costs.

The cost matrix is an essential tool for solving assignment problems. It allows for the identification of the optimal assignment, which results in minimized costs. By constructing the matrix carefully and using optimization algorithms, the optimal assignment can be found quickly and accurately.

Solving Assignment Problems using the Cost Matrix - Cost matrix: How to construct and use it in assignment problems

optimizing the cost matrix is an essential step in constructing and using it in assignment problems. This process aims to minimize the overall cost of the assignment, making it an efficient and cost-effective solution. The optimization process can be approached from different points of view, such as minimizing the total cost, maximizing the overall efficiency, or achieving a balance between cost and efficiency. In this section, we will discuss some of the methods used to optimize the cost matrix and their advantages.

1. Row and column reduction: This method involves subtracting the minimum value of each row and column from the cost matrix to reduce the overall cost. The advantage of this method is that it is simple and easy to implement. For example, suppose we have a cost matrix of size n x n. To reduce the cost, we need to find the minimum value of each row and subtract it from all the elements in that row. Similarly, we need to find the minimum value of each column and subtract it from all the elements in that column.

2. Hungarian algorithm: This algorithm is an efficient method for solving assignment problems and optimizing the cost matrix. It involves finding the minimum number of lines required to cover all the zeros in the reduced matrix. The advantage of this method is that it guarantees an optimal solution and is suitable for large-sized matrices. For example, suppose we have a cost matrix of size n x n. To use the Hungarian algorithm, we need to reduce the matrix using the row and column reduction method and then find the minimum number of lines required to cover all the zeros in the reduced matrix.

3. Branch and bound method: This method involves dividing the problem into sub-problems and solving them recursively. The advantage of this method is that it can handle complex problems and find the optimal solution. For example, suppose we have a cost matrix of size n x n. To use the branch and bound method, we need to divide the problem into sub-problems and solve them recursively until we find the optimal solution.

Optimizing the cost matrix is an important step in constructing and using it in assignment problems. The methods discussed above are some of the most commonly used methods to optimize the cost matrix and find the optimal solution. Depending on the problem's complexity and size, one method may be more suitable than the others.

Optimizing the Cost Matrix - Cost matrix: How to construct and use it in assignment problems

When it comes to real-life applications , the assignment problem is frequently utilized in various fields. One of the most common areas is in logistics, where the problem is used to optimize transportation of goods. The assignment problem can also be applied in sports, where it can help coaches determine which team members should play in a particular game. Additionally, the assignment problem can be used in the field of computer science , where it is used to solve problems related to resource allocation. Here are some more specific examples:

1. In the healthcare industry, the assignment problem can be used to match patients with the most appropriate healthcare providers . This can help ensure that patients receive the care they need from the most qualified professionals.

2. In the field of economics, the assignment problem can be used to match workers with jobs. This can help to minimize unemployment and ensure that the right people are in the right jobs.

3. In the field of agriculture, the assignment problem can be used to determine which crops should be grown on which fields. By optimizing crop selection, farmers can improve yields and maximize profits.

Overall, the assignment problem has a wide range of applications and can be used to solve a variety of different problems. Whether you are working in logistics, healthcare, economics, or agriculture, the assignment problem can help you optimize your operations and achieve better results.

Real life Applications of Assignment Problems - Cost matrix: How to construct and use it in assignment problems

The cost matrix is an essential component of assignment problems. It provides a visual representation of the costs associated with assigning tasks to individuals or machines. However, like any other tool, the cost matrix has its limitations and challenges that one should be aware of when using it. These limitations and challenges can affect the accuracy and efficiency of the results obtained from the cost matrix. In this section, we will discuss some of the limitations and challenges of the cost matrix.

1. Difficulty in determining costs: One of the primary challenges of the cost matrix is determining the costs associated with assigning tasks. Depending on the nature of the task, the costs can be challenging to estimate. For example, if the task involves a machine, the cost could be the energy consumed, maintenance required, or depreciation of the machine. On the other hand, if the task involves an individual, the cost could be the hourly wage, training costs, or travel expenses. Determining these costs can be time-consuming, and if not done accurately, it can lead to inaccurate results.

2. Limited flexibility: The cost matrix assumes that the cost of each task is fixed and does not change over time. However, in real-world scenarios , the cost of tasks can vary depending on several factors, such as demand, availability, and competition. Therefore, the cost matrix may not be suitable for situations where the cost of tasks is highly variable.

3. Inability to account for qualitative factors: The cost matrix only considers quantitative factors, such as the cost of tasks and resources. It does not account for qualitative factors such as the skills and experience of individuals or the quality of the equipment used. Therefore, the cost matrix may not be suitable for situations where the quality of work is critical.

4. Size limitations: The size of the cost matrix can also be a limitation. As the number of tasks and resources increases, the size of the cost matrix can become too large to handle efficiently. This can lead to longer computation times, increased memory requirements, and reduced accuracy.

5. Limited use cases: The cost matrix is most suitable for assignment problems where the number of tasks and resources is relatively small. In situations where the number of tasks and resources is significant, alternative optimization techniques such as linear programming may be more appropriate.

While the cost matrix is a valuable tool for solving assignment problems, it is essential to be aware of its limitations and challenges. By understanding these limitations and challenges, we can make better decisions about when and how to use the cost matrix.

Limitations and Challenges of Cost Matrix - Cost matrix: How to construct and use it in assignment problems

Constructing and using cost matrices is an important part of solving assignment problems. From a mathematical perspective, cost matrices provide a clear representation of the costs associated with each assignment. From a practical standpoint, cost matrices allow businesses and organizations to optimize their resources and assign tasks in the most efficient way possible.

If you're interested in learning more about cost matrices and their applications, there are a number of resources available. Here are a few worth checking out:

1. Linear programming textbooks - Cost matrices are an important part of linear programming, and many textbooks on the subject cover them in detail. Some popular options include "Linear Programming: Foundations and Extensions" by Robert Vanderbei and "Introduction to Linear Optimization" by Dimitris Bertsimas and John N. Tsitsiklis.

2. Online tutorials - If you prefer to learn through online resources, there are a number of tutorials available that cover cost matrices. For example, the website MathIsFun.com has a clear and concise tutorial on the subject.

3. Problem sets - The best way to learn how to use cost matrices is to practice with them. Look for problem sets online or create your own using real-world scenarios. For example, imagine you run a catering business and need to assign tasks to your employees for a large event. Use a cost matrix to determine the most efficient way to assign tasks based on each employee's skills and availability.

By familiarizing yourself with cost matrices and their applications, you'll be better equipped to solve assignment problems and optimize resources in a variety of settings.

Conclusion and Further Resources - Cost matrix: How to construct and use it in assignment problems

Read Other Blogs

Capital structure research is a branch of finance that studies how firms choose and manage their...

In today's fast-paced and competitive business world, reading is not just a leisure activity, but a...

Venturing into the realm of early-stage startups, one encounters a dynamic ecosystem where angel...

The rapid growth of educational technology (EdTech) has opened up new possibilities for learning...

In the realm of customer relationship management (CRM), the integration of analytics has...

In the realm of persistence strategies, ensuring data consistency is akin to conducting a symphony...

Market research is the compass that guides startups through the uncharted waters of the business...

In the realm of oral health, the fusion of clinical expertise and business acumen has given rise to...

In today's fiercely competitive business landscape, the decision to outsource non-core tasks can be...

Assignment Problem

Feb 20, 2024

The assignment problem is a special case of transportation problem.

Suppose there are $n$ jobs to be performed and $n$ persons are available for these jobs. Assume that each person can do each job at a time, though with varying degree of efficiency.

Let $c_{ij}$ be the cost if the $i^{th}$ person is assigned the $j^{th}$ job. Then the problem is to find an assignment so that the total cost of performing all jobs is minimum. (i.e., which job should be assigned to which person with minimum cost). Such problem is called an Assignment Problem (AP).

The tabular form of the assignment problem is as follows

Persons \ Jobs	$1$	$2$	$\cdots$	$j$	$\cdots$	$n$
Persons/ Jobs	$1$	$2$	$\cdots$	$j$	$\cdots$	$n$
$1$	$c_{11}$	$c_{12}$	$\cdots$	$c_{1j}$	$\cdots$	$c_{1n}$
$2$	$c_{21}$	$c_{22}$	$\cdots$	$c_{2j}$	$\cdots$	$c_{2n}$
$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$
$i$	$c_{i1}$	$c_{i2}$	$\cdots$	$c_{ij}$	$\cdots$	$c_{in}$
$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$
$n$	$c_{n1}$	$c_{n2}$	$\cdots$	$c_{nj}$	$\cdots$	$c_{nn}$

The above table is called the $n\times n$ cost-matrix, where $c_{ij}$ are real numbers.

Thus the objective in the Assignment Problem is to assign a number of jobs to the equal number of persons at a minimum cost or maximum profit. e.g. assigning men to offices, classes to rooms, drivers to trucks, problems to research teams etc.

Mathematical Formulation of AP

Mathematically, the AP can be stated as $$ \begin{equation}\label{eq2.4} \min z = \sum_{i=1}^n\sum_{j=1}^n x_{ij} c_{ij}. \end{equation} $$ subject to $$ \begin{equation}\label{eq2.5} \sum_{j=1}^n x_{ij} =1,; \text{ for } i=1,2,\ldots, n \end{equation} $$

$$ \begin{equation}\label{eq2.6} \sum_{i=1}^n x_{ij} =1,; \text{ for } j=1,2,\ldots,n \end{equation} $$ where $$ \begin{equation*} x_{ij}=\left{ \begin{array}{ll} 1, & \hbox{if $i^{th}$ person is assigned $j^{th}$ job;} \ 0, & \hbox{otherwise.} \end{array} \right. \end{equation*} $$ Constraint \eqref{eq2.5} indicate that one job is done by $i^{th}$ person $i=1,2,\ldots, n$ and constraint \eqref{eq2.6} indicate that one person should be assigned $j^{th}$ job $j=1,2,\ldots, n$.

It may be observed from the above formulation that AP is a special type of Linear programming problem.

Unbalanced Assignment Problem

If the cost matrix of an assignment problem is not a square matrix, the assignment problem is called an Unbalanced Assignment Problem . In such a case, add dummy row or dummy column with zero cost in the cost matrix so as to form a square matrix. Then apply the usual assignment method to find the optimal solution.

Maximal Assignment Problem

Sometimes, the assignment problem deals with the maximization of an objective function instead of minimization.. For example, it may be required to assign persons to jobs in such a way that the expected profit is maximum. In such a case, first convert the problem of maximization to minimization and apply the usual procedure of assignment.

The assignment problem of maximization type can be converted to minimization type by subtracting all the elements of the given profit matrix from the largest element.

Restrictions on Assignment

Sometimes due to technical or other difficulties do not permit the assignment of a particular facility to a particular job. In such a situation, the difficulty can be overcome by assigning a very high cost (say, infinity i.e. $\infty$) to the corresponding cell.

Because of assigning an infinite penalty to such a cell the activity will be automatically excluded from the optimal solution. Then apply the usual procedure to find the optimal assignment.

Procedure, Example Solved Problem | Operations Research - Solution of assignment problems (Hungarian Method) | 12th Business Maths and Statistics : Chapter 10 : Operations Research

Chapter: 12th business maths and statistics : chapter 10 : operations research.

Solution of assignment problems (Hungarian Method)

First check whether the number of rows is equal to the numbers of columns, if it is so, the assignment problem is said to be balanced.

Step :1 Choose the least element in each row and subtract it from all the elements of that row.

Step :2 Choose the least element in each column and subtract it from all the elements of that column. Step 2 has to be performed from the table obtained in step 1.

Step:3 Check whether there is atleast one zero in each row and each column and make an assignment as follows.

Step :4 If each row and each column contains exactly one assignment, then the solution is optimal.

Example 10.7

Solve the following assignment problem. Cell values represent cost of assigning job A, B, C and D to the machines I, II, III and IV.

Here the number of rows and columns are equal.

∴ The given assignment problem is balanced. Now let us find the solution.

Step 1: Select a smallest element in each row and subtract this from all the elements in its row.

Look for atleast one zero in each row and each column.Otherwise go to step 2.

Step 2: Select the smallest element in each column and subtract this from all the elements in its column.

Since each row and column contains atleast one zero, assignments can be made.

Step 3 (Assignment):

Thus all the four assignments have been made. The optimal assignment schedule and total cost is

The optimal assignment (minimum) cost

Example 10.8

Consider the problem of assigning five jobs to five persons. The assignment costs are given as follows. Determine the optimum assignment schedule.

∴ The given assignment problem is balanced.

Now let us find the solution.

The cost matrix of the given assignment problem is

Column 3 contains no zero. Go to Step 2.

Thus all the five assignments have been made. The Optimal assignment schedule and total cost is

The optimal assignment (minimum) cost = ` 9

Example 10.9

Solve the following assignment problem.

Since the number of columns is less than the number of rows, given assignment problem is unbalanced one. To balance it , introduce a dummy column with all the entries zero. The revised assignment problem is

Here only 3 tasks can be assigned to 3 men.

Step 1: is not necessary, since each row contains zero entry. Go to Step 2.

Step 3 (Assignment) :

Since each row and each columncontains exactly one assignment,all the three men have been assigned a task. But task S is not assigned to any Man. The optimal assignment schedule and total cost is

The optimal assignment (minimum) cost = ₹ 35

Description

M = matchpairs( Cost , costUnmatched ) solves the linear assignment problem for the rows and columns of the matrix Cost . Each row is assigned to a column in such a way that the total cost is minimized. costUnmatched specifies the cost per row of not assigning each row, and also the cost per column of not having a row assigned to each column.

[ M , uR , uC ] = matchpairs( Cost , costUnmatched ) additionally returns indices for unmatched rows in uR and indices for unmatched columns in uC .

[ ___ ] = matchpairs( Cost , costUnmatched , goal ) specifies the goal of the optimization using any of the output argument combinations in previous syntaxes. goal can be 'min' or 'max' to produce matches that either minimize or maximize the total cost.

collapse all

Assign Flights with Minimal Cost

Assign salespeople to flights such that the total cost of transportation is minimized.

A company has four salespeople who need to travel to key cities around the country. The company must book their flights, and wants to spend as little money as possible. These salespeople are based in different parts of the country, so the cost for them to fly to each city varies.

This table shows the cost for each salesperson to fly to each key city.

Dallas Chicago New York City St. Louis Fred $ 6 0 0 $ 6 7 0 $ 9 6 0 $ 5 6 0 Beth $ 9 0 0 $ 2 8 0 $ 9 7 0 $ 5 4 0 Sue $ 3 1 0 $ 3 5 0 $ 9 5 0 $ 8 2 0 Greg $ 3 2 5 $ 2 9 0 $ 6 0 0 $ 5 4 0

Each city represents a sales opportunity. If a city is missed, then the company loses out on an average revenue gain of $2,000.

Create a cost matrix to represent the cost of each salesperson flying to each city.

Use matchpairs to assign the salespeople to the cities with minimal cost. Specify the cost of unassignment as 1000, since the cost of unassignment is counted twice if a row and a column remain unmatched.

matchpairs calculates the least expensive way to get a salesperson to each city.

Dallas Chicago New York City St. Louis Fred $ 6 0 0 $ 6 7 0 $ 9 6 0 $ 560 Beth $ 9 0 0 $ 280 $ 9 7 0 $ 5 4 0 Sue $ 310 $ 3 5 0 $ 9 5 0 $ 8 2 0 Greg $ 3 2 5 $ 2 9 0 $ 600 $ 5 4 0

Unequal Numbers of Rows and Columns

Match rows to columns when you have many more columns than rows in the cost matrix.

Create a 3-by-8 cost matrix. Since you have only three rows, matchpairs can produce at most three matches with the eight columns.

Use matchpairs to match the rows and columns of the cost matrix. To get the maximum number of matches, use a large cost of unassignment (relative to the magnitude of the entries in the cost matrix). Specify three outputs to return the indices of unmatched rows and columns.

Five of the columns in C are not matched with any rows.

Assign Taxis to Maximize Profit

Assign taxis to routes such that the profit is maximized.

A taxi company has several ride requests from across the city. The company wants to dispatch its limited number of taxis in a way that makes the most money.

This table shows the estimated taxi fare for each of five ride requests. Only three of the five ride requests can be filled.

Ride 1 Ride 2 Ride 3 Ride 4 Ride 5 Cab A $ 5 . 7 0 $ 6 . 3 0 $ 3 . 1 0 $ 4 . 8 0 $ 3 . 5 0 Cab B $ 5 . 8 0 $ 6 . 4 0 $ 3 . 3 0 $ 4 . 7 0 $ 3 . 2 0 Cab C $ 5 . 7 0 $ 6 . 3 0 $ 3 . 2 0 $ 4 . 9 0 $ 3 . 4 0

Create a profits matrix to represent the profits of each taxi ride.

Use matchpairs to match the taxis to the most profitable rides. Specify three outputs to return any unmatched rows and columns, and the 'max' option to maximize the profits. Specify the cost of unassignment as zero, since the company makes no money from unfilled taxis or ride requests.

matchpairs calculates the most profitable rides to fill. The solution leaves ride requests 3 and 5 unfilled.

Calculate the total profits for the calculated solution. Since costUnmatched is zero, you only need to add together the profits from each match.

Track Point Positions over Time

Use matchpairs to track the movement of several points by minimizing the total changes in distance.

Plot a grid of points at time t = 0 in green. At time t = 1 , some of the points move a small amount in a random direction.

Use matchpairs to match the points at t = 0 with the points at t = 1 . To do this, first calculate a cost matrix where C(i,j) is the Euclidean distance from point i to point j .

Next, use matchpairs to match the rows and columns in the cost matrix. Specify the cost of unassignment as 1. With such a low cost of unassignment relative to the entries in the cost matrix, it is likely matchpairs will leave some points unmatched.

The values M(:,2) correspond to the original points ( x 0 , y 0 ) , while the values M(:,1) correspond to the moved points ( x 1 , y 1 ) .

Plot the matched pairs of points. The points that moved farther than 2*costUnmatched away from the original point remain unmatched.

Input Arguments

Cost — cost matrix matrix.

Cost matrix. Each entry Cost(i,j) specifies the cost of assigning row i to column j .

Data Types: single | double

costUnmatched — Cost of not matching scalar

Cost of not matching, specified as a scalar. matchpairs compares the value of 2*costUnmatched to the entries in Cost to determine whether it is more beneficial for a row or column to remain unmatched. Use this parameter to make matches more or less likely in the algorithm. For more information, see linear assignment problem .

Example: M = matchpairs(C,10) specifies a cost of 10 for not matching a row or column of C .

goal — Optimization goal 'min' (default) | 'max'

Optimization goal, specified as either 'min' or 'max' . The optimization goal specifies whether the total cost should be minimized or maximized.

Example: M = matchpairs(Cost,costUnmatched,'max') specifies that the rows and columns of Cost should be matched together to maximize the total cost.

Output Arguments

M — matches matrix.

Matches, returned as a matrix. M is a p -by- 2 matrix, where M(i,1) and M(i,2) are the row and column indices of a matched pair in the cost matrix. The rows of M are sorted with the second column in ascending order.

Each row and column can be matched a single time only, so each M(i,1) value and each M(i,2) value is unique.

M contains p matches, and p is less than or equal to the maximum number of matches min(size(Cost)) .

The cost of the matches in M is sum([Cost(M(1,1),M(1,2)), Cost(M(2,1),M(2,2)), ..., Cost(M(p,1),M(p,2))]) .

uR — Unassigned rows column vector

Unassigned rows, returned as a column vector of indices. The entries in uR indicate which rows in Cost are unassigned. Each entry in uR and uC contributes to the total cost of the solution according to costUnassigned .

uC — Unassigned columns column vector

Unassigned columns, returned as a column vector of indices. The entries in uC indicate which columns in Cost are unassigned. Each entry in uR and uC contributes to the total cost of the solution according to costUnassigned .

Linear Assignment Problem

The linear assignment problem is a way of assigning rows to columns such that each row is assigned to a column and the total cost of the assignments is minimized (or maximized). The cost of assigning each row to each column is captured in a cost matrix . The entry Cost(i,j) is the cost of assigning row i to column j .

The cost of unassignment assigns a cost to any row or column that is not matched. This practice allows for minimum-cost solutions that do not assign all rows or columns. If a row and column are not matched, this increases the total cost by 2*costUnmatched .

The total cost of a solution M is the sum of the cost of all matched pairs added to the cost of all unmatched pairs:

T C = ∑ i = 1 p Cost ( M ( i , 1 ) , M ( i , 2 ) ) + costUnmatched ⋅ ( m + n − 2 p )

In code the total cost is

Cost is an m -by- n matrix.

M is a p -by- 2 matrix, where M(i,1) and M(i,2) are the row and column of a matched pair.

(m+n-2*p) is the total number of unmatched rows and columns.

[1] Duff, I.S. and J. Koster. "On Algorithms For Permuting Large Entries to the Diagonal of a Sparse Matrix." SIAM J. Matrix Anal. & Appl. 22(4), 2001. pp 973–996.

Extended Capabilities

C/c++ code generation generate c and c++ code using matlab® coder™..

Usage notes and limitations:

Code generation does not support sparse matrix inputs for this function.

Version History

Introduced in R2019a

equilibrate | sprank | dmperm

MATLAB Command

You clicked a link that corresponds to this MATLAB command:

Run the command by entering it in the MATLAB Command Window. Web browsers do not support MATLAB commands.

Select a Web Site

Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .

Switzerland (English)
Switzerland (Deutsch)
Switzerland (Français)
中国 (English)

You can also select a web site from the following list:

How to Get Best Site Performance

Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.

América Latina (Español)
Canada (English)
United States (English)
Belgium (English)
Denmark (English)
Deutschland (Deutsch)
España (Español)
Finland (English)
France (Français)
Ireland (English)
Italia (Italiano)
Luxembourg (English)
Netherlands (English)
Norway (English)
Österreich (Deutsch)
Portugal (English)
Sweden (English)
United Kingdom (English)

Asia Pacific

Australia (English)
India (English)
New Zealand (English)

Contact your local office

OPERATIONS RESEARCH

Lesson 9. solution of assignment problem.

Current course

Google OR-Tools
Español – América Latina
Português – Brasil
Tiếng Việt

Assignment as a Minimum Cost Flow Problem

You can use the min cost flow solver to solve special cases of the assignment problem .

In fact, min cost flow can often return a solution faster than either the MIP or CP-SAT solver. However, MIP and CP-SAT can solve a larger class of problems than min cost flow, so in most cases MIP or CP-SAT are the best choices.

The following sections present Python programs that solve the following assignment problems using the min cost flow solver:

A minimal linear assignment example .
An assignment problem with teams of workers .

Linear assignment example

This section show how to solve the example, described in the section Linear Assignment Solver , as a min cost flow problem.

Import the libraries

The following code imports the required library.

Declare the solver

The following code creates the minimum cost flow solver.

Create the data

The flow diagram for the problem consists of the bipartite graph for the cost matrix (see the assignment overview for a slightly different example), with a source and sink added.

The data contains the following four arrays, corresponding to the start nodes, end nodes, capacities, and costs for the problem. The length of each array is the number of arcs in the graph.

To make clear how the data is set up, each array is divided into three sub-arrays:

The first array corresponds to arcs leading out of the source.
The second array corresponds to the arcs between workers and tasks. For the costs , this is just the cost matrix (used by the linear assignment solver), flattened into a vector.
The third array corresponds to the arcs leading into the sink.

The data also includes the vector supplies , which gives the supply at each node.

How a min cost flow problem represents an assignment problem

How does the min cost flow problem above represent an assignment problem? First, since the capacity of every arc is 1, the supply of 4 at the source forces each of the four arcs leading into the workers to have a flow of 1.

Next, the flow-in-equals-flow-out condition forces the flow out of each worker to be 1. If possible, the solver would direct that flow across the minimum cost arc leading out of each worker. However, the solver cannot direct the flows from two different workers to a single task. If it did, there would be a combined flow of 2 at that task, which couldn't be sent across the single arc with capacity 1 from the task to the sink. This means that the solver can only assign a task to a single worker, as required by the assignment problem.

Finally, the flow-in-equals-flow-out condition forces each task to have an outflow of 1, so each task is performed by some worker.

Create the graph and constraints

The following code creates the graph and constraints.

Invoke the solver

The following code invokes the solver and displays the solution.

The solution consists of the arcs between workers and tasks that are assigned a flow of 1 by the solver. (Arcs connected to the source or sink are not part of the solution.)

The program checks each arc to see if it has flow 1, and if so, prints the Tail (start node) and the Head (end node) of the arc, which correspond to a worker and task in the assignment.

Output of the program

Here is the output of the program.

The result is the same as that for the linear assignment solver (except for the different numbering of workers and costs). The linear assignment solver is slightly faster than min cost flow — 0.000147 seconds versus 0.000458 seconds.

The entire program

The entire program is shown below.

Assignment with teams of workers

This section presents a more general assignment problem. In this problem, six workers are divided into two teams. The problem is to assign four tasks to the workers so that the workload is equally balanced between the teams — that is, so each team performs two of the tasks.

For a MIP solver solution to this problem see Assignment with Teams of Workers .

The following sections describe a program that solves the problem using the min cost flow solver.

The following code creates the data for the program.

The workers correspond to nodes 1 - 6. Team A consists of workers 1, 3, and 5, and team B consists of workers 2, 4, and 6. The tasks are numbered 7 - 10.

There are two new nodes, 11 and 12, between the source and workers. Node 11 is connected to the nodes for team A, and Node 12 is connected to the nodes for team B, with arcs of capacity 1. The graph below shows just the nodes and arcs from the source to the workers.

The key to balancing the workload is that the source 0 is connected to nodes 11 and 12 by arcs of capacity 2. This means that nodes 11 and 12 (and therefore teams A and B) can have a maximum flow of 2. As a result, each team can perform at most two of the tasks.

Create the constraints

The following shows the output of the program.

Team A is assigned tasks 9 and 10, while team B is assigned tasks 7 and 8.

Note that the min cost flow solver is faster for this problem than the MIP solver , which takes around 0.006 seconds.

Except as otherwise noted, the content of this page is licensed under the Creative Commons Attribution 4.0 License , and code samples are licensed under the Apache 2.0 License . For details, see the Google Developers Site Policies . Java is a registered trademark of Oracle and/or its affiliates.

Last updated 2024-08-28 UTC.

Stack Overflow for Teams Where developers & technologists share private knowledge with coworkers
Advertising & Talent Reach devs & technologists worldwide about your product, service or employer brand
OverflowAI GenAI features for Teams
OverflowAPI Train & fine-tune LLMs
Labs The future of collective knowledge sharing
About the company Visit the blog

Collectives™ on Stack Overflow

Find centralized, trusted content and collaborate around the technologies you use most.

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

Get early access and see previews of new features.

Most efficient way to build cost matrix for linear sum assignment?

Suppose we want to solve a linear sum assignment with scipy and the cost for the assignment can be build from Euclidean distances.

Thus, out of m workers W=[j_1, ..., j_m] and n tasks T=[t_1, ..., t_n] , the cost matrix is given by

This looks computationally heavy and not very efficient. Is there a numpy/scipy way to do this better and faster?

Working example:

2 Answers 2

I believe what you are looking for is cdist . Scipy cdist

Here is your example with working code:

This may not be the most efficient way but iteration is passed on to numpy so this may be faster:

Why not just broadcast the arrays together? – Mad Physicist Commented Apr 20, 2020 at 14:05
Try this: t.reshape(-1, 1) - w . That won't make full arrays for anything but the output. – Mad Physicist Commented Apr 20, 2020 at 14:16

Your Answer

Reminder: Answers generated by artificial intelligence tools are not allowed on Stack Overflow. Learn more

Sign up or log in

Post as a guest.

Required, but never shown

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy .

Not the answer you're looking for? Browse other questions tagged python numpy scipy or ask your own question .

The Overflow Blog
Where does Postgres fit in a world of GenAI and vector databases?
Mobile Observability: monitoring performance through cracked screens, old...
Featured on Meta
We've made changes to our Terms of Service & Privacy Policy - July 2024
Bringing clarity to status tag usage on meta sites
What does a new user need in a homepage experience on Stack Overflow?
Feedback requested: How do you use tag hover descriptions for curating and do...
Staging Ground Reviewer Motivation

Hot Network Questions

Using \tl_put_right with grouping from latex3 explsyntax
Has a tire ever exploded inside the Wheel Well?
What are some refutations to the etymological fallacy?
The answer is not wrong
What is the difference between a "Complaint for Civil Protection Order" and a "Motion for Civil Protection Order"?
How can I delete a column from several CSV files?
What are the 270 mitzvot relevant today?
How can I get an Edge's Bevel Weight attribute value via Python?
Which hash algorithms support binary input of arbitrary bit length?
Why is "on " the optimal preposition in this case?
about flag changes in 16-bit calculations on the MC6800
Why does flow separation cause an increase in pressure drag?
Dress code for examiner in UK PhD viva
Image Intelligence concerning alien structures on the moon
Large file manipulation
Ring Buffer Implementation in C++
Command-line script that strips out all comments in given source files
Reference request: acceleration/curvature of curve in metric space
What happens if all nine Supreme Justices recuse themselves?
How did Oswald Mosley escape treason charges?
If a trigger runs an update will it ALWAYS have the same timestamp for a temporal table?
My toilet has no working parts in the tank. I poured water into the bowl but it didn't work. Can it work without the tank?
What unique phenomena would be observed in a system around a hypervelocity star?
Is this a mistake or am I misunderstanding how to calculate a capacitor's impedance with ESR and ESL?

The assignment problem as a cooperative game

Published: 28 August 2024

Cite this article

V. V. Morozov 1 &
S. I. Romanov 1

We consider the problem of optimal distribution of assignments between workers on machines. Workers can exchange machines with the aim of saving the total time to execute the assignments, compared to their initial distribution. It is proved that the corresponding cooperative game has a non-empty c -core and is totally balanced. Based on the Hungarian method of solving the assignment problem, an algorithm for constructing an imputation from the c -core is formulated. In the case of an integer characteristic function, the algorithm constructs an imputation from the c -core with integer components. This result is generalized to the case of arbitrary totally balanced games of three and four persons, as well as for symmetric games.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save.

Get 10 units per month
Download Article/Chapter or eBook
1 Unit = 1 Article or 1 Chapter
Cancel anytime

Price includes VAT (Russian Federation)

Instant access to the full article PDF.

Rent this article via DeepDyve

Institutional subscriptions

Assignment Games with Conflicts: Robust Price of Anarchy and Convergence Results via Semi-Smoothness

A note on assignment games with the same nucleolus.

An Extension of a Class of Cost Sharing Methods to the Class of Solutions to Two-Person Cooperative Games

Mazalov, V.V.: Matematicheskaya teoriya igr i prilozheniya [in Russian] (Mathematical game theory and applications). Lan, Saint-Petersburg (2010)

Google Scholar

Peleg, B., Sudhölter, P.: Introduction to the theory of cooperative games. Springer-Verlag, Berlin (2007)

Bondareva, O.N.: Nekotorye primeneniya metodov lineynogo programmirovaniya k teorii kooperativnyh igr [in Russian] (Some applications of linear programming methods to the theory of cooperative games). Probl. Cybern. 10 , 119–140 (1963)

Shapley, L.S.: On balanced sets and cores. RM-4601-PR. The Rand Corporation, Santa Monica, California (1965)

Charnes, A., Kortanek, K.: On balanced sets, cores and programming. Cah. Centre Etudes Rech. Oper. 9 (1), 32–43 (1967)

MathSciNet Google Scholar

Vasin, A.A., Morozov, V.V.: Teoriya igr i modeli matematicheskoy ekonomiki [in Russian] (Game theory and models of mathematical economics). MAX Press, Moscow (2005)

Peleg, B.: An inductive method for constructing minimal balanced collections of finite sets. Nav. Res. Logist. Quart. 12 (2), 155–162 (1965)

Article MathSciNet Google Scholar

Raiser, G.D.: Combinatorial mathematics. Mir, Moscow (1966)

Kuhn, H.W.: The Hungarian method for the assignment problem. Nav. Res. Logist. Quart. 2 (1-2), 155–162 (1955)

Download references

Author information

Authors and affiliations.

Faculty of Computational Mathematics and Cybernetics, Lomonosov Moscow State University, Moscow, Russian Federation

V. V. Morozov & S. I. Romanov

You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to V. V. Morozov .

Additional information

Translated from Prikladnaya Matematika i Informatika , No. 74, pp. 19–26, 2023

This article is a translation of the original article published in Russian in the journal Prikladnaya Matematika i Informatika . The translation was done with the help of an artificial intelligence machine translation tool, and subsequently reviewed and revised by an expert with knowledge of the field. Springer Nature works continuously to further the development of tools for the production of journals, books and on the related technologies to support the authors.

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Morozov, V.V., Romanov, S.I. The assignment problem as a cooperative game. Comput Math Model (2024). https://doi.org/10.1007/s10598-024-09600-0

Download citation

Received : 06 May 2023

Accepted : 12 October 2023

Published : 28 August 2024

DOI : https://doi.org/10.1007/s10598-024-09600-0

Share this article

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

Optimal assignment problem
Core of a cooperative game
Hungarian method
Directed multigraph
Find a journal
Publish with us
Track your research

SciPy v0.18.1 Reference Guide
Optimization and root finding ( scipy.optimize )

scipy.optimize.linear_sum_assignment ¶

Solve the linear sum assignment problem.

The linear sum assignment problem is also known as minimum weight matching in bipartite graphs. A problem instance is described by a matrix C, where each C[i,j] is the cost of matching vertex i of the first partite set (a “worker”) and vertex j of the second set (a “job”). The goal is to find a complete assignment of workers to jobs of minimal cost.

Formally, let X be a boolean matrix where $X[i,j] = 1$ iff row i is assigned to column j. Then the optimal assignment has cost

s.t. each row is assignment to at most one column, and each column to at most one row.

This function can also solve a generalization of the classic assignment problem where the cost matrix is rectangular. If it has more rows than columns, then not every row needs to be assigned to a column, and vice versa.

The method used is the Hungarian algorithm, also known as the Munkres or Kuhn-Munkres algorithm.

Parameters:	: array
Returns:	: array col_ind].sum(). The row indices will be sorted; in the case of a square cost matrix they will be equal to .

Parameters:

: array

Returns: