## Assignment Problem: Meaning, Methods and Variations | Operations Research

After reading this article you will learn about:- 1. Meaning of Assignment Problem 2. Definition of Assignment Problem 3. Mathematical Formulation 4. Hungarian Method 5. Variations.

## Meaning of Assignment Problem:

An assignment problem is a particular case of transportation problem where the objective is to assign a number of resources to an equal number of activities so as to minimise total cost or maximize total profit of allocation.

The problem of assignment arises because available resources such as men, machines etc. have varying degrees of efficiency for performing different activities, therefore, cost, profit or loss of performing the different activities is different.

Thus, the problem is “How should the assignments be made so as to optimize the given objective”. Some of the problem where the assignment technique may be useful are assignment of workers to machines, salesman to different sales areas.

## Definition of Assignment Problem:

ADVERTISEMENTS:

Suppose there are n jobs to be performed and n persons are available for doing these jobs. Assume that each person can do each job at a term, though with varying degree of efficiency, let c ij be the cost if the i-th person is assigned to the j-th job. The problem is to find an assignment (which job should be assigned to which person one on-one basis) So that the total cost of performing all jobs is minimum, problem of this kind are known as assignment problem.

The assignment problem can be stated in the form of n x n cost matrix C real members as given in the following table:

www.springer.com The European Mathematical Society

• StatProb Collection
• Recent changes
• Current events
• Random page
• Project talk
• Request account
• What links here
• Related changes
• Special pages
• Printable version
• Permanent link
• Page information
• View source

## Assignment problem

The problem of optimally assigning $m$ individuals to $m$ jobs. It can be formulated as a linear programming problem that is a special case of the transport problem :

maximize $\sum _ {i,j } c _ {ij } x _ {ij }$

$$\sum _ { j } x _ {ij } = a _ {i} , i = 1 \dots m$$

(origins or supply),

$$\sum _ { i } x _ {ij } = b _ {j} , j = 1 \dots n$$

(destinations or demand), where $x _ {ij } \geq 0$ and $\sum a _ {i} = \sum b _ {j}$, which is called the balance condition. The assignment problem arises when $m = n$ and all $a _ {i}$ and $b _ {j}$ are $1$.

If all $a _ {i}$ and $b _ {j}$ in the transposed problem are integers, then there is an optimal solution for which all $x _ {ij }$ are integers (Dantzig's theorem on integral solutions of the transport problem).

In the assignment problem, for such a solution $x _ {ij }$ is either zero or one; $x _ {ij } = 1$ means that person $i$ is assigned to job $j$; the weight $c _ {ij }$ is the utility of person $i$ assigned to job $j$.

The special structure of the transport problem and the assignment problem makes it possible to use algorithms that are more efficient than the simplex method . Some of these use the Hungarian method (see, e.g., [a5] , [a1] , Chapt. 7), which is based on the König–Egervary theorem (see König theorem ), the method of potentials (see [a1] , [a2] ), the out-of-kilter algorithm (see, e.g., [a3] ) or the transportation simplex method.

In turn, the transportation problem is a special case of the network optimization problem.

A totally different assignment problem is the pole assignment problem in control theory.

• This page was last edited on 5 April 2020, at 18:48.
• Privacy policy
• About Encyclopedia of Mathematics
• Disclaimers
• Impressum-Legal

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

## Solving an Assignment Problem

This section presents an example that shows how to solve an assignment problem using both the MIP solver and the CP-SAT solver.

In the example there are five workers (numbered 0-4) and four tasks (numbered 0-3). Note that there is one more worker than in the example in the Overview .

The costs of assigning workers to tasks are shown in the following table.

The problem is to assign each worker to at most one task, with no two workers performing the same task, while minimizing the total cost. Since there are more workers than tasks, one worker will not be assigned a task.

## MIP solution

The following sections describe how to solve the problem using the MPSolver wrapper .

## Import the libraries

The following code imports the required libraries.

## Create the data

The following code creates the data for the problem.

The costs array corresponds to the table of costs for assigning workers to tasks, shown above.

## Declare the MIP solver

The following code declares the MIP solver.

## Create the variables

The following code creates binary integer variables for the problem.

## Create the constraints

Create the objective function.

The following code creates the objective function for the problem.

The value of the objective function is the total cost over all variables that are assigned the value 1 by the solver.

## Invoke the solver

The following code invokes the solver.

## Print the solution

The following code prints the solution to the problem.

Here is the output of the program.

## Complete programs

Here are the complete programs for the MIP solution.

## CP SAT solution

The following sections describe how to solve the problem using the CP-SAT solver.

## Declare the model

The following code declares the CP-SAT model.

The following code sets up the data for the problem.

The following code creates the constraints for the problem.

Here are the complete programs for the CP-SAT solution.

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 2023-01-02 UTC.

## 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).

(c) Highlight the rows that have assignments in indicated columns (if they haven’t previously 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.

## Leave a Comment Cancel reply

Your Mobile number and Email id will not be published. Required fields are marked *

Request OTP on Voice Call

Post My Comment

• Share Share

## Register with BYJU'S & Download Free PDFs

Register with byju's & watch live videos.

## Nash Balanced Assignment Problem

• Conference paper
• First Online: 21 November 2022
• Cite this conference paper

• Minh Hieu Nguyen 11 ,
• Mourad Baiou 11 &
• Viet Hung Nguyen 11

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13526))

Included in the following conference series:

• International Symposium on Combinatorial Optimization

353 Accesses

2 Citations

In this paper, we consider a variant of the classic Assignment Problem (AP), called the Balanced Assignment Problem (BAP) [ 2 ]. The BAP seeks to find an assignment solution which has the smallest value of max-min distance : the difference between the maximum assignment cost and the minimum one. However, by minimizing only the max-min distance, the total cost of the BAP solution is neglected and it may lead to an inefficient solution in terms of total cost. Hence, we propose a fair way based on Nash equilibrium [ 1 , 3 , 4 ] to inject the total cost into the objective function of the BAP for finding assignment solutions having a better trade-off between the two objectives: the first aims at minimizing the total cost and the second aims at minimizing the max-min distance. For this purpose, we introduce the concept of Nash Fairness (NF) solutions based on the definition of proportional-fair scheduling adapted in the context of the AP: a transfer of utilities between the total cost and the max-min distance is considered to be fair if the percentage increase in the total cost is smaller than the percentage decrease in the max-min distance and vice versa.

We first show the existence of a NF solution for the AP which is exactly the optimal solution minimizing the product of the total cost and the max-min distance. However, finding such a solution may be difficult as it requires to minimize a concave function. The main result of this paper is to show that finding all NF solutions can be done in polynomial time. For that, we propose a Newton-based iterative algorithm converging to NF solutions in polynomial time. It consists in optimizing a sequence of linear combinations of the two objective based on Weighted Sum Method [ 5 ]. Computational results on various instances of the AP are presented and commented.

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

## Access this chapter

• Available as PDF
• Read on any device
• Instant download
• Own it forever
• Available as EPUB and PDF
• Compact, lightweight edition
• Dispatched in 3 to 5 business days
• Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Bertsimas, D., Farias, V.F., Trichakis, N.: The price of fairness. Oper. Res. January–February 59 (1), 17–31 (2011)

MathSciNet   MATH   Google Scholar

Martello, S., Pulleyblank, W.R., Toth, P., De Werra, D.: Balanced optimization problems. Oper. Res. Lett. 3 (5), 275–278 (1984)

Article   MathSciNet   MATH   Google Scholar

Kelly, F.P., Maullo, A.K., Tan, D.K.H.: Rate control for communication networks: shadow prices, proportional fairness and stability. J. Oper. Res. Soc. 49 (3), 237–252 (1997). https://doi.org/10.1057/palgrave.jors.2600523

Article   Google Scholar

Ogryczak, W., Luss, H., Pioro, M., Nace, D., Tomaszewski, A.: Fair optimization and networks: a survey. J. Appl. Math. 2014 , 1–26 (2014)

Marler, R.T., Arora, J.S.: The weighted sum method for multi-objective optimization: new insights. Struct. Multi. Optim. 41 (6), 853–862 (2010)

Heller, I., Tompkins, C.B.: An extension of a theorem of Dantzig’s. Ann. Math. Stud. (38), 247–254 (1956)

Google Scholar

Kuhn, H.W.: The Hungarian method for assignment problem. Naval Res. Logist. Q. 2 (1–2), 83–97 (1955)

Martello, S.: Most and least uniform spanning trees. Discrete Appl. Math. 15 (2), 181–197 (1986)

Beasley, J.E.: Linear programming on Clay supercomputer. J. Oper. Res. Soc. 41 , 133–139 (1990)

Nguyen, M.H, Baiou, M., Nguyen, V.H., Vo, T.Q.T.: Nash fairness solutions for balanced TSP. In: International Network Optimization Conference (INOC2022) (2022)

Download references

## Author information

Authors and affiliations.

INP Clermont Auvergne, Univ Clermont Auvergne, Mines Saint-Etienne, CNRS, UMR 6158 LIMOS, 1 Rue de la Chebarde, Aubiere Cedex, France

Minh Hieu Nguyen, Mourad Baiou & Viet Hung Nguyen

You can also search for this author in PubMed   Google Scholar

## Corresponding author

Correspondence to Viet Hung Nguyen .

## Editor information

Editors and affiliations.

ESSEC Business School of Paris, Cergy Pontoise Cedex, France

Ivana Ljubić

IBM TJ Watson Research Center, Yorktown Heights, NY, USA

Francisco Barahona

Georgia Institute of Technology, Atlanta, GA, USA

Santanu S. Dey

Université Paris-Dauphine, Paris, France

A. Ridha Mahjoub

Proposition 1 . There may be more than one NF solution for the AP.

Let us illustrate this by an instance of the AP having the following cost matrix

By verifying all feasible assignment solutions in this instance, we obtain easily three assignment solutions $$(1-1, 2-2, 3-3), (1-2, 2-3, 3-1)$$ , $$(1-3, 2-2, 3-1)$$ and $$(1-3, 2-1, 3-2)$$ corresponding to 4 NF solutions (280, 36), (320, 32), (340, 30) and (364, 28). Note that $$i-j$$ where $$1 \le i,j \le 3$$ represents the assignment between worker i and job j in the solution of this instance.     $$\square$$

We recall below the proofs of some recent results that we have published in [ 10 ]. They are needed to prove the new results presented in this paper.

Theorem 2 [ 10 ] . $$(P^{*},Q^{*}) = {{\,\mathrm{arg\,min}\,}}_{(P,Q) \in \mathcal {S}} PQ$$ is a NF solution.

Obviously, there always exists a solution $$(P^{*},Q^{*}) \in \mathcal {S}$$ such that

Now $$\forall (P',Q') \in \mathcal {S}$$ we have $$P'Q' \ge P^{*}Q^{*}$$ . Then

The first inequality holds by the Cauchy-Schwarz inequality.

Hence, $$(P^{*},Q^{*})$$ is a NF solution.     $$\square$$

Theorem 3 [ 10 ] . $$(P^{*},Q^{*}) \in \mathcal {S}$$ is a NF solution if and only if $$(P^{*},Q^{*})$$ is an optimal solution of $$\mathcal {P(\alpha ^{*})}$$ where $$\alpha ^{*} = \frac{Q^{*}}{P^{*}}$$ .

Firstly, let $$(P^{*},Q^{*})$$ be a NF solution and $$\alpha ^{*} = \frac{Q^{*}}{P^{*}}$$ . We will show that $$(P^{*},Q^{*})$$ is an optimal solution of $$\mathcal {P(\alpha ^{*})}$$ .

Since $$(P^{*},Q^{*})$$ is a NF solution, we have

Since $$\alpha ^{*} = \frac{Q^{*}}{P^{*}}$$ , we have $$\alpha ^{*}P^{*}+Q^{*} = 2Q^{*}$$ .

Dividing two sides of ( 6 ) by $$P^{*} > 0$$ we obtain

So we deduce from ( 7 )

Hence, $$(P^{*},Q^{*})$$ is an optimal solution of $$\mathcal {P}(\alpha ^{*})$$ .

Now suppose $$\alpha ^{*} = \frac{Q^{*}}{P^{*}}$$ and $$(P^{*},Q^{*})$$ is an optimal solution of $$\mathcal {P}(\alpha ^{*})$$ , we show that $$(P^{*},Q^{*})$$ is a NF solution.

If $$(P^{*},Q^{*})$$ is not a NF solution, there exists a solution $$(P',Q') \in \mathcal {S}$$ such that

We have then

which contradicts the optimality of $$(P^{*},Q^{*})$$ .     $$\square$$

Lemma 3 [ 10 ] . Let $$\alpha , \alpha ' \in \mathbb {R}_+$$ and $$(P_{\alpha }, Q_{\alpha })$$ , $$(P_{\alpha '}, Q_{\alpha '})$$ be the optimal solutions of $$\mathcal {P(\alpha )}$$ and $$\mathcal {P(\alpha ')}$$ respectively, if $$\alpha \le \alpha '$$ then $$P_{\alpha } \ge P_{\alpha '}$$ and $$Q_{\alpha } \le Q_{\alpha '}$$ .

The optimality of $$(P_{\alpha }, Q_{\alpha })$$ and $$(P_{\alpha '}, Q_{\alpha '})$$ gives

By adding both sides of ( 8a ) and ( 8b ), we obtain $$(\alpha - \alpha ') (P_{\alpha } - P_{\alpha '}) \le 0$$ . Since $$\alpha \le \alpha '$$ , it follows that $$P_{\alpha } \ge P_{\alpha '}$$ .

On the other hand, inequality ( 8a ) implies $$Q_{\alpha '} - Q_{\alpha } \ge \alpha (P_{\alpha } - P_{\alpha '}) \ge 0$$ that leads to $$Q_{\alpha } \le Q_{\alpha '}$$ .     $$\square$$

Lemma 4 [ 10 ] . During the execution of Procedure Find ( $$\alpha _{0})$$ in Algorithm 1 , $$\alpha _{i} \in [0,1], \, \forall i \ge 1$$ . Moreover, if $$T_{0} \ge 0$$ then the sequence $$\{\alpha _i\}$$ is non-increasing and $$T_{i} \ge 0, \, \forall i \ge 0$$ . Otherwise, if $$T_{0} \le 0$$ then the sequence $$\{\alpha _i\}$$ is non-decreasing and $$T_{i} \le 0, \, \forall i \ge 0$$ .

Since $$P \ge Q \ge 0, \, \forall (P, Q) \in \mathcal {S}$$ , it follows that $$\alpha _{i+1} = \frac{Q_i}{P_i} \in [0,1], \, \forall i \ge 0$$ .

We first consider $$T_{0} \ge 0$$ . We proof $$\alpha _i \ge \alpha _{i+1}, \, \forall i \ge 0$$ by induction on i . For $$i = 0$$ , we have $$T_{0} = \alpha _{0} P_{0} - Q_{0} = P_{0}(\alpha _{0}-\alpha _{1}) \ge 0$$ , it follows that $$\alpha _{0} \ge \alpha _{1}$$ . Suppose that our hypothesis is true until $$i = k \ge 0$$ , we will prove that it is also true with $$i = k+1$$ .

Indeed, we have

The inductive hypothesis gives $$\alpha _k \ge \alpha _{k+1}$$ that implies $$P_{k+1} \ge P_k > 0$$ and $$Q_{k} \ge Q_{k+1} \ge 0$$ according to Lemma 3 . It leads to $$Q_{k}P_{k+1} - P_{k}Q_{k+1} \ge 0$$ and then $$\alpha _{k+1} - \alpha _{k+2} \ge 0$$ .

Hence, we have $$\alpha _{i} \ge \alpha _{i+1}, \, \forall i \ge 0$$ .

Consequently, $$T_{i} = \alpha _{i}P_{i} - Q_{i} = P_{i}(\alpha _{i}-\alpha _{i+1}) \ge 0, \, \forall i \ge 0$$ .

Similarly, if $$T_{0} \le 0$$ we obtain that the sequence $$\{\alpha _i\}$$ is non-decreasing and $$T_{i} \le 0, \, \forall i \ge 0$$ . That concludes the proof.     $$\square$$

Lemma 5 [ 10 ] . From each $$\alpha _{0} \in [0,1]$$ , Procedure Find $$(\alpha _{0})$$ converges to a coefficient $$\alpha _{k} \in \mathcal {C}_{0}$$ satisfying $$\alpha _{k}$$ is the unique element $$\in \mathcal {C}_{0}$$ between $$\alpha _{0}$$ and $$\alpha _{k}$$ .

As a consequence of Lemma 4 , Procedure $$\textit{Find}(\alpha _{0})$$ converges to a coefficient $$\alpha _{k} \in [0,1], \forall \alpha _{0} \in [0,1]$$ .

By the stopping criteria of Procedure Find $$(\alpha _{0})$$ , when $$T_{k} = \alpha _{k} P_{k} - Q_{k} = 0$$ we obtain $$\alpha _{k} \in C_{0}$$ and $$(P_{k},Q_{k})$$ is a NF solution. (Theorem 3 )

If $$T_{0} = 0$$ then obviously $$\alpha _{k} = \alpha _{0}$$ . We consider $$T_{0} > 0$$ and the sequence $$\{\alpha _i\}$$ is now non-negative, non-increasing. We will show that $$[\alpha _{k},\alpha _{0}] \cap \mathcal {C}_{0} = \alpha _{k}$$ .

Suppose that we have $$\alpha \in (\alpha _{k},\alpha _{0}]$$ and $$\alpha \in \mathcal {C}_{0}$$ corresponding to a NF solution ( P ,  Q ). Then there exists $$1 \le i \le k$$ such that $$\alpha \in (\alpha _{i}, \alpha _{i-1}]$$ . Since $$\alpha \le \alpha _{i-1}$$ , $$P \ge P_{i-1}$$ and $$Q \le Q_{i-1}$$ due to Lemma 3 . Thus, we get

By the definitions of $$\alpha$$ and $$\alpha _{i}$$ , inequality ( 9 ) is equivalent to $$\alpha \le \alpha _{i}$$ which leads to a contradiction.

By repeating the same argument for $$T_{0} < 0$$ , we also have a contradiction.     $$\square$$

## Rights and permissions

Reprints and permissions

## Copyright information

© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG

## About this paper

Cite this paper.

Nguyen, M.H., Baiou, M., Nguyen, V.H. (2022). Nash Balanced Assignment Problem. In: Ljubić, I., Barahona, F., Dey, S.S., Mahjoub, A.R. (eds) Combinatorial Optimization. ISCO 2022. Lecture Notes in Computer Science, vol 13526. Springer, Cham. https://doi.org/10.1007/978-3-031-18530-4_13

## Download citation

DOI : https://doi.org/10.1007/978-3-031-18530-4_13

Published : 21 November 2022

Publisher Name : Springer, Cham

Print ISBN : 978-3-031-18529-8

Online ISBN : 978-3-031-18530-4

eBook Packages : Computer Science Computer Science (R0)

## Share this paper

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

• Publish with us

Policies and ethics

• Find a journal
• Track your research

## Quantitative Techniques: Theory and Problems by P. C. Tulsian, Vishal Pandey

Get full access to Quantitative Techniques: Theory and Problems and 60K+ other titles, with a free 10-day trial of O'Reilly.

There are also live events, courses curated by job role, and more.

## UNBALANCED ASSIGNMENT PROBLEM

Unbalanced Assignment problem is an assignment problem where the number of facilities is not equal to the number of jobs. To make unbalanced assignment problem, a balanced one, a dummy facility(s) or a dummy job(s) (as the case may be) is introduced with zero cost or time.

Get Quantitative Techniques: Theory and Problems now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

## Don’t leave empty-handed

Get Mark Richards’s Software Architecture Patterns ebook to better understand how to design components—and how they should interact.

## Check it out now on O’Reilly

Dive in for free with a 10-day trial of the O’Reilly learning platform—then explore all the other resources our members count on to build skills and solve problems every day.

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

Related Topics

Privacy Policy , Terms and Conditions , DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.

## Unbalanced Assignment Problem: Definition, Formulation, and Solution Methods

Table of Contents

Are you familiar with the assignment problem in Operations Research (OR)? This problem deals with assigning tasks to workers in a way that minimizes the total cost or time needed to complete the tasks. But what if the number of tasks and workers is not equal? In this case, we face the Unbalanced Assignment Problem (UAP). This blog will help you understand what the UAP is, how to formulate it, and how to solve it.

## What is the Unbalanced Assignment Problem?

The Unbalanced Assignment Problem is an extension of the Assignment Problem in OR, where the number of tasks and workers is not equal. In the UAP, some tasks may remain unassigned, while some workers may not be assigned any task. The objective is still to minimize the total cost or time required to complete the assigned tasks, but the UAP has additional constraints that make it more complex than the traditional assignment problem.

## Formulation of the Unbalanced Assignment Problem

To formulate the UAP, we start with a matrix that represents the cost or time required to assign each task to each worker. If the matrix is square, we can use the Hungarian algorithm to solve the problem. But when the matrix is not square, we need to add dummy tasks or workers to balance the matrix. These dummy tasks or workers have zero costs and are used to make the matrix square.

Once we have a square matrix, we can apply the Hungarian algorithm to find the optimal assignment. However, we need to be careful in interpreting the results, as the assignment may include dummy tasks or workers that are not actually assigned to anything.

## Solutions for the Unbalanced Assignment Problem

Besides the Hungarian algorithm, there are other methods to solve the UAP, such as the transportation algorithm and the auction algorithm. The transportation algorithm is based on transforming the UAP into a transportation problem, which can be solved with the transportation simplex method. The auction algorithm is an iterative method that simulates a bidding process between the tasks and workers to find the optimal assignment.

In summary, the Unbalanced Assignment Problem is a variant of the traditional Assignment Problem in OR that deals with assigning tasks to workers when the number of tasks and workers is not equal. To solve the UAP, we need to balance the matrix by adding dummy tasks or workers and then apply algorithms such as the Hungarian algorithm, the transportation algorithm, or the auction algorithm. Understanding the UAP can help businesses and organizations optimize their resource allocation and improve their operational efficiency.

How useful was this post?

Click on a star to rate it!

Average rating 1 / 5. Vote count: 1

No votes so far! Be the first to rate this post.

We are sorry that this post was not useful for you! 😔

Let us improve this post!

Tell us how we can improve this post?

## Operations Research

1 Operations Research-An Overview

• History of O.R.
• Approach, Techniques and Tools
• Phases and Processes of O.R. Study
• Typical Applications of O.R
• Limitations of Operations Research
• Models in Operations Research
• O.R. in real world

2 Linear Programming: Formulation and Graphical Method

• General formulation of Linear Programming Problem
• Optimisation Models
• Basics of Graphic Method
• Important steps to draw graph
• Multiple, Unbounded Solution and Infeasible Problems
• Solving Linear Programming Graphically Using Computer
• Application of Linear Programming in Business and Industry

3 Linear Programming-Simplex Method

• Principle of Simplex Method
• Computational aspect of Simplex Method
• Simplex Method with several Decision Variables
• Two Phase and M-method
• Multiple Solution, Unbounded Solution and Infeasible Problem
• Sensitivity Analysis
• Dual Linear Programming Problem

4 Transportation Problem

• Basic Feasible Solution of a Transportation Problem
• Modified Distribution Method
• Stepping Stone Method
• Unbalanced Transportation Problem
• Degenerate Transportation Problem
• Transhipment Problem
• Maximisation in a Transportation Problem

5 Assignment Problem

• Solution of the Assignment Problem
• Unbalanced Assignment Problem
• Problem with some Infeasible Assignments
• Maximisation in an Assignment Problem
• Crew Assignment Problem

6 Application of Excel Solver to Solve LPP

• Building Excel model for solving LP: An Illustrative Example

7 Goal Programming

• Concepts of goal programming
• Goal programming model formulation
• Graphical method of goal programming
• The simplex method of goal programming
• Using Excel Solver to Solve Goal Programming Models
• Application areas of goal programming

8 Integer Programming

• Some Integer Programming Formulation Techniques
• Binary Representation of General Integer Variables
• Unimodularity
• Cutting Plane Method
• Branch and Bound Method
• Solver Solution

9 Dynamic Programming

• Dynamic Programming Methodology: An Example
• Definitions and Notations
• Dynamic Programming Applications

10 Non-Linear Programming

• Solution of a Non-linear Programming Problem
• Convex and Concave Functions
• Kuhn-Tucker Conditions for Constrained Optimisation
• Quadratic Programming
• Separable Programming
• NLP Models with Solver

11 Introduction to game theory and its Applications

• Important terms in Game Theory
• Saddle points
• Mixed strategies: Games without saddle points
• 2 x n games
• Exploiting an opponent’s mistakes

12 Monte Carlo Simulation

• Reasons for using simulation
• Monte Carlo simulation
• Limitations of simulation
• Steps in the simulation process
• Some practical applications of simulation
• Two typical examples of hand-computed simulation
• Computer simulation

13 Queueing Models

• Characteristics of a queueing model
• Notations and Symbols
• Statistical methods in queueing
• The M/M/I System
• The M/M/C System
• The M/Ek/I System
• Decision problems in queueing

#### IMAGES

1. Assignment Problem-Simple Balanced

2. How to Solve Balanced Assignment Problem Using Excel Solver #Excel #Solver #AssignementProblem

3. Assignment Problem (Part-1) Introduction/Formulation/Balanced/Unbalanced AP

4. Assignment Problem

5. Balanced Assignment Problem Using Excel Solver

6. Balanced Assignment Problem

#### VIDEO

1. Assignment Problem (Balanced)

2. Balanced Assignment problem|Hungarian method ||Operation Research ||

3. Assignment Problem-Simple Balanced

4. Assignment Problem ( Brute force method) Design and Analysis of Algorithm

5. Transportation Problem Least Cost Method

6. 2. Minimal Assignment problem {Hungarian Method}

#### COMMENTS

1. Assignment problem

The assignment problem consists of finding, in a weighted bipartite graph, a matching of a given size, in which the sum of weights of the edges is minimum. If the numbers of agents and tasks are equal, then the problem is called balanced assignment. Otherwise, it is called unbalanced assignment. [1] If the total cost of the assignment for all ...

2. Assignment Problem: Meaning, Methods and Variations

Variations of the Assignment Problems: Unbalanced Assignment Problem: Any assignment problem is said to be unbalanced if the cost matrix is not a square matrix, i.e. the no of rows and the no of columns are not equal. To make it balanced we add a dummy row or dummy column with all the entries is zero. Example 3:

3. Assignment Problem

Title: "Cracking the Balanced Assignment Problem in Operations Research!"🔍 Uncover the secrets of the Balanced Assignment Problem in this quick guide to Ope...

4. Nash Balanced Assignment Problem

The Balanced Assignment Problem (BAP) is a variant of the classic AP where instead of minimizing the total cost, we minimize the max-min distance which is the difference between the maximum assignment cost and the minimum one in the assignment solution. In [ 2 ], the authors proposed an efficient threshold-based algorithm to solve the BAP in ...

5. How to Solve the Assignment Problem: A Complete Guide

Step 1: Set up the cost matrix. The first step in solving the assignment problem is to set up the cost matrix, which represents the cost of assigning a task to an agent. The matrix should be square and have the same number of rows and columns as the number of tasks and agents, respectively.

6. Assignment problem

The assignment problem arises when $m = n$ and all $a _ {i}$ and $b _ {j}$ are $1$. If all $a _ {i}$ and $b _ {j}$ in the transposed problem are integers, then there is an optimal solution for which all $x _ {ij }$ are integers (Dantzig's theorem on integral solutions of the transport problem).

7. A Comparative Analysis of Assignment Problem

3.2 Balanced Assignment Problem. The "Balanced Assignment Problem" is one in which there is the same quantity of machines and jobs. The goal is to delegate tasks to machines in a manner that results in the lowest cost achievable, given that there are "n" jobs to complete on "m" machines (i.e., one job to one machine). Each machine ...

8. The assignment problem revisited

First, we give a detailed review of two algorithms that solve the minimization case of the assignment problem, the Bertsekas auction algorithm and the Goldberg & Kennedy algorithm. It was previously alluded that both algorithms are equivalent. We give a detailed proof that these algorithms are equivalent. Also, we perform experimental results comparing the performance of three algorithms for ...

9. Solving an Assignment Problem

The problem is to assign each worker to at most one task, with no two workers performing the same task, while minimizing the total cost. Since there are more workers than tasks, one worker will not be assigned a task. MIP solution. The following sections describe how to solve the problem using the MPSolver wrapper. Import the libraries

10. PDF Solving the Unbalanced Assignment Problem: Simpler Is Better

The typical textbook solution to the balanced assignment problem is then found using Kuhn's [3] Hungarian method. Problems in which there are more jobs than machines and more than one job can be ...

11. Solving the Unbalanced Assignment Problem: Simpler Is Better

The assignment problem (AP) is a well-known optimization problem that deals with the allocation of 'n' jobs to 'n' machines on a 1-to-1 basis. It minimizes the cost/time or maximizes the profit ...

12. Assignment Problems

6.4 Sum-k assignment problem .....195 6.5 Balanced assignment problem .....195 6.6 Lexicographic bottleneck assignment problem .....198 6.7 Inverse assignment problems .....202 7 Quadratic assignment problems: Formulations and bounds 205

13. 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.

14. Balanced Assignment Problem

Balanced Assignment Problem is an assignment problem where the number of facilities is equal to the number of jobs. Get Quantitative Techniques: Theory and Problems now with the O'Reilly learning platform. O'Reilly members experience books, live events, courses curated by job role, and more from O'Reilly and nearly 200 top publishers.

15. Nash balanced assignment problem

The Balanced Assignment Problem (BAP) is a variant of the classic AP where instead of minimizing the total cost, we minimize the max-min distance, which is the difference between the maximum assignment cost and the minimum one in the assignment solution.

16. PDF Nash Balanced Assignment Problem

Nash Balanced Assignment Problem. Abstract. In this paper, we consider a variant of the classic Assignment Problem (AP), called the Balanced Assignment Problem (BAP) [2]. The BAP seeks to find an assignment solution which has the smallest value of max-min distance: the difference between the maximum assignment cost and the minimum one. However ...

17. PDF ASSIGNMENT PROBLEM

An assignment problem is a particular case of transportation problem. The objective is to assign a number of resources to an equal number ... Solution: The given problem is balanced with 5 job and 5 machine. A = 2 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 4 9 22 58 11 19 43 78 72 50 63 41 28 91 37 45 74 42 27 49 39 36 11 57 22 25 3 7 7 7 7 7 7 7 7 7 7 7 7 ...

18. Assignment Problem

#assingmentproblem #minimization #balancedassingmentproblem

19. An Alternative Approach Assignment Problems for

Assignment Problems Abdur Rashid Department of Mathematics, Jahangirnagar University, Savar, Dhaka-1342, Bangladesh. Abstract This paper is devoted to present a new approach to make an unbalanced assignment problem into a balanced one and a comparison is carried out with the existing methods. The proposed approach is quite simple and

20. PDF UNIT 5 ASSIGNMENT PROBLEMS

Assignment Problems 7 Hungarian Method of Solving an Assignment Problem The steps for obtaining an optimal solution of an assignment problem are as follows: 1. Check whether the given matrix is square. If not, make it square by adding a suitable number of dummy rows (or columns) with 0 cost/time elements. 2.

21. Unbalanced Assignment Problem

Unbalanced Assignment problem is an assignment problem where the number of facilities is not equal to the number of jobs. To make unbalanced assignment problem, a balanced one, a dummy facility (s) or a dummy job (s) (as the case may be) is introduced with zero cost or time. Get Quantitative Techniques: Theory and Problems now with the O ...

22. Solution of assignment problems (Hungarian Method)

Solve the following assignment problem. Solution: 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.

23. Unbalanced Assignment Problem: Definition, Formulation, and Solution

The Unbalanced Assignment Problem is an extension of the Assignment Problem in OR, where the number of tasks and workers is not equal. In the UAP, some tasks may remain unassigned, while some workers may not be assigned any task. The objective is still to minimize the total cost or time required to complete the assigned tasks, but the UAP has ...