assignment problem minimize cost

for i = 1, 2, ..., n and j = 1, 2, ..., n

In the above table, c ij is the cost of performing jth job by ith worker.

Generalized Form of an Assignment Problem

The optimization model is

Minimize c 11 x 11 + c 12 x 12 + ------- + c nn x nn

subject to x i1 + x i2 +..........+ x in = 1          i = 1, 2,......., n x 1j + x 2j +..........+ x nj = 1          j = 1, 2,......., n

x ij = 0 or 1

In Σ Sigma notation

x ij = 0 or 1 for all i and j

An assignment problem can be solved by transportation methods, but due to high degree of degeneracy the usual computational techniques of a transportation problem become very inefficient. Therefore, a special method is available for solving such type of problems in a more efficient way.

Assumptions in Assignment Problem

• Number of jobs is equal to the number of machines or persons.
• Each man or machine is assigned only one job.
• Each man or machine is independently capable of handling any job to be done.
• Assigning criteria is clearly specified (minimizing cost or maximizing profit).

Share this article with your friends

Operations Research Simplified Back Next

Goal programming Linear programming Simplex Method Transportation Problem

Stack Exchange Network

Stack Exchange network consists of 183 Q&A communities including Stack Overflow , the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Q&A for work

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

Min max solution to the random assignment problem

Consider the standard assignment problem : $n$ people are assigned to $n$ jobs (one person to one job) so to minimize the sum of costs. When the costs are generated randomly (using the exponential (1) distribution), it is known that the expected sum of costs is $\pi^2/6$ .

An alternative solution to the assignment problem is to choose an allocation that instead minimizes the largest costs incurred by any individual, in the spirit of the John Rawls fairness criteria (see here ). Is it known any algorithm that finds such maximin allocation, and is it known what is the random sum of costs in the random version of the problem?

Many thanks,

• assignment-problem

Yes, there is an efficient algorithm to find an assignment that minimizes the largest cost. Suppose we want to check whether there is an assignment with largest cost $t$ . To do that, delete all edges with cost larger than $t$ , ignore the costs, and check whether the graph has a bipartite matching using the Hopcroft-Karp algorithm; if it does, there is a valid assignment. Now use binary search over $t$ until you find the minimum $t$ such that a valid assignment exists. Thus, the problem can be solved $O(|E| \sqrt{|V|} \lg |E|)$ time.

• $\begingroup$ Thank you. I have asked the second question here cs.stackexchange.com/questions/140571/… , I would appreciate any comments on it $\endgroup$ –  fox May 21, 2021 at 9:55
• $\begingroup$ Are you familiar with any paper that implements such an algorithm or studies this problem? $\endgroup$ –  fox May 21, 2021 at 9:56

Your Answer

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 assignment-problem or ask your own question .

Hot network questions.

• What legal reason, if any, does my bank have to know if I am a dual citizen of the US?
• LilyPond: tuplet bars don't seem to match time used
• Can campaign promises be enforced by a contract, or has it ever happened they were?
• Visual Studio Code crashes with [...ERROR:process_memory_range.cc(75)] read out of range
• VS Code not launching after incorrect command execution on Ubuntu 22.04
• How can I obtain a record of my fathers' medals from WW2?
• A man is kidnapped by his future descendants and isolated his whole life to prevent a bad thing; they accidentally undo their own births
• Estimating Probability Density for Sample
• Leaders and Rulers
• Accelerating Expansion of Universe - Why Not Caused by Radiation?
• How to underline several empty lines
• What is every charm combo in Hollow Knight?
• Find the number of cycles of length 3
• Why does SQL-Server Management Studio change "Execute Query" into "Save Results"?
• Are there any jobs that are forbidden by law to convicted felons?
• Filter by partition number when the table is partitioned by computed column
• Prove that "max independent set is larger than max clique" is NP-Hard
• How much extra did a color RF modulator cost?
• incorrect signature: void getDescribe() from the type Schema.DescribeFieldResult
• Python matrix class
• How to align vertically by "\shortstack" in equation in LaTeX?
• Romans 3:22 – ‘of’ or ‘in’? Old translations differ from modern ones. Why?
• Bringing homemade sweet bread into Australia
• Is it legal to deposit a check that says pay to the order of cash

The assignment problem revisited

• Original Paper
• Published: 16 August 2021
• Volume 16 , pages 1531–1548, ( 2022 )

Cite this article

• Carlos A. Alfaro   ORCID: orcid.org/0000-0001-9783-8587 1 ,
• Sergio L. Perez 2 ,
• Carlos E. Valencia 3 &
• Marcos C. Vargas 1  

1014 Accesses

4 Citations

4 Altmetric

Explore all metrics

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 the assignment problem: the \(\epsilon \) - scaling auction algorithm , the Hungarian algorithm and the FlowAssign algorithm . The experiment shows that the auction algorithm still performs and scales better in practice than the other algorithms which are harder to implement and have better theoretical time complexity.

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

Access this article

Price includes VAT (Russian Federation)

Instant access to the full article PDF.

Rent this article via DeepDyve

Institutional subscriptions

Similar content being viewed by others

Some results on an assignment problem variant

Integer Programming

A Full Description of Polytopes Related to the Index of the Lowest Nonzero Row of an Assignment Matrix

Bertsekas, D.P.: The auction algorithm: a distributed relaxation method for the assignment problem. Annal Op. Res. 14 , 105–123 (1988)

Article   MathSciNet   Google Scholar  

Bertsekas, D.P., Castañon, D.A.: Parallel synchronous and asynchronous implementations of the auction algorithm. Parallel Comput. 17 , 707–732 (1991)

Article   Google Scholar  

Bertsekas, D.P.: Linear network optimization: algorithms and codes. MIT Press, Cambridge, MA (1991)

MATH   Google Scholar  

Bertsekas, D.P.: The auction algorithm for shortest paths. SIAM J. Optim. 1 , 425–477 (1991)

Bertsekas, D.P.: Auction algorithms for network flow problems: a tutorial introduction. Comput. Optim. Appl. 1 , 7–66 (1992)

Bertsekas, D.P., Castañon, D.A., Tsaknakis, H.: Reverse auction and the solution of inequality constrained assignment problems. SIAM J. Optim. 3 , 268–299 (1993)

Bertsekas, D.P., Eckstein, J.: Dual coordinate step methods for linear network flow problems. Math. Progr., Ser. B 42 , 203–243 (1988)

Bertsimas, D., Tsitsiklis, J.N.: Introduction to linear optimization. Athena Scientific, Belmont, MA (1997)

Google Scholar  

Burkard, R., Dell’Amico, M., Martello, S.: Assignment Problems. Revised reprint. SIAM, Philadelphia, PA (2011)

Gabow, H.N., Tarjan, R.E.: Faster scaling algorithms for network problems. SIAM J. Comput. 18 (5), 1013–1036 (1989)

Goldberg, A.V., Tarjan, R.E.: A new approach to the maximum flow problem. J. Assoc. Comput. Mach. 35 , 921–940 (1988)

Goldberg, A.V., Tarjan, R.E.: Finding minimum-cost circulations by successive approximation. Math. Op. Res. 15 , 430–466 (1990)

Goldberg, A.V., Kennedy, R.: An efficient cost scaling algorithm for the assignment problem. Math. Programm. 71 , 153–177 (1995)

MathSciNet   MATH   Google Scholar  

Goldberg, A.V., Kennedy, R.: Global price updates help. SIAM J. Discr. Math. 10 (4), 551–572 (1997)

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

Kuhn, H.W.: Variants of the Hungarian method for the assignment problem. Naval Res. Logist. Quart. 2 , 253–258 (1956)

Lawler, E.L.: Combinatorial optimization: networks and matroids, Holt. Rinehart & Winston, New York (1976)

Orlin, J.B., Ahuja, R.K.: New scaling algorithms for the assignment ad minimum mean cycle problems. Math. Programm. 54 , 41–56 (1992)

Ramshaw, L., Tarjan, R.E., Weight-Scaling Algorithm, A., for Min-Cost Imperfect Matchings in Bipartite Graphs, : IEEE 53rd Annual Symposium on Foundations of Computer Science. New Brunswick, NJ 2012 , 581–590 (2012)

Zaki, H.: A comparison of two algorithms for the assignment problem. Comput. Optim. Appl. 4 , 23–45 (1995)

Download references

Acknowledgements

This research was partially supported by SNI and CONACyT.

Author information

Authors and affiliations.

Banco de México, Mexico City, Mexico

Carlos A. Alfaro & Marcos C. Vargas

Mountain View, CA, 94043, USA

Sergio L. Perez

Departamento de Matemáticas, CINVESTAV del IPN, Apartado postal 14-740, 07000, Mexico City, Mexico

Carlos E. Valencia

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Carlos A. Alfaro .

Ethics declarations

Conflict of interest.

There is no conflict of interest.

Additional information

Publisher's note.

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

The authors were partially supported by SNI and CONACyT.

Rights and permissions

Reprints and permissions

About this article

Alfaro, C.A., Perez, S.L., Valencia, C.E. et al. The assignment problem revisited. Optim Lett 16 , 1531–1548 (2022). https://doi.org/10.1007/s11590-021-01791-4

Download citation

Received : 26 March 2020

Accepted : 03 August 2021

Published : 16 August 2021

Issue Date : June 2022

DOI : https://doi.org/10.1007/s11590-021-01791-4

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

• Assignment problem
• Bertsekas auction algorithm
• Combinatorial optimization and matching
• Find a journal
• Publish with us
• Track your research

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 / 5. Vote count: 2

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

• Stack Overflow Public questions & answers
• Stack Overflow for Teams Where developers & technologists share private knowledge with coworkers
• Talent Build your employer brand
• Advertising Reach developers & technologists worldwide
• Labs The future of collective knowledge sharing
• About the company

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.

Minimizing maximum cost in an one-to-one assignment problem

I want to compute a one-to-one assignment, from A to B where A and B have n elements. Each element of A will be assigned to one element in B. There is an associated cost between each element of A and B. The goal is to minimize the maximum cost of the assignment.

How to compute such an assignment using the cost matrix? I need to select an element from each row/column such that minimax strategy is achieved.

I was able to achieve this by listing all possible assignments and calculating their maximum costs and then selecting the one with the least maximum cost, but I wonder if there's a better approach.

• optimization
• game-theory

• You're looking for a "minimum cost matching in a complete balanced bipartite graph" -- searching using these terms should give you good results. bipartite means you have 2 sets of vertices with edges between them. Balanced means these sets are the same size. Complete means that all edges between the two sets are present. A matching is a set of edges s.t. each vertex is on at most one edge. –  Dave Dec 15, 2022 at 16:44
• homes.di.unimi.it/righini/Didattica/OttimizzazioneCombinatoria/… –  Dave Dec 15, 2022 at 20:35

2 Answers 2

The easiest is probably as a MIP (Mixed-Integer Programming) model:

This can be solved with any MIP solver.

A brute force polynomial cost algorithm based on repeated application of max matching in bipartite graph:

Order the pairs by assignment cost. Take n cheapest pairs. This determines a bipartite graph with A and B as vertices (pairs are edges). Try to find a matching in this graph. If found, it determines the optimal one-to-one assignment.

If not found, add the next pair. Repeat until a matching is found.

I suspect this can be optimized by not running the matching algorithm from the start every time you add an edge but rather keeping the maximum matching and checking if it can be augmented with the newly added edge.

• If you squint, this is sort of what the Hungarian algorithm is doing, but the extra complexity in manipulating the dual solution is what makes it correct. –  David Eisenstat Dec 16, 2022 at 14:44

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 algorithm optimization game-theory or ask your own question .

• The Overflow Blog
• Introducing Staging Ground: The private space to get feedback on questions...
• How to prevent your new chatbot from giving away company secrets
• Featured on Meta
• The [tax] tag is being burninated
• The return of Staging Ground to Stack Overflow
• The 2024 Developer Survey Is Live
• Policy: Generative AI (e.g., ChatGPT) is banned

Hot Network Questions

• incorrect signature: void getDescribe() from the type Schema.DescribeFieldResult
• Can campaign promises be enforced by a contract, or has it ever happened they were?
• Find the number of cycles of length 3
• How are neutrinos able to cause a supernova explosion?
• Are there any jobs that are forbidden by law to convicted felons?
• Filter by partition number when the table is partitioned by computed column
• Who are the mathematicians interested in the history of mathematics?
• Problem with cline being to short
• When I move the bones and they bend, they can't bend where they can do it clearly
• is it correct to say "push the table by its far edge"?
• Bringing homemade sweet bread into Australia
• A trigonometric equation: how hard could it be?
• Is bike tyre pressure info deliberately hard to read?
• Short story about a neurodivergent child who becomes a pilot
• Nagel line of a tetrahedron?
• Which ability checks are rolled for a shove attack?
• Tools like leanblueprint for other proof assistants, especially Coq?
• Accelerating Expansion of Universe - Why Not Caused by Radiation?
• What can I plant to retain a steep slope?
• are "I will check your homework later" and "I will check on your homework later" similar?
• Accumulated charge in conductors
• VS Code not launching after incorrect command execution on Ubuntu 22.04
• Visual Studio Code crashes with [...ERROR:process_memory_range.cc(75)] read out of range
• How did ALT + F4 become the shortcut for closing?

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

One of the most well-known combinatorial optimization problems is the assignment problem . Here's an example: suppose a group of workers needs to perform a set of tasks, and for each worker and task, there is a cost for assigning the worker to the task. 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.

You can visualize this problem by the graph below, in which there are four workers and four tasks. The edges represent all possible ways to assign workers to tasks. The labels on the edges are the costs of assigning workers to tasks.

An assignment corresponds to a subset of the edges, in which each worker has at most one edge leading out, and no two workers have edges leading to the same task. One possible assignment is shown below.

The total cost of the assignment is 70 + 55 + 95 + 45 = 265 .

The next section shows how solve an assignment problem, using both the MIP solver and the CP-SAT solver.

Other tools for solving assignment problems

OR-Tools also provides a couple of other tools for solving assignment problems, which can be faster than the MIP or CP solvers:

• Linear sum assignment solver
• Minimum cost flow solver

However, these tools can only solve simple types of assignment problems. So for general solvers that can handle a wide variety of problems (and are fast enough for most applications), we recommend the MIP and CP-SAT solvers.

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.