the assignment problem has alternative solution if

• Math Article

Alternate Optima

We know that an optimal solution is a solution to a linear programming problem that satisfies the set of constraints of the problem (either maximization or minimization problem) and the corresponding objective function. An alternate optima arises when an LPP (linear programming problem) or integer programming problem contains more than one optimal solution. Also, an alternate optima is called an alternate optimal solution.

Learn: Linear programming problem

Alternate Optimal Solution in Graphical Method

Consider a graphical analysis of a problem (see figure) given with a set of constraints and an objective function of maximization. As we know, the optimal solution set is a smaller set within the feasible region. The below graph represents the feasible region obtained from three constraints of a linear programming problem.

In the above graph, the objective function is parallel to the line segment rs. Thus, all the rs points (x 1 , x 2 ) provide maximum yield. That means there is an alternate optimal solution.

Alternate Optimal Solution in LPP

In LPP (linear programming problem), an alternate optimal solution or alternative optimal solution occurs when the given problem has more than one solution, which means when the objective function is similar to a nonredundant critical constraint . Here, the critical constraint is the constraint that is satisfied as an equation at the optimal solution. Also, the objective function can take the same optimal value for more than one solution point, thus providing us with alternative optima.

Alternate Optimal Solution in Simplex Method

Let us consider an example problem that contains infinite solutions and is solved using the simplex method. It also illustrates the practical consequence of identifying such solutions.

Find the solution of the problem given below using the simplex method (big M method)

Max Z = 2x 1 + 4x 2

x 1 + 2x 2 ≤ 5

x 1 + x 2 ≤ 4

and x 1 , x 2 ≥ 0.

Given LPP is:

and x 1 , x 2 ≥ 0

The given problem can be converted into canonical form by adding suitable slack variables, surplus variables and artificial variables.

The first and second constraints are of type ‘≤’, in the given problem, so we should add slack variables S 1 and S 2 , respectively.

Thus, we get the modified problem as:

Max Z = 2x 1 + 4x 2 + 0.S 1 + 0.S 2

x 1 + 2x 2 + S 1 = 5

x 1 + x 2 + S 2 = 4

and x 1 , x 2 , S 1 , S 2 ≥ 0

Let’s make the table for iteration 1.

The negative minimum of Z j – C j is -4, and its column index is 2. Thus, the entering variable is x 2 .

The minimum ratio is 2.5, and its row index is 1.

That means S 1 is the remaining basic variable.

∴ The pivot element (key element) is 2.

Now, perform the following operations on rows.

R 1 → R 1 /2

R 2 → R 2 – new R 1

Here, all Z j – C j ≥ 0

Hence, the optimal solution has arrived with value of variables as :

x 1 = 0, x 2 = 5/2

Max Z = 2(0) + 4(5/2) = 10

Also, in the above iteration table, we have Z 1 – C 1 = 0 and x 1 is not in the basis (i.e. x 1 = 0).

This implies that there is more than 1 optimal solution to the problem.

Therefore, we may get another alternative optimal solution by entering the variable x 1 into the basis.

Here, the entering variable is x 1 .

The minimum ratio is 3, and its row index is 2. That means S 2 is the remaining basis variable.

Also, the pivot or key element is 12.

Now, R 2 → R 2 × 2

R 1 → R 1 – (½) new R 2

Hence, the optimal solution has arrived with the value of variables as:

x 1 = 3, x 2 = 1

Max Z = 2(3) + 4(1) = 6 + 4 10

Frequently Asked Questions on Alternate Optima

What is an alternative optima in the simplex method.

In the simplex method, an alternative optima arises when all z i – c i are greater than or equal to 0, and one of the variables cannot be the basis variable in interaction tables.

How do you determine if an LPP has an alternative optimal solution?

When the given LPP (linear programming problem) contains more than one optimal solution, then we can say that there exists an alternative optimal solution.

Can we have multiple optimal solutions for an LPP?

Yes, a linear programming problem (LPP) can have multiple optimal solutions, i.e. more than one or infinite solutions.

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

Register with BYJU'S & Download Free PDFs

Register with byju's & watch live videos.

Algorithms: The Assignment Problem

One of the interesting things about studying optimization is that the techniques show up in a lot of different areas. The “assignment problem” is one that can be solved using simple techniques, at least for small problem sizes, and is easy to see how it could be applied to the real world.

Assignment Problem

Pretend for a moment that you are writing software for a famous ride sharing application. In a crowded environment, you might have multiple prospective customers that are requesting service at the same time, and nearby you have multiple drivers that can take them where they need to go. You want to assign the drivers to the customers in a way that minimizes customer wait time (so you keep the customers happy) and driver empty time (so you keep the drivers happy).

The assignment problem is designed for exactly this purpose. We start with m agents and n tasks. We make the rule that every agent has to be assigned to a task. For each agent-task pair, we figure out a cost associated to have that agent perform that task. We then figure out which assignment of agents to tasks minimizes the total cost.

Of course, it may be true that m != n , but that’s OK. If there are too many tasks, we can make up a “dummy” agent that is more expensive than any of the others. This will ensure that the least desirable task will be left to the dummy agent, and we can remove that from the solution. Or, if there are too many agents, we can make up a “dummy” task that is free for any agent. This will ensure that the agent with the highest true cost will get the dummy task, and will be idle.

If that last paragraph was a little dense, don’t worry; there’s an example coming that will help show how it works.

There are special algorithms for solving assignment problems, but one thing that’s nice about them is that a general-purpose solver can handle them too. Below is an example, but first it will help to cover a few concepts that we’ll be using.

Optimization Problems

Up above, we talked about making “rules” and minimizing costs. The usual name for this is optimization. An optimization problem is one where we have an “objective function” (which tells us what our goals are) and one or more “constraint functions” (which tell us what the rules are). The classic example is a factory that can make both “widgets” and “gadgets”. Each “widget” and “gadget” earns a certain amount of profit, but it also uses up raw material and time on the factory’s machines. The optimization problem is to determine exactly how many “widgets” and how many “gadgets” to make to maximize profit (the objective) while fitting within the material and time available (the constraints).

If we were to write this simple optimization problem out, it might look like this:

In this case, we have two variables: g for the number of gadgets we make and w for the number of widgets we make. We also have three constraints that we have to meet. Note that they are inequalities; we might not use all the available material or time in our optimal solution.

Just to unpack this a little: in English, the above is saying that we make 45 dollars / euros / quatloos per gadget we make. However, to make a gadget needs 120 lbs of raw material 1, 80 lbs of raw material 2, and 3.8 hours of machine time. So there is a limit on how many gadgets we can make, and it might be a better use of resources to balance gadgets with widgets.

Of course, real optimization problems have many more than two variables and many constraint functions, making them much harder to solve. The easiest kind of optimization problem to solve is linear, and fortunately, the assignment problem is linear.

Linear Programming

A linear program is a kind of optimization problem where both the objective function and the constraint functions are linear. (OK, that definition was a little self-referential.) We can have as many variables as we want, and as many constraint functions as we want, but none of the variables can have exponents in any of the functions. This limitation allows us to apply very efficient mathematical approaches to solve the problem, even for very large problems.

We can state the assignment problem as a linear programming problem. First, we choose to make “i” represent each of our agents (drivers) and “j” to represent each of our tasks (customers). Now, to write a problem like this, we need variables. The best approach is to use “indicator” variables, where xij = 1 means “driver i picks up customer j” and xij = 0 means “driver i does not pick up customer j”.

We wind up with:

This is a compact mathematical way to describe the problem, so again let me put it in English.

First, we need to figure out the cost of having each driver pick up each customer. Then, we can calculate the total cost for any scenario by just adding up the costs for the assignments we pick. For any assignment we don’t pick, xij will equal zero, so that term will just drop out of the sum.

Of course, the way we set up the objective function, the cheapest solution is for no drivers to pick up any customers. That’s not a very good business model. So we need a constraint to show that we want to have a driver assigned to every customer. At the same time, we can’t have a driver assigned to mutiple customers. So we need a constraint for that too. That leads us to the two constraints in the problem. The first just says, if you add up all the assignments for a given driver, you want the total number of assignments for that driver to be exactly one. The second constraint says, if you add up all the assignments to a given customer, you want the total number of drivers assigned to the customer to be one. If you have both of these, then each driver is assigned to exactly one customer, and the customers and drivers are happy. If you do it in a way that minimizes costs, then the business is happy too.

Solving with Octave and GLPK

The GNU Linear Programming Kit is a library that solves exactly these kinds of problems. It’s easy to set up the objective and constraints using GNU Octave and pass these over to GLPK for a solution.

Given some made-up sample data, the program looks like this:

Start with the definition of “c”, the cost information. For this example, I chose to have four drivers and three customers. There are sixteen numbers there; the first four are the cost of each driver to get the first customer, the next four are for the second customer, and the next four are for the third customer. Because we have an extra driver, we add a “dummy” customer at the end that is zero cost. This represents one of the drivers being idle.

The next definition is “b”, the right-hand side of our constraints. There are eight constraints, one for each of the drivers, and one for each of the customers (including the dummy). For each constraint, the right-hand side is 1.

The big block in the middle defines our constraint matrix “a”. This is the most challenging part of taking the mathematical definition and putting it into a form that is usable by GLPK; we have to expand out each constraint. Fortunately, in these kinds of cases, we tend to get pretty patterns that help us know we’re on the right track.

The first line in “a” says that the first customer needs a driver. To see why, remember that in our cost information, the first four numbers are the cost for each driver to get the first customer. With this constraint, we are requiring that one of those four costs be included and therefore that a driver is “selected” for the first customer. The other lines in “a” work similarly; the last four ensure that each driver has an assignment.

Note that the number of rows in “a” matches the number of items in “b”, and the number of columns in “a” matches the number of items in “c”. This is important; GLPK won’t run if this is not true (and our problem isn’t stated right in any case).

Compared to the above, the last few lines are easy.

• “lb” gives the lower bound for each variable.
• “ub” gives the upper bound.
• “ctype” tells GLPK that each constraint is an equality (“strict” as opposed to providing a lower or upper bound).
• “vartype” tells GLPK that these variables are all integers (can’t have half a driver showing up).
• “s” tells GLPK that we want to minimize our costs, not maximize them.

We push all that through a function call to GLPK, and what comes back are two values (along with some other stuff I’ll exclude for clarity):

The first item tells us that our best solution takes 27 minutes, or dollars, or whatever unit we used for cost. The second item tells us the assignments we got. (Note for pedants: I transposed this output to save space.)

This output tells us that customer 1 gets driver 2, customer 2 gets driver 3, customer 3 gets driver 4, and driver 1 is idle. If you look back at the cost data, you can see this makes sense, because driver 1 had some of the most expensive times to the three customers. You can also see that it managed to pick the least expensive pairing for each customer. (Of course, if I had done a better job making up cost data, it might not have picked the least expensive pairing in all cases, because a suboptimal individual pairing might still lead to an overall optimal solution. But this is a toy example.)

Of course, for a real application, we would have to take into consideration many other factors, such as the passage of time. Rather than knowing all of our customers and drivers up front, we would have customers and drivers continually showing up and being assigned. But I hope this simple example has revealed some of the concepts behind optimization and linear programming and the kinds of real-world problems that can be solved.

• DSA Tutorial
• Data Structures
• Linked List
• Dynamic Programming
• Binary Tree
• Binary Search Tree
• Divide & Conquer
• Mathematical
• Backtracking
• Branch and Bound
• Pattern Searching

Hungarian Algorithm for Assignment Problem | Set 1 (Introduction)

• For each row of the matrix, find the smallest element and subtract it from every element in its row.
• Do the same (as step 1) for all columns.
• Cover all zeros in the matrix using minimum number of horizontal and vertical lines.
• Test for Optimality: If the minimum number of covering lines is n, an optimal assignment is possible and we are finished. Else if lines are lesser than n, we haven’t found the optimal assignment, and must proceed to step 5.
• Determine the smallest entry not covered by any line. Subtract this entry from each uncovered row, and then add it to each covered column. Return to step 3.

Try it before moving to see the solution

Explanation for above simple example:

  An example that doesn’t lead to optimal value in first attempt: In the above example, the first check for optimality did give us solution. What if we the number covering lines is less than n.

Time complexity : O(n^3), where n is the number of workers and jobs. This is because the algorithm implements the Hungarian algorithm, which is known to have a time complexity of O(n^3).

Space complexity :   O(n^2), where n is the number of workers and jobs. This is because the algorithm uses a 2D cost matrix of size n x n to store the costs of assigning each worker to a job, and additional arrays of size n to store the labels, matches, and auxiliary information needed for the algorithm.

In the next post, we will be discussing implementation of the above algorithm. The implementation requires more steps as we need to find minimum number of lines to cover all 0’s using a program. References: http://www.math.harvard.edu/archive/20_spring_05/handouts/assignment_overheads.pdf https://www.youtube.com/watch?v=dQDZNHwuuOY

Please Login to comment...

Similar reads, improve your coding skills with practice.

What kind of Experience do you want to share?

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

385 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

Subscribe and save.

• Get 10 units per month
• Download Article/Chapter or eBook
• 1 Unit = 1 Article or 1 Chapter
• Cancel anytime
• 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

Similar content being viewed by others

The fair owa one-to-one assignment problem: np-hardness and polynomial time special cases.

An Efficient Primal-Dual Algorithm for Fair Combinatorial Optimization Problems

Restricted Max-Min Allocation: Integrality Gap and Approximation Algorithm

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

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.

Assignment problem or something else?

My primary goal with this question is to identify the type of problem I have so I know what solution to pursue. I think it's either an instance of the assignment problem or the fair item allocation problem, though I can also envision a solution that involves a variation on the stable marriage problem .

The question:

Is there an existing definition of the assignment problem where the solution is not to get as many people as possible their #1 option, but to get the group as a whole the highest preference level of assignments? In other words, the important thing is not that "as many agents as possible get their highest preference." An agent will sacrifice a higher preference for a slightly lower one if it means that another agent will move up to a higher preference.

Example: Alice would not swap her 1st preference for her 8th so that Bob can get from his 7th to his 6th. But Alice would swap her 1st for her 3rd if it means Bob gets from his 8th to his 4th.

Obviously, there's a lot of subjectivity in what constitutes acceptable tradeoffs, but I'm thinking about ways to define and account for that.

If I visualize it as ships in a harbor, the ideal solution is one where it's a calm day, no movement on the water. Everybody is at the same level--hopefully at high tide. :) Solutions that are more stormy, where some or a lot of ships are up while others are down, are less desirable, even if the average level among them is high.

I think the term for what I'm not looking for is rank-maximal allocation . I can't find the term for the solution I do want. But this may just be a gap in my understanding.

More context:

I'm coming to these as a layman, so I'm lost in some of the formal notation and theory, though the concepts are generally clear enough. This is very much a "down the rabbit hole" situation for me. My wife has an event at work where she has to assign groups to projects. She usually does it by hand, and she asked me if there's a program to do it. I said, "There must be." Now that I know how much I don't know, I'm looking for a nudge in the right direction. :)

Here's my scenario: 8 groups, 8 projects. Each group can have one project, each project one group. Each group submits an ordinal preference for which project they would like to have (1 for the most preferred, 8 for the least). The goal is to find the best combination of assignments for the groups as a whole.

To give a simple hypothetical example. The following two scenarios are available.

Scenario A:

• Alice gets 1st choice
• Bob gets 1st choice
• Charlie gets 3rd choice

Scenario B:

• Alice gets 2nd choice
• Bob gets 2nd choice
• Charlie gets 2nd choice

All of the agents will agree that Scenario B is preferable. No one gets their 1st choice, but no one has to accept their 3rd.

The assignment problem is a good fit except, as I understand it, the solutions all value giving as many agents as possible their #1 choice, or finding the "lowest cost" solution. So solutions to the assignment problem would find Scenario A above to be the better solution. In my scenario, the best solution may not include anyone getting their 1st choice. All agents would gladly trade their first choice for their second or third if it means another agent gets to move up from a low preference to a higher preference.

This Q&A made me look at the stable marriage problem, but the issue I run into there is that the projects have no preferences. So I thought, well, maybe I can do SMP with indifference, where one side is completely indifferent. But my gut tells me that's the same thing as the assignment problem. I need the suitors to care about each other's outcomes almost as much as their own.

My next stop was the fair item allocation problem. I think this might be closer to what I'm looking for, but I struggled to understand all the different fairness criteria. It felt more complex than the problem I'm trying to solve, though I may be underestimating my problem.

I'm tempted to use this Hungarian Algorithm solver. My gut is that it would be highly likely to produce an acceptable solution. My problem is that I can't stop thinking about whether or not there's a more optimal solution.

I think with my level of knowledge here, my trying to cook up hypotheticals might just be more confusing. But I'll try to reemphasize the standard the ideal solution would meet, barring everyone getting their 1st choice:

• gap between "best" (most preferred) and "worst" (least preferred) assignment is as close to 0 as possible
• maximum number of assignment possible are "highly preferred" (say in the 1-4 range)
• it is acceptable to grow the gap to increase highly preferred assignments up to a point -- we can thin the cluster to shift its preference value higher, but we don't want to drop anyone too far.

The solution I'm thinking of now would be something like this: use the Hungarian Algorithm to get the rank-maximal allocation, then implement some kind of a swap meet where each agent considers his neighbor to see if a trade would result in a better overall outcome. I don't want to go too far down that path if I'd be ignoring a better solution. Or if the Hungarian algorithm is the solution and it's just a matter of getting over my own mental blocks. :)

Which type of problem do I actually have? Other than that I can't stop thinking about this?

• assignment-problem

• 1 $\begingroup$ I don't think this is answerable, because I don't see a clear specification of what you want. "there's a lot of subjectivity in what constitutes acceptable tradeoffs" - if so, the problem is not a computer science problem. You need to figure out what you want (the problem specification) before it makes sense to ask for an algorithm to compute the solution you want. Are you perhaps asking for a solution that maximizes the happiness of the least-happy team? $\endgroup$ –  D.W. ♦ Commented Jan 12, 2020 at 3:25
• $\begingroup$ I see what you're saying. I'm trying to think of a better way to define the most desirable solution. I'm visualizing plotting the assignments on a number line by preference. So there would be 8 points. Best solution is that they're all at 1, of course. Barring that, the best solution is the one where the cluster has the narrowest margin from left to right AND the greatest weight on the left side of the line (1-4). So a solution where a lot of the points cluster around 3 and a few cluster around 6 is better than one with a big cluster at 1 but a point at 8. Is that a clearer definition? $\endgroup$ –  tmoore82 Commented Jan 12, 2020 at 17:03
• $\begingroup$ No, it's not clearer. Examples aren't a substitute for a general specification. It seems you are trying to specify two objective functions you want to simultaneously maximize. But you probably can't simultaneously maximize both, because typically the maximum for the first will be less than the maximum for the second -- so part of the heart of this is figuring out how you want to trade off between those two competing but incompatible desires. We can't tell you that; only you know what you want. $\endgroup$ –  D.W. ♦ Commented Jan 12, 2020 at 19:23
• 1 $\begingroup$ I still wonder if perhaps you value the overall solution according to the happiness of the least-happy team, and that's what you want to maximize. It seems consistent with the examples you've given so far. $\endgroup$ –  D.W. ♦ Commented Jan 12, 2020 at 19:24
• $\begingroup$ I definitely do want to maximize the happiness of the least happy team. That's a great way to put it. I have a little hesitation about "dragging down" the group as a whole. I'm trying to define the tradeoff, but i'm falling short, it seems. Still thinking about it. Are there examples of solving for maximizing the happiness of the least happy team? What would that look like? $\endgroup$ –  tmoore82 Commented Jan 13, 2020 at 2:31

General remarks

You don't seem clear yet on what it is you're trying to optimize. As such, this question is not well-posed and not solvable. The first step in such situations is for you to figure out an objective function that measures how happy you are with a given solution. That formalizes the specification of what you want. Until you can do that, it's not reasonable to expect a computer to find what you want when you're not even sure what exactly you want. Only once you have such a characterization of what you're seeking does it make sense to ask for an algorithm to solve it.

There are several things you might be trying to optimize. I'll answer for two of them.

Maximizing the total happiness

Suppose we imagine that there is some amount of happiness that occurs if you match a group to a project, and we want to find an assignment that maximizes the sum of happinesses.

This can be solved by finding a maximum matching in a bipartite graph . You have one vertex for each group and one vertex for each project, and an edge between a group and a project that describes the utility/reward if that group is assigned to that project. Then, use any standard algorithm for maximum bipartite matching, such as the Hungarian algorithm.

I'd suggest that you don't think of this in terms of ranked preferences (your #1 preferred project, your #2 choice) but rather in terms of ratings (e.g., I'd be 100 units of happiness if I'm assigned this project, 50 units of happiness for that one, etc.). Ratings are more powerful and encode more information than rankings: given ratings, you can infer what the rankings would be if you wanted, but it also contains extra information about how much more I prefer my #1 choice over my #2 choice. This can lead to a better solution. It does require people to provide more information about their preferences, but that additional information might lead to a better solution, so it seems worthwhile.

Maximum bipartite matching is a special case of the assignment problem, so you could also view this as an instance of the assignment problem: you can convert rewards to costs by negating the value (so a utility/reward of $10$ corresponds to a cost of $-10$ ), then running an algorithm for the assignment problem.

Maximizing the least-happy group

Alternatively, suppose you measure how happy you are with an assignment overall by how happy is the unhappiest group.

Then this too can be solved by maximum matching. A simple approach is to use binary search: guess a threshold $t$ , build a bipartite graph with an edge from a group $g$ to a project $p$ if $g$ would have happiness $\ge t$ if assigned to $p$ . (Ignore all other pairs $g,p$ that yield less happiness.) Then check whether there is a perfect matching in this group. If yes, then it is possible to find an assignment that assures all groups have happiness $\ge t$ ; if not, then it is impossible. Finally, do binary search on $t$ to find the largest $t$ for which such an assignment exists. The running time will be the time to find a perfect matching (e.g., using the Hungarian algorithm), multiplied by a logarithmic factor (for the binary search).

There may be faster algorithms, but this one is conceptually simple to understand.

• $\begingroup$ Thanks for your answer! I think I follow what you're saying about rankings vs ratings. But wouldn't it still solve for the most groups to get the highest utility even if one group gets the least? In other words, if 7 groups get their 100 choice and one group gets their 60 choice, that's subjectively less acceptable than if some groups sacrifice their 100 choice to 90 so the last group can get up to 80. I can imagine the totals adding up the same under the Hungarian Algorithm. Does that make sense? $\endgroup$ –  tmoore82 Commented Jan 11, 2020 at 20:45
• 1 $\begingroup$ @tmoore82, It doesn't make sense to me. I think you need to edit your question to specify exactly what is the objective function you want to maximize or what is the precise definition of what constitutes an acceptable or optimal solution. Without that, I don't think the question is answerable, as the problem is not well-posed. Given your example, I would have said that they are not altrustic; altruistic would be the best outcome overall for the group, even if some have to sacrifice. So it's not clear to me what kind of solution you desire. $\endgroup$ –  D.W. ♦ Commented Jan 11, 2020 at 23:58
• $\begingroup$ Yes. That's right. The best outcome overall for the group, even if some have to sacrifice. That's a great way to put it. I'll edit the question and see if I can make that more clear. Thank you so much. That's really helpful language. $\endgroup$ –  tmoore82 Commented Jan 12, 2020 at 0:09
• $\begingroup$ Yet in your example 7*100+60 sounds to me like a better outcome overall than 7*90+80, so something doesn't seem to add up for me here. I look forward to your edit. $\endgroup$ –  D.W. ♦ Commented Jan 12, 2020 at 0:11
• 1 $\begingroup$ @tmoore82, perhaps you want to minimize the gap between the happiest and unhappiest team, rather than maximize the total utility? If so, I suggest editing the question to ask how to minimize that objective function. Be warned that the best way to minimize the gap might involve making everyone unhappy, so be sure that that is actually the criterion you want to optimize... $\endgroup$ –  D.W. ♦ Commented Jan 12, 2020 at 1:30

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 .

• Featured on Meta
• Bringing clarity to status tag usage on meta sites
• We've made changes to our Terms of Service & Privacy Policy - July 2024
• Announcing a change to the data-dump process

Hot Network Questions

• Why is Excel not counting time with COUNTIF?
• Ai-Voice cloning Scam?
• When is internal use internal (considering licenses and their obligations)?
• Claims of "badness" without a moral framework?
• The minimal Anti-Sudoku
• Do comets ever run out of water?
• can a CPU once removed retain information that poses a security concern?
• Windows aug. 13 update broke my Ubuntu system!
• Is it normal to be able to tear off PCB components with bare hands?
• How to make a case based on factual evidence that my colleague's writing style for submitted manuscripts has got to be overhauled?
• Communicate the intention to resign
• How is it decided whether a creature can survive without a head?
• Does full erase create all 0s or all 1s on the CD-RW?
• What mode of transport is ideal for the cold post-apocalypse?
• Sharing course material from a previous lecturer with a new lecturer
• Why would Space Colonies even want to secede?
• Is "the above table" more acceptable than "the below table", and if so, why?
• Why did evolution fail to protect humans against sun?
• Are Austria to Austria trains via the Deutsches Eck (German Corner) essentially domestic trains?
• Union of lists with original order
• How do you determine maximum frequency of AD574A 12-bit ADC?
• Looking for a British childrens book, I think from the 1950s, called "C-for-Charlie"
• Why did Borland ignore the Macintosh market?
• Why does Air Force Two lack a tail number?

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:

Computing k different solutions to the assignment problem

New citation alert added.

This alert has been successfully added and will be sent to:

You will be notified whenever a record that you have chosen has been cited.

To manage your alert preferences, click on the button below.

New Citation Alert!

Please log in to your account

Information & Contributors

Bibliometrics & citations, view options.

• Andrade-Garda J Ares-Casal J Hidalgo-Lorenzo M Lara J Lizcano D Suárez-Garaboa S (2022) A centralized matching scheme to solve the role-partner allocation problem in collaborative networks Computers and Industrial Engineering 10.1016/j.cie.2022.108244 169 :C Online publication date: 1-Jul-2022 https://dl.acm.org/doi/10.1016/j.cie.2022.108244

Index Terms

Computing methodologies

Mathematics of computing

Discrete mathematics

Mathematical analysis

Mathematical optimization

Continuous optimization

Theory of computation

Design and analysis of algorithms

Linear programming

Recommendations

A property of assignment type mixed integer linear programming problems.

In this paper we will prove that rather tight upper bounds can be given for the number of non-unique assignments that are achieved after solving the linear programming relaxation of some types of mixed integer linear assignment problems. Since in these ...

An efficient compact quadratic convex reformulation for general integer quadratic programs

We address the exact solution of general integer quadratic programs with linear constraints. These programs constitute a particular case of mixed-integer quadratic programs for which we introduce in Billionnet et al. (Math. Program., 2010) a general ...

New approaches for solving the block-to-train assignment problem

Railroad planning involves solving two optimization problems: (i) the blocking problem, which determines what blocks to make and how to route traffic over these blocks; and (ii) the train schedule design problem, which determines train origins, ...

Information

Published in.

Pergamon Press, Inc.

United States

Publication History

Author tags.

• Assignment problems
• Semi-assignment
• Ranking solutions
• Computational experiments
• Research-article

Contributors

Other metrics, bibliometrics, article metrics.

• 1 Total Citations View Citations
• 0 Total Downloads
• Downloads (Last 12 months) 0
• Downloads (Last 6 weeks) 0

View options

Login options.

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Share this publication link.

Copying failed.

Share on social media

Affiliations, export citations.

• Please download or close your previous search result export first before starting a new bulk export. Preview is not available. By clicking download, a status dialog will open to start the export process. The process may take a few minutes but once it finishes a file will be downloadable from your browser. You may continue to browse the DL while the export process is in progress. Download
• Download citation
• Copy citation

We are preparing your search results for download ...

We will inform you here when the file is ready.

Your file of search results citations is now ready.

Your search export query has expired. Please try again.

Multiple Optimal Solutions: Assignment Problem

Sometimes, it is possible to cross out all the zeros in the reduced matrix in two or more ways.

If you can choose a zero cell arbitrarily, then there will be multiple optimal solutions with the same total pay-off for assignments made. In such a case, the management may select that set of optimal assignments, which is more suited to their requirement.

• Maximization Problem
• Unbalanced Assignment Problem

Example: Multiple Optimal Solutions

Consider the following assignment problem : The Spicy Spoon restaurant has four payment counters. There are four persons available for service. The cost of assigning each person to each counter is given in the following table.

Assign one person to one counter to minimize the total cost.

After applying steps 1 to 3 of the Hungarian Method, we obtain the following matrix.

Use Horizontal Scrollbar to View Full Table Calculation.

Now by applying the usual procedure, we get the following matrix.

The resulting matrix suggest the alternative optimal solutions as shown in the following tables.

The persons B & C may be assigned either to job 2 or 3. The two alternative assignments are:

Share This Article

Operations Research Simplified Back Next

Goal programming Linear programming Simplex Method Transportation Problem

Academia.edu no longer supports Internet Explorer.

To browse Academia.edu and the wider internet faster and more securely, please take a few seconds to  upgrade your browser .

Enter the email address you signed up with and we'll email you a reset link.

• We're Hiring!
• Help Center

An Alternative Proposed Method for Solution of Assignment Problem

The assignment problem is a particular type of linear programming problem. In this paper, we analyzed the standard and existing proposed methods. After studying these methods, we proposed a new alternative method for solving the assignment problem. We examined the newly proposed method by a couple of numerical examples and compare this result with the standard method. The main characteristic of this newly proposed method is that it constructed a very easy logical and arithmetical algorithm. Here we point out some advantages and limitations of the new proposed method. Programming code for the newly proposed method has been added in this paper.

Related Papers

International Journal for Research in Applied Science & Engineering Technology (IJRASET)

IJRASET Publication

In this paper a new method is proposed for finding an optimal solution of a wide range of assignment problems, directly. A numerical illustration is established and the optimality of the result yielded by this method is also checked. The most attractive feature of this method is that it requires very simple arithmetical and logical calculations. The method is illustrated through an example.

1 í µí°·í µí±’í µí±í µí±Ží µí±Ÿí µí±¡í µí±ší µí±’í µí±›í µí±¡í µí±œí µí±“í µí±€í µí±Ží µí±¡ í µí±•í µí±’í µí±ší µí±Ží µí±¡í µí±–í µí±í µí± ,í µí° ¶í µí±œí µí±ší µí±–í µí±™í µí±™í µí±Ží µí±ˆí µí±›í µí±–í µí±£í µí±’í µí±Ÿí µí± í µí±–í µí±¡í µí±¦ ,í µí°µí µí±Ží µí±›í µí±”í µí±™í µí±Ží µí±‘í µí±’í µí± í µí±• 2 í µí°·í µí±’í µí±í µí±Ží µí±Ÿí µí±¡í µí±ší µí±’í µí±›í µí±¡í µí±œí µí±“í µí±€í µí±Ží µí±¡ í µí±•í µí±’í µí±ší µí±Ží µí±¡í µí±–í µí±í µí± ,í µí° ¶í µí±œí µí±ší µí±–í µí±™í µí±™í µí±Ží µí±ˆí µí±›í µí±–í µí±£í µí±’í µí±Ÿí µí± í µí±–í µí±¡í µí±¦ ,í µí°µí µí±Ží µí±›í µí±”í µí±™í µí±Ží µí±‘í µí±’í µí± í µí±• Abstract: Assignment problem is an important problem in mathematics and is also discuss in real physical world. In this paper we attempt to introduce a new proposed approach for solving assignment problem with algorithm and solution steps. We examine a numerical example by using new method and compute by existing two methods. Also we compare the optimal solutions among this new method and two existing method .The proposed method isa systematic procedure, easy to apply for solving assignment problem.

archana pandey

Assignment problems arise in different situation where we have to find an optimal way to assign n-objects to mother objects in an injective fashion. The assignment problems are a well studied topic in combinatorial optimization. These problems find numerous application in production planning, telecommunication VLSI design, economic etc. The assignment problems is a special case of Transportation problem. Depending on the objective we want to optimize, we obtain the typical assignment problems. Assignment problem is an important subject discussed in real physical world we endeavor in this paper to introduce a new approach to assignment problem namely, matrix ones assignment method or MOA-method for solving wide range of problem. An example using matrix ones assignment methods and the existing Hungarian method have been solved and compared it graphically. Also some of the variations and some special cases in assignment problem and its applications have been discussed in the paper.

Trisna Darmawansyah

Assignment problem is an important subject discussed in real physical world. We endeavor in this paper to introduce a new approach to assignment problem namely, ones assignment method, for solving a wide rang of such problems. This method offers significant advantages over similar methods, in the process, first we define the assignment matrix, then by using determinant representation we obtain a reduced matrix which has at least one 1 in each row and columns. Then by using the new method, we obtain an optimal solution for assignment problem by assigning ones to each row and each column. The new method is based on creating some ones in the assignment matrix and then try to find a complete assignment to there ones. The proposed method is a systematic procedure, easy to apply and can be utilized for all types of assignment problem with maximize or minimize objective functions. At the end, this method is illustrated with some numerical examples.

Science Park Research Organization & Counselling

Michael Florian

Hussein Ali Hussein Al-Dallal Al-Saeedi

YMER Digital

Assignment model comes under the class of linear programming model which is the most used techniques of operations research, which looks alike with transportation model with an objective function of minimizing the time or cost of manufacturing the products by allocating one job to one machine or one machine to one job or one destination to one origin or one origin to one destination only. In this paper, we represent linear mathematical formulation of Assignment problem and solved using Lingo Software. Keyword: Resource Allocation, Optimization Problem, Lingo Software, Assignment problem.

American Scientific Research Journal for Engineering, Technology, and Sciences

humayra afroz

Assignment problem is an important problem in mathematics and is also discuss in real physical world. In this paper we attempt to introduce a new proposed approach for solving assignment problem with algorithm and solution steps. We examine a numerical example by using new method and compute by existing two methods. Also we compare the optimal solutions among this new method and two existing methods. The proposed method is a systematic procedure, easy to apply for solving assignment problem.

Journal of Advances in Mathematics and Computer Science

Hudu Mohammed

Assignment problem is an important area in Operation Research and is also discussed in real physical world. In this paper an attempt has been made to solve the assignment problem using a new Method called the Penalty method. We discuss a numerical example by using the new Method and compare it with standard existing method which is the Hungarian method. We compare the optimal solution of the new Method and the Hungarian method. The new method is a simple procedure, easy to apply for solving assignment problem.

Loading Preview

Sorry, preview is currently unavailable. You can download the paper by clicking the button above.

RELATED PAPERS

IOP Publishing

American Journal of Operations Research

Mr Ebenezer Quayson

Advances in Mathematics: Scientific Journal

Dhanashri Munot

Applied Mathematical Sciences

Anwar N Jasim

IOSR Journals

Discrete Applied Mathematics

catherine roucairol

ashwin suryavanshee

Ajit Pal Singh

Bhausaheb G Kore

Hogpodrat Pangkum

Bela Vizvari

Industrial Engineering Journal

Shridhar Mhalsekar

Dr Avanish Kumar

International MultiConference of Engineers and Computer Scientists

Rudrajit Tapadar

AL-Rafidain Journal of Computer Sciences and Mathematics

Dr. Najla A Al-Saati

IJAR Indexing

Journal of Mathematics and Informatics

Sophia Porchelvi

shirko mahmoudi

Oksana Pichugina

International Journal of Computer Applications

Laila Abd, Al-Ghani, Saleh Nasser

Malaya Journal of Matematik

DR ANJU KHANDELWAL

•   We're Hiring!
•   Help Center
• Find new research papers in:
• Health Sciences
• Earth Sciences
• Cognitive Science
• Mathematics
• Computer Science
• Academia ©2024

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

Collectives™ on Stack Overflow

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

Q&A for work

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

Get early access and see previews of new features.

Alternative solution on an assigment problem using PuLP

I'm creating a program to solve assignment problems and so far so good, it works properly and in the end, it solves the problem. I'm using the PuLP library. But I just realized that when the problem has alternative solutions (instead of the unique optimal basic feasible solution) it only shows me the optimal one. Is there any function inside PuLP or any other library that can give me the number of total solutions (for example) or the objective function value for those said alt solutions?

• Status: Optimal

Total = 15.0

• linear-programming

The basic assignment problem looks like:

If you solve this, you get one optimal solution x*[i,j] . Let's record this solution in a[i,j,k] with initially k=0 . To find a next best solution we can add the constraint:

where n is the size of set i (and j) or the number of ones in the solution. This constraint will precisely cut off previous solutions. The algorithm becomes:

• solve original assignment problem
• store solution in a[i,j,k]
• solve problem with additional constraint
• if infeasible: STOP
• if no more solutions needed: STOP
• go to step 3.

An alternative would be to use a solver that has a so-called solution pool . That will do all of this in just one solve.

For an example see: https://yetanothermathprogrammingconsultant.blogspot.com/2018/04/k-best-solutions-for-assignment-problem.html

Your Answer

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

Sign up or log in

Post as a guest.

Required, but never shown

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

Not the answer you're looking for? Browse other questions tagged python linear-programming pulp or ask your own question .

• The Overflow Blog
• Scaling systems to manage all the metadata ABOUT the data
• Navigating cities of code with Norris Numbers
• Featured on Meta
• We've made changes to our Terms of Service & Privacy Policy - July 2024
• Bringing clarity to status tag usage on meta sites
• Tag hover experiment wrap-up and next steps

Hot Network Questions

• How are USB-C cables so thin?
• What is this fruit from Cambodia? (orange skin, 3cm, orange juicy flesh, very stick white substance)
• Is an invalid date considered the same as a NULL value?
• As a resident of a Schengen country, do I need to list every visit to other Schengen countries in my travel history in visa applications?
• Why is Excel not counting time with COUNTIF?
• Union of lists with original order
• What is Causing This Phenomenon? Is it the Geometry Package?
• How much air escapes into space every day, and how long before it makes Earth air pressure too low for humans to breathe?
• Sums of X*Y chunks of the nonnegative integers
• Testing framework with a single assertion macro
• Why does Air Force Two lack a tail number?
• Why are the perfect fifth and fourth called "perfect" in 12-ET when they differ by approximately 2 cents from just intonation?
• What's the polarity of this electrolytic capacitor symbol?
• What mode of transport is ideal for the cold post-apocalypse?
• Are Austria to Austria trains via the Deutsches Eck (German Corner) essentially domestic trains?
• To what extent do value sets determine polynomials mod p?
• Functional derivative under a path integral sign
• Alternative to BlakeTwo256 for WASM Compatibility in a no_std Environment in Rust
• Unstable output C++: running the same thing twice gives different output
• How to interpret coefficients of logistic regression using natural cubic splines?
• How to make a case based on factual evidence that my colleague's writing style for submitted manuscripts has got to be overhauled?
• Is there an integer that serves as the short leg of a primitive Pythagorean triple, the long leg of another, and the hypotenuse of a third?
• OAuth 2.0 - why is the state parameter needed in order to prevent CSRF at authorization code login flow?
• Is groff ignoring `.nh` command?

Index     Assignment problem     Hungarian algorithm     Solve online    

Solve an assignment problem online

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

Fill in the cost matrix ( random cost matrix ):

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

HungarianAlgorithm.com © 2013-2024

SQL Server Database and Server Roles for Security and Permissions

By: Nivritti Suste   |   Updated: 2024-08-13   |   Comments   |   Related: > Security

SQL Server is one of the most used relational database management systems in many organizations. It is mainly used to store, manage, and retrieve data with ease. Apart from this, SQL Server is popular for data security, including encryption, data masking, and role-based access control.

Today, we will discuss role-based access control (RBAC) in SQL Server. Using RBAC, you can assign specific permissions to users according to their roles within the server. There are different types of roles in SQL Server, which can be confusing. Here, we will discuss the distinctions between SQL Server and Database roles, helping us to manage security more effectively.

Let's first understand the roles. There are two types of roles in SQL Server: 1) SQL Server Roles and 2) Database Roles.

What are SQL Server Roles?

SQL Server roles are predefined sets of permissions used to control access to server resources. They are created at the server level and typically assigned to logins or other server roles, which helps administrators manage permissions and security for the entire SQL Server instance. SQL Server roles are like Windows groups, allowing for easy management and assignment of permissions to multiple users.

Types of SQL Server Roles

There are three types of SQL Server roles: fixed server, user-defined server, and application.

Fixed SQL Server Roles -  Fixed server roles are predefined sets of server-level permissions that cannot be modified or deleted. These roles are created during the installation of SQL Server. This includes one of the important ' sysadmin ' roles, which has "God-level control" over the entire SQL Server instance, and other specialized roles like bulkadmin, dbcreator, diskadmin.

User-Defined SQL Server Roles - There are multiple instances when you need custom sets of permissions based on your business needs. Here, user-defined server roles come into the picture; these are not predefined roles. User-defined server roles will allow you to create custom sets of permissions based on your specific needs. These roles granted to logins or only other user-defined server roles provide more control over access to server-wide resources.

SQL Server Application Roles -  The above-mentioned roles are mostly assigned to individual users. This third type of role is like user-defined server roles called Application Roles. These roles are created for applications only and used by applications instead of any individual users. These special roles let applications borrow permissions for a short time to complete the task, keeping regular users and app users separate and safe.

Key Features of SQL Server Roles

• Scope : Server-wide
• Creation : Created at the server level
• Assignment : Assigned to logins or other roles
• Permissions : Control access to server resources (databases, logins, etc.)

Example: SQL Code to Create a SQL Server Role

• Create a SQL Server Role. Replace [role_name] with the desired name for your new server role.
• Assign the User to the Role. Replace [role_name] with the name you chose in Step 1 and [user_name] with the username you want to assign the role to.
• You need to have sufficient permissions (e.g., sysadmin server role) to create server roles and manage user memberships.
• This code snippet only creates the role and assigns the user. You'll need to grant specific permissions to the role itself to control user access within the server.

Example: Granting Permissions to the Role

You can use the GRANT statement.

This grants the "Connect to Server" permission to the newly created role. You can explore other permission options based on your needs.

How to Check Server Roles Using SSMS

• Open SSMS and connect to your SQL Server.
• In the Object Explorer , navigate to Security > Server Roles .
• Expand the Server Roles. You will see all the predefined and user-defined roles listed.

Alternatively, you can use SQL Query:

What are SQL Server Database Roles?

The Database Roles, as the name suggests, are specific to control databases and database objects. Unlike server roles, these roles are created and managed at the database level and can be assigned to database users and other roles within the same database they are created. These roles are a more controlled approach to managing permissions in a SQL Server instance as different users may have different levels of permissions.

Types of SQL Server Database Roles

There are also three types of database roles: fixed database, user-defined database, and application.

Fixed SQL Server Database Roles - Fixed database roles are like fixed server roles in that they cannot be modified or deleted. However, they are limited to the specific database in which they were created. The default fixed database role is ' db_owner' , which has full control over the entire database and other roles like db_accessadmin, db_backupoperator, and db_datareader.

User-Defined SQL Server Database Roles - User-defined database roles allow for the creation of custom sets of permissions within a specific database. These roles can be assigned to users or other user-defined database roles, allowing for more granular control over access to objects within that database.

SQL Server Application Roles - Like SQL Server roles, application roles at the database level are intended for use by applications rather than normal users. They enable applications to temporarily assume permissions and perform actions on behalf of the role, providing an added layer of security.

Key Features

• Scope : Database-specific
• Creation : Created at the database level
• Assignment : Assigned to database users or other roles
• Permissions : Control access to specific database objects (tables, views, etc.)

Example: SQL Code to Create a Database Role

• Create a Database Role
• [role_name]: The desired name for your new database role.
• [user_name]: The username who will own (own as in "be authorized by") the role. This user doesn't necessarily need to be the one assigned to the role.

This statement combines the CREATE ROLE and AUTHORIZATION clauses in a single line. The AUTHORIZATION clause specifies the user who will "own" the database role. This doesn't necessarily restrict who can be assigned to the role, but it determines who can manage the role's permissions later (e.g., adding/removing members and granting/revoking permissions to the role).

• Assigning a User to the Database Role
• [role_name]: The name of the database role you created.
• [user_name]: The username you want to assign to the database role.

This will grant the user the permissions associated with the database role.

• You need to have the db_owner role or equivalent permissions on the database to create database roles and manage user memberships.
• Remember to grant specific permissions to the database role itself to control user access within the database. You can use the GRANT statement for this purpose.

How to Check Database Roles Using SSMS

• In SSMS , navigate to the specific database you want to check.
• Right-click on " Security " and select " Roles ".
• This will show you a list of all the roles defined within that database.

Another way to check database roles with a system view:

• Open a new query window in SSMS.
• Use the below query to check all 'Database_Role.'

Roles Key Differences Brief

When to Use Which Role

• SQL Server Roles: To manage overall user access to the SQL Server instance and its resources.
• Database Roles: To grant granular permissions within specific databases based on user needs.

Best Practices for Using SQL Server and Database Roles

Follow these tips to keep things safe and organized when setting up who can access what in SQL Server:

• Limit Sharing: Only give roles what they need. Don't give extra access.
• Keep Checking: As things change, update roles so access stays right.
• Give Just Enough: Roles and users should only have what they need to do their job.
• Make Your Own Roles: Don't use predefined roles. Create ones that fit your needs.
• Roles for Jobs: Use roles for different jobs to keep things organized.
• Write it Down: Keep track of all the roles, so you don't get confused.
• Double Check: Look at the roles regularly to make sure everything is safe.

Understanding the difference between SQL Server roles and database roles is important to keep your SQL Server secure. SQL Server roles provide server-wide control, while database roles offer more controlled permissions within specific databases. By leveraging these roles appropriately, database administrators and SQL developers can enhance security, streamline permission management, and ensure users have the necessary access without compromising security.

• Check out these MSSQLTips.com Security tips .

About the author

Comments For This Article

Related Content

Understanding SQL Server fixed database roles

SQL Server Database Users to Roles Mapping Report

The Power of the SQL Server Database Owner

Nesting Database Roles in SQL Server

Implicit Permissions Due to SQL Server Database Roles

Retrieving SQL Server Fixed Database Roles for Disaster Recovery

List SQL Server Login and User Permissions with fn_my_permissions

Free Learning Guides

Learn Power BI

What is SQL Server?

Download Links

Become a DBA

What is SSIS?

Related Categories

Auditing and Compliance

SQL Injection

Surface Area Configuration Manager

Development

Date Functions

System Functions

JOIN Tables

SQL Server Management Studio

Database Administration

Performance

Performance Tuning

Locking and Blocking

Data Analytics \ ETL

Microsoft Fabric

Azure Data Factory

Integration Services

Popular Articles

Date and Time Conversions Using SQL Server

Format SQL Server Dates with FORMAT Function

SQL Server CROSS APPLY and OUTER APPLY

SQL Server Cursor Example

SQL CASE Statement in Where Clause to Filter Based on a Condition or Expression

DROP TABLE IF EXISTS Examples for SQL Server

SQL NOT IN Operator

SQL Convert Date to YYYYMMDD

Rolling up multiple rows into a single row and column for SQL Server data

Format numbers in SQL Server

Script to retrieve SQL Server database backup history and no backups

Resolving could not open a connection to SQL Server errors

How to install SQL Server 2022 step by step

SQL Server PIVOT and UNPIVOT Examples

How to monitor backup and restore progress in SQL Server

An Introduction to SQL Triggers

SQL Server Management Studio Dark Mode

Using MERGE in SQL Server to insert, update and delete at the same time

SQL Server Loop through Table Rows without Cursor