Operations Management and Strategic Management · Job Evaluation, Job Allocation - Assignment

Assignment Problem: Prohibited Assignments and Multiple Optimal Solutions

Updated 10 October 2026 · Fact-checked

In an assignment problem, a prohibited assignment is blocked by giving that cell a very large cost M in minimisation, so it is never chosen. Multiple optimal solutions exist when, after the Hungarian method, extra zeros allow more than one complete set of assignments with the same total cost. A travelling salesman problem is solved like an assignment problem, but the result must form a single closed tour.

Understand Special Cases: Restrictions and Multiple Optimal Solutions

The assignment problem matches n jobs to n workers (or machines), one each, to minimise total cost or time. The Hungarian method finds the answer by creating zeros in the cost matrix and then picking one zero in every row and column.

Sometimes a worker cannot do a job. The machine may be unsuitable, or the person may be unavailable. This is a prohibited assignment. You block it by putting a very large cost, written M, in that cell. In a minimisation problem, M is so big that the cell never gets a zero and is never chosen. In a maximisation problem, you put a very large negative value (−M) in that cell of the profit matrix. After you convert to a loss matrix, this becomes a very large positive cost M. Either way, the blocked cell must never be chosen.

Multiple optimal solutions appear when the final matrix has more zeros than you need, so you have a choice of zeros. Different choices can give different assignments, but every one costs the same total. You find the cost by adding the original costs of any one valid set. The total is the same for all of them.

The travelling salesman problem (TSP) asks a salesman to visit n cities once each and return to the start at least total distance or cost. You set up an n × n matrix of distances. The diagonal (city to itself) is blocked with M. Solve it as an assignment problem. Then check the result: the assignments must link up into one closed tour through all cities. If they form two or more separate loops (sub-tours), the solution is not valid for TSP.

If you get sub-tours, you take the next best zero or cell that joins the loops. Do this by trial, keeping the extra cost as small as possible.

Key rules to remember

Prohibited assignment: Cost of blocked cell = M (a very large number); For minimisation. M is never chosen. Treat M as unchanged by subtraction: M − k is still very large.
Valid assignment test: Number of lines = n ⇒ optimal assignment possible; If the minimum lines covering all zeros is less than n, revise the matrix and repeat.
Revision step: Subtract the smallest uncovered element from uncovered cells; add it to cells at line intersections; Cells covered by one line stay unchanged.
Total cost: Total cost = Σ original cost of each assigned cell; Always read the cost from the original matrix, not the reduced one.
Multiple optima signal: More than one way to choose n independent zeros ⇒ multiple optimal solutions; All such solutions have the same total cost.
TSP set-up: Diagonal cells (i to i) = M; tour must be one closed cycle through all n cities; Assignment answer with sub-tours is not a valid tour.

How to solve Special Cases: Restrictions and Multiple Optimal Solutions questions

Use this method for any assignment question with restrictions, ties or a travelling salesman set-up.

1Check the matrix is square. If not, add a dummy row or column of zeros. Then write M in every prohibited cell (and on the diagonal for TSP).
2Row reduction: subtract the smallest element of each row from every element in that row. Treat M as staying M.
3Column reduction: subtract the smallest element of each column from every element in that column.
4Cover all zeros with the minimum number of horizontal and vertical lines. If the lines equal n, go to the next step. If fewer, subtract the smallest uncovered element from all uncovered cells, add it to cells at intersections, and repeat.
5Make the assignment. Start with rows or columns that have a single zero, tick that assignment and cross out other zeros in its row and column. Repeat. If every row has two or more zeros, you have a tie, so pick any zero and continue.
6If more than one complete set of assignments exists, list each as a separate optimal solution and state that multiple optima exist.
7For TSP, join the assignments into a route. If they form one closed tour, you are done. If they form sub-tours, choose the next smallest cell that links the loops and re-check.
8Compute total cost from the original matrix. Give the assignment table, the total, and a one-line conclusion.

Quickest way: Zero-scan shortcut for restricted and tied problems

When to use it: Use it when the matrix is 4 × 4 or 5 × 5 and you need to finish within about ten minutes.

Write M first in blocked cells so you never forget it.
Do row and column reduction in one pass and redraw the matrix neatly.
Scan for the row or column with the fewest zeros and assign it first.
If you reach a stage where each unassigned row has two zeros, say 'multiple optimal solutions' and write down both choices.
Compute cost for one choice from the original matrix. Quickly check the second choice gives the same total as a self-check.
For TSP, write the route as A → B → C → A and tick that every city appears once.

Common mistakes in Special Cases: Restrictions and Multiple Optimal Solutions

Putting 0 or a small number in a prohibited cell instead of M.
Students think of 'no cost' instead of 'not allowed'.
Fix: A prohibited cell must be M in minimisation. Write it before you start reducing.
Subtracting from M and treating the result as a small number.
M looks like any other entry during reduction.
Fix: Treat M minus any number as still M. Never let it become a zero or the smallest uncovered element.
Adding the reduced-matrix numbers to get total cost.
The zeros are in front of you, so students add the reduced values.
Fix: Go back to the original matrix and add the cost of each assigned cell.
Stopping at one solution when ties exist and giving no mention of alternatives.
Students stop once they get a full assignment.
Fix: If a row or column offers a choice of zeros, say so and show the other assignment. Both give the same cost.
Accepting a TSP assignment with sub-tours as the final route.
The assignment looks complete, so the loop check is skipped.
Fix: Trace the route from the start city. If you return before visiting all cities, break the sub-tour using the next lowest cell and re-check.
Leaving the diagonal blank or zero in a TSP matrix.
A city to itself seems to have zero distance.
Fix: Put M on the diagonal so a city is never assigned to itself.

Worked examples

Example 1

Four jobs J1 to J4 are to be assigned to four machines M1 to M4, one each, at minimum cost (₹). Machine M3 cannot do job J2. Costs: J1: 12, 10, 14, 16 | J2: 15, 11, M, 13 | J3: 13, 12, 15, 14 | J4: 11, 14, 12, 10 (columns are M1, M2, M3, M4; M denotes the prohibited cell). Find the optimal assignment and cost.

Show the solution

Row reduction. Row minima: J1 = 10, J2 = 11, J3 = 12, J4 = 10. Reduced rows: J1: 2, 0, 4, 6 | J2: 4, 0, M, 2 | J3: 1, 0, 3, 2 | J4: 1, 4, 2, 0.
Column reduction. Column minima: M1 = 1, M2 = 0, M3 = 2, M4 = 0. Reduced matrix: J1: 1, 0, 2, 6 | J2: 3, 0, M, 2 | J3: 0, 0, 1, 2 | J4: 0, 4, 0, 0.
Cover zeros (first time). The zeros are at J1M2, J2M2, J3M1, J3M2, J4M1, J4M3, J4M4. Three lines cover them: column M1, column M2 and row J4. Three is fewer than n = 4, so revise.
Uncovered cells: J1M3 = 2, J1M4 = 6, J2M3 = M, J2M4 = 2, J3M3 = 1, J3M4 = 2. Smallest uncovered = 1. Subtract 1 from uncovered cells and add 1 at the intersections (J4M1 and J4M2). New matrix: J1: 1, 0, 1, 5 | J2: 3, 0, M, 1 | J3: 0, 0, 0, 1 | J4: 1, 5, 0, 0.
Cover zeros (second time). J1 and J2 both have their only zero in M2, so four independent zeros are not possible. Three lines cover all zeros: column M2, row J3 and row J4. Three is fewer than 4, so revise again.
Uncovered cells: J1M1 = 1, J1M3 = 1, J1M4 = 5, J2M1 = 3, J2M3 = M, J2M4 = 1. Smallest uncovered = 1. Subtract 1 from uncovered cells and add 1 at the intersections (J3M2 and J4M2). Cells covered by one line stay. Final matrix: J1: 0, 0, 0, 4 | J2: 2, 0, M, 0 | J3: 0, 1, 0, 1 | J4: 1, 6, 0, 0.
Check lines. At least four lines are now needed, because four independent zeros exist (see the next step). Lines equal n = 4, so an optimal assignment is possible.
Assign. Zeros: J1 at M1, M2, M3; J2 at M2, M4; J3 at M1, M3; J4 at M3, M4. One complete set: J2→M4, then J4→M3, then J3→M1, then J1→M2. All four rows and columns are used.
Cost from original matrix: J1M2 = 10, J2M4 = 13, J3M1 = 13, J4M3 = 12. Total = 10 + 13 + 13 + 12 = 48.
Other complete sets exist in the same final matrix. J1→M1, J2→M2, J3→M3, J4→M4 costs 12 + 11 + 15 + 10 = 48. J1→M3, J2→M2, J3→M1, J4→M4 costs 14 + 11 + 13 + 10 = 48. All give the same total, so multiple optima exist.

Answer: Assign J1→M2, J2→M4, J3→M1, J4→M3. Minimum total cost = ₹48. Other optimal assignments exist at the same cost, for example J1→M1, J2→M2, J3→M3, J4→M4 (12 + 11 + 15 + 10 = ₹48), so there are multiple optimal solutions.

Example 2

A salesman must start from city A, visit B, C and D once each and return to A. Distances (km): A–B 10, A–C 15, A–D 20, B–A 10, B–C 35, B–D 25, C–A 15, C–B 35, C–D 30, D–A 20, D–B 25, D–C 30. Find the shortest route.

Show the solution

This problem is solved by enumeration, not by the assignment method. With only four cities, listing every tour is quick and gives the exact answer. For larger problems, use the assignment method with M on the diagonal and check the result for sub-tours.
The matrix is symmetric, so a tour and its reverse have equal length. With four cities there are (4 − 1)! = 6 directed tours from A, which is 3 distinct tours when direction is ignored.
Tour 1: A→B→C→D→A = 10 + 35 + 30 + 20 = 95.
Tour 2: A→B→D→C→A = 10 + 25 + 30 + 15 = 80.
Tour 3: A→C→B→D→A = 15 + 35 + 25 + 20 = 95.
The reverse of each tour has the same length: A→D→C→B→A = 95, A→C→D→B→A = 80, A→D→B→C→A = 95.
The minimum is 80, from A→B→D→C→A or its reverse A→C→D→B→A. These are the same tour travelled in opposite directions.

Answer: Shortest route: A → B → D → C → A (or the same tour reversed, A → C → D → B → A), total distance 80 km. The other two tours are each 95 km.

Exam tips

Write the M cells first and say 'M is prohibited' in your answer. Examiners look for it.
If a tie appears, show both assignments and state the cost for each. A one-line note that multiple optima exist earns the interpretation mark.
Always compute total cost from the original matrix and show the cell-by-cell addition.
In TSP questions, trace the route in words after the assignment and say whether it is a single tour. Mention sub-tours if they arise.
For MCQs, if a question says 'cannot be assigned', the answer is usually linked to assigning a very large cost M to that cell.

Practice questions from Job Evaluation, Job Allocation - Assignment

Special Cases: Restrictions and Multiple Optimal Solutions: frequently asked questions

How do you handle a prohibited assignment in the assignment problem?

Put a very large cost M in that cell for a minimisation problem. It stays large through reduction, so it never becomes a zero and is never chosen. Solve the rest by the Hungarian method.

How do you know there are multiple optimal solutions?

After the final matrix, if you can choose the n independent zeros in more than one way, there are multiple optimal solutions. Each gives the same total cost when you add the original cell costs.

Is the travelling salesman problem the same as the assignment problem?

It is solved with the same method, but with M on the diagonal and an extra condition. The final assignments must form one closed tour through all cities. If they form separate loops, you must adjust the solution.

Do I use the reduced matrix or original matrix to find total cost?

Use the original matrix. Note the cells chosen in the final assignment and add their original costs.