optimal solution of an assignment problem can be obtained

How to Solve the Assignment Problem: A Complete Guide

Table of Contents

Assignment problem is a special type of linear programming problem that deals with assigning a number of resources to an equal number of tasks in the most efficient way. The goal is to minimize the total cost of assignments while ensuring that each task is assigned to only one resource and each resource is assigned to only one task. In this blog, we will discuss the solution of the assignment problem using the Hungarian method, which is a popular algorithm for solving the problem.

Understanding the Assignment Problem

Before we dive into the solution, it is important to understand the problem itself. In the assignment problem, we have a matrix of costs, where each row represents a resource and each column represents a task. The objective is to assign each resource to a task in such a way that the total cost of assignments is minimized. However, there are certain constraints that need to be satisfied – each resource can be assigned to only one task and each task can be assigned to only one resource.

Solving the Assignment Problem

There are various methods for solving the assignment problem, including the Hungarian method, the brute force method, and the auction algorithm. Here, we will focus on the steps involved in solving the assignment problem using the Hungarian method, which is the most commonly used and efficient method.

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.

Step 2: Subtract the smallest element from each row and column

To simplify the calculations, we need to reduce the size of the cost matrix by subtracting the smallest element from each row and column. This step is called matrix reduction.

Step 3: Cover all zeros with the minimum number of lines

The next step is to cover all zeros in the matrix with the minimum number of horizontal and vertical lines. This step is called matrix covering.

Step 4: Test for optimality and adjust the matrix

To test for optimality, we need to calculate the minimum number of lines required to cover all zeros in the matrix. If the number of lines equals the number of rows or columns, the solution is optimal. If not, we need to adjust the matrix and repeat steps 3 and 4 until we get an optimal solution.

Step 5: Assign the tasks to the agents

The final step is to assign the tasks to the agents based on the optimal solution obtained in step 4. This will give us the most cost-effective or profit-maximizing assignment.

Solution of the Assignment Problem using the Hungarian Method

The Hungarian method is an algorithm that uses a step-by-step approach to find the optimal assignment. The algorithm consists of the following steps:

• Subtract the smallest entry in each row from all the entries of the row.
• Subtract the smallest entry in each column from all the entries of the column.
• Draw the minimum number of lines to cover all zeros in the matrix. If the number of lines drawn is equal to the number of rows, we have an optimal solution. If not, go to step 4.
• Determine the smallest entry not covered by any line. Subtract it from all uncovered entries and add it to all entries covered by two lines. Go to step 3.

The above steps are repeated until an optimal solution is obtained. The optimal solution will have all zeros covered by the minimum number of lines. The assignments can be made by selecting the rows and columns with a single zero in the final matrix.

Applications of the Assignment Problem

The assignment problem has various applications in different fields, including computer science, economics, logistics, and management. In this section, we will provide some examples of how the assignment problem is used in real-life situations.

Applications in Computer Science

The assignment problem can be used in computer science to allocate resources to different tasks, such as allocating memory to processes or assigning threads to processors.

Applications in Economics

The assignment problem can be used in economics to allocate resources to different agents, such as allocating workers to jobs or assigning projects to contractors.

Applications in Logistics

The assignment problem can be used in logistics to allocate resources to different activities, such as allocating vehicles to routes or assigning warehouses to customers.

Applications in Management

The assignment problem can be used in management to allocate resources to different projects, such as allocating employees to tasks or assigning budgets to departments.

Let’s consider the following scenario: a manager needs to assign three employees to three different tasks. Each employee has different skills, and each task requires specific skills. The manager wants to minimize the total time it takes to complete all the tasks. The skills and the time required for each task are given in the table below:

The assignment problem is to determine which employee should be assigned to which task to minimize the total time required. To solve this problem, we can use the Hungarian method, which we discussed in the previous blog.

Using the Hungarian method, we first subtract the smallest entry in each row from all the entries of the row:

Next, we subtract the smallest entry in each column from all the entries of the column:

We draw the minimum number of lines to cover all the zeros in the matrix, which in this case is three:

Since the number of lines is equal to the number of rows, we have an optimal solution. The assignments can be made by selecting the rows and columns with a single zero in the final matrix. In this case, the optimal assignments are:

• Emp 1 to Task 3
• Emp 2 to Task 2
• Emp 3 to Task 1

This assignment results in a total time of 9 units.

I hope this example helps you better understand the assignment problem and how to solve it using the Hungarian method.

Solving the assignment problem may seem daunting, but with the right approach, it can be a straightforward process. By following the steps outlined in this guide, you can confidently tackle any assignment problem that comes your way.

How useful was this post?

Click on a star to rate it!

Average rating 0 / 5. Vote count: 0

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

Exact solution approaches for bilevel assignment problems

• Published: 11 November 2015
• Volume 64 , pages 215–242, ( 2016 )

Cite this article

• Behdad Beheshti 1 ,
• Oleg A. Prokopyev 1 &
• Eduardo L. Pasiliao 2  

566 Accesses

11 Citations

Explore all metrics

We consider the bilevel assignment problem in which each decision maker (i.e., the leader and the follower) has its own objective function and controls a distinct set of edges in a given bipartite graph. The leader acts first by choosing some of its edges. Subsequently, the follower completes the assignment process. The edges selected by the leader and the follower are required to constitute a perfect matching. In this paper we propose an exact solution approach, which is based on a branch-and-bound framework and exploits structural properties of the assignment problem. Extensive computational experiments with linear sum and linear bottleneck objective functions are conducted to demonstrate the performance of the developed methods. While the considered problem is known to be NP -hard in general, we also describe some restricted cases that can be solved in polynomial time.

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

Exact Solution Methodologies for Linear and (Mixed) Integer Bilevel Programming

A class of algorithms for mixed-integer bilevel min–max optimization.

Exact solution approaches for a class of bilevel fractional programs

Aboudi, R., Jørnsten, K.: Resource constrained assignment problems. Discret. Appl. Math. 26 (2), 175–191 (1990)

Article   MathSciNet   MATH   Google Scholar  

Aiex, R.M., Resende, M.G.C., Pardalos, P.M., Toraldo, G.: GRASP with path relinking for three-index assignment. INFORMS J. Comput. 17 (2), 224–247 (2005)

Balinski, M.L., Gomory, R.E.: A primal method for the assignment and transportation problems. Manag. Sci. 10 (3), 578–593 (1964)

Article   Google Scholar  

Beheshti, B.: Test instances for the bilevel assignment problem. http://www.pitt.edu/droleg/files/BAP.html . Accessed April 6, 2014

Boros, E., Hammer, P.L.: Pseudo-boolean optimization. Discret. Appl. Math. 123 (1), 155–225 (2002)

Burkard, R., Dell’Amico, M., Martello, S.: Assignment Problems. Society for Industrial Mathematics, Philadelphia (2009)

Book   MATH   Google Scholar  

Chegireddy, C.R., Hamacher, H.W.: Algorithms for finding \(k\) -best perfect matchings. Discret. Appl. Math. 18 (2), 155–165 (1987)

Colson, B., Marcotte, P., Savard, G.: An overview of bilevel optimization. Ann. Oper. Res. 153 (1), 235–256 (2007)

Deng, X.: Complexity issues in bilevel linear programming. In: Migdalas, A., Pardalos, P.M., Varbrand, P. (eds.) Multilevel Optimization: Algorithms and Applications, pp. 149–164. Kluwer Academic Publishers, Dordrecht (1998)

Chapter   Google Scholar  

Fukuda, K., Matsui, T.: Finding all minimum-cost perfect matchings in bipartite graphs. Networks 22 (5), 461–468 (1992)

Garfinkel, R.S.: An improved algorithm for the bottleneck assignment problem. Oper. Res. 19 (7), 1747–1751 (1971)

Article   MATH   Google Scholar  

Gassner, E., Klinz, B.: The computational complexity of bilevel assignment problems. 4OR Q. J. Oper. Res. 7 (4), 379–394 (2009)

Glover, F.: Improved linear integer programming formulations of nonlinear integer problems. Manag. Sci. 22 (4), 455–460 (1975)

King, D.E.: Dlib-ml: a machine learning toolkit. J. Mach. Learn. Res. 10 , 1755–1758 (2009)

Google Scholar  

Krokhmal, P.A.: On optimality of a polynomial algorithm for random linear multidimensional assignment problem. Optim. Lett. 5 (1), 153–164 (2011)

Lieshout, P.M.D., Volgenant, A.: A branch-and-bound algorithm for the singly constrained assignment problem. Eur. J. Oper. Res. 176 (1), 151–164 (2007)

Liu, Y.H., Spencer, T.H.: Solving a bilevel linear program when the inner decision maker controls few variables. Eur. J. Oper. Res. 81 (3), 644–651 (1995)

Migdalas, A., Pardalos, P.M., Värbrand, P.: Multilevel Optimization: Algorithms and Applications, vol. 20. Springer, Berlin (1998)

Murty, K.G.: An algorithm for ranking all the assignments in order of increasing cost. Oper. Res. 16 (3), 682–687 (1968)

Pardalos, P.M., Pitsoulis, L.: Nonlinear Assignment Problems: Algorithms and Applications, vol. 7. Springer, Berlin (2000)

Pedersen, C.R., Relund Nielsen, L., Andersen, K.A.: An algorithm for ranking assignments using reoptimization. Comput. Oper. Res. 35 (11), 3714–3726 (2008)

Download references

Acknowledgments

The authors would like to thank the Associate Editor and the anonymous reviewers for their constructive comments that helped us to greatly improve the quality of the paper. This material is based upon work supported by the U.S. Air Force Research Laboratory (AFRL) Mathematical Modeling and Optimization Institute and the U.S. Air Force Office of Scientific Research (AFOSR). The research of the second author was also supported by the U.S. Air Force Summer Faculty Fellowship and by AFRL/RW under agreement number FA8651-12-2-0008. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of AFRL/RW or the U.S. Government.

Author information

Authors and affiliations.

Department of Industrial Engineering, University of Pittsburgh, 1048 Benedum Hall, Pittsburgh, PA, 15261, USA

Behdad Beheshti & Oleg A. Prokopyev

AFRL Munitions Directorate, Building 13, Eglin AFB, FL, 32542, USA

Eduardo L. Pasiliao

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Oleg A. Prokopyev .

Rights and permissions

Reprints and permissions

About this article

Beheshti, B., Prokopyev, O.A. & Pasiliao, E.L. Exact solution approaches for bilevel assignment problems. Comput Optim Appl 64 , 215–242 (2016). https://doi.org/10.1007/s10589-015-9799-4

Download citation

Received : 14 October 2014

Published : 11 November 2015

Issue Date : May 2016

DOI : https://doi.org/10.1007/s10589-015-9799-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

• Bilevel programming
• Assignment problem
• Combinatorial optimization
• Find a journal
• Publish with us
• Track your research

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:

Bibliographic and Citation Tools

Code, data and media associated with this article, recommenders and search tools.

• Institution

arXivLabs: experimental projects with community collaborators

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs .

• WolframAlpha.com
• WolframCloud.com
• All Sites & Public Resources...

• Wolfram|One
• Mathematica
• Wolfram|Alpha Notebook Edition
• Finance Platform
• System Modeler
• Wolfram Player
• Wolfram Engine
• WolframScript
• Enterprise Private Cloud
• Application Server
• Enterprise Mathematica
• Wolfram|Alpha Appliance
• Corporate Consulting
• Technical Consulting
• Wolfram|Alpha Business Solutions
• Data Repository
• Neural Net Repository
• Function Repository
• Wolfram|Alpha Pro
• Problem Generator
• Products for Education
• Wolfram Cloud App
• Wolfram|Alpha for Mobile
• Wolfram|Alpha-Powered Apps
• Paid Project Support
• Summer Programs
• All Products & Services »
• Wolfram Language Revolutionary knowledge-based programming language. Wolfram Cloud Central infrastructure for Wolfram's cloud products & services. Wolfram Science Technology-enabling science of the computational universe. Wolfram Notebooks The preeminent environment for any technical workflows. Wolfram Engine Software engine implementing the Wolfram Language. Wolfram Natural Language Understanding System Knowledge-based broadly deployed natural language. Wolfram Data Framework Semantic framework for real-world data. Wolfram Universal Deployment System Instant deployment across cloud, desktop, mobile, and more. Wolfram Knowledgebase Curated computable knowledge powering Wolfram|Alpha.
• All Technologies »
• Aerospace & Defense
• Chemical Engineering
• Control Systems
• Electrical Engineering
• Image Processing
• Industrial Engineering
• Mechanical Engineering
• Operations Research
• Actuarial Sciences
• Bioinformatics
• Data Science
• Econometrics
• Financial Risk Management
• All Solutions for Education
• Machine Learning
• Multiparadigm Data Science
• High-Performance Computing
• Quantum Computation Framework
• Software Development
• Authoring & Publishing
• Interface Development
• Web Development
• All Solutions »
• Wolfram Language Documentation
• Fast Introduction for Programmers
• Videos & Screencasts
• Wolfram Language Introductory Book
• Webinars & Training
• Support FAQ
• Wolfram Community
• Contact Support
• All Learning & Support »
• Company Background
• Wolfram Blog
• Careers at Wolfram
• Internships
• Other Wolfram Language Jobs
• Wolfram Foundation
• Computer-Based Math
• A New Kind of Science
• Wolfram Technology for Hackathons
• Student Ambassador Program
• Wolfram for Startups
• Demonstrations Project
• Wolfram Innovator Awards
• Wolfram + Raspberry Pi
• All Company »

Wolfram Language ™

Optimal assignment problem.

Find the amount of electricity a company must send from its four power plants to five cities so as to maximize profit and minimize cost while meeting the cities' peak demands.

This example demonstrates how LinearFractionalOptimization may be used to minimize the ratio of cost to profit within given constraints. Use of a matrix-valued variable makes the modeling relatively simple.

As an example, here is the cost of transporting one million kilowatt hours (kWh) of electricity from four plants to five cities.

The profit that each power plant generates by selling 1 million kWh to each city is shown here.

The cities have a peak demand of 45, 20, 30, 30 and 40 million kWh, respectively, and a minimum demand of 5 million kWh.

The power plants can supply a minimum of 35, 50, 40 and 40 million kWh of electricity, respectively.

The optimal amount of electricity to send each city by each plant can be found by minimizing the ratio of cost to profit.

The breakdown of electricity supplied is shown.

Related Examples

• Wolfram|Alpha Notebook Edition
• Mobile Apps
• Wolfram Workbench
• Volume & Site Licensing
• View all...
• For Customers
• Online Store
• Product Registration
• Product Downloads
• Service Plans Benefits
• User Portal
• Your Account
• Customer Service
• Get Started with Wolfram
• Fast Introduction for Math Students
• Public Resources
• Wolfram|Alpha
• Resource System
• Connected Devices Project
• Wolfram Data Drop
• Wolfram Science
• Computational Thinking
• About Wolfram
• Legal & Privacy Policy

An optimal solution of an assignment problem can be obtained only...

An optimal solution of an assignment problem can be obtained only if.

A. Each row & column has only one zero element

B. Each row & column has at least one zero element

C. The data is arrangement in a square matrix

D. None of the above

Answer: Option D

Solution(By Examveda Team)

This Question Belongs to Management >> Operations Research

Join The Discussion

Comments ( 1 ).

answer for this question is options. A

Related Questions on Operations Research

The use of decision models.

A. Is possible when the variables value is known

B. Reduces the scope of judgement & intuition known with certainty in decision-making

C. Require the use of computer software

Every mathematical model.

A. Must be deterministic

B. Requires computer aid for its solution

C. Represents data in numerical form

D. All of the above

A physical model is example of.

A. An iconic model

B. An analogue model

C. A verbal model

D. A mathematical model

The qualitative approach to decision analysis relies on.

A. Experience

B. Judgement

C. Intuition

More Related Questions on Operations Research

Read More: MCQ Type Questions and Answers

•   Arithmetic Ability
•   Competitive Reasoning
•   Competitive English
•   Data Interpretation
•   General Knowledge
•   State GK
•   History
•   Geography
•   Current Affairs
•   Banking Awareness
•   Computer Fundamentals
•   Networking
•   C Program
•   Java Program
•   Database
•   HTML
•   Javascript
•   Computer Science
•   Electronics and Communications Engineering
•   Electrical Engineering
•   Mechanical Engineering
•   Civil Engineering
•   Chemical Engineering
•   Automobile Engineering
•   Biotechnology Engineering
•   Mining Engineering
•   Commerce
•   Management
•   Philosophy
•   Agriculture
•   Sociology
•   Political Science
•   Pharmacy

The Application of Assignment Problem Optimal Solution Using Ones Assignment Method in The Curriculum Developer Team

Ieee account.

• Change Username/Password
• Update Address

Purchase Details

• Payment Options
• Order History
• View Purchased Documents

Profile Information

• Communications Preferences
• Profession and Education
• Technical Interests
• US & Canada: +1 800 678 4333
• Worldwide: +1 732 981 0060
• Contact & Support
• About IEEE Xplore
• Accessibility
• Terms of Use
• Nondiscrimination Policy
• Privacy & Opting Out of Cookies

A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity. © Copyright 2024 IEEE - All rights reserved. Use of this web site signifies your agreement to the terms and conditions.