Skip to content

Strategic Cost Management · Assignment

Restricted Assignments and Travelling Salesman Problem

Updated 11 October 2026 · Fact-checked

A restricted assignment problem has some worker-job pairs that are not allowed. You block each one with a very large cost M and then apply the Hungarian method. The travelling salesman problem is solved the same way, with M on the diagonal. You then check that the answer forms one single closed tour.

Understand Restricted Assignments and Travelling Salesman Problem

A standard assignment problem matches n workers to n jobs, one each, at least total cost. Sometimes a worker cannot do a job. He may lack the skill, the machine may be unavailable, or a route may be closed. That pair is a prohibited assignment.

You handle it by putting a very large cost, written M, in that cell. For minimisation, M is so large that the optimal solution will never choose that cell. M stays large through every step. M minus a number is still M, and M is never chosen as a row or column minimum.

The travelling salesman problem (TSP) asks: a salesman must visit every city exactly once and return to the start. Which order gives the least total distance, time or cost? Each city is both a 'from' city and a 'to' city, so the distance table looks like an assignment matrix. A city cannot be assigned to itself, so every diagonal cell is M.

There is one catch. An assignment gives each city exactly one successor and one predecessor, but this can split into sub-tours, such as A→D→A and B→C→B. That is not a valid route. If the Hungarian solution is a single closed loop through all cities, you are done. If not, you must break the sub-tours.

In the exam, expect a small matrix of four or five rows. Marks go for correct M handling, correct reduction, the final assignment, the total cost and the sub-tour check.

Key rules to remember

Prohibited cell rule
Cost of prohibited assignment = M (M very large, M ± k = M)
Use for minimisation. Never choose an M cell in the final answer.
TSP diagonal rule
Cost(i → i) = M for every city i
A city cannot be its own next city.
Optimality test
Minimum number of lines covering all zeros = n
n is the order of the square matrix. If fewer lines, revise the matrix.
Matrix revision
Subtract the smallest uncovered element from uncovered cells and add it to cells at line intersections
Cells covered by one line stay unchanged.
TSP validity check
Assignment is a valid tour only if it forms one closed loop of n cities
Two or more loops are sub-tours and the solution is not yet valid.
Total cost
Total cost = Σ original costs of the chosen cells
Always read the cost from the original matrix, not the reduced one.

How to solve Restricted Assignments and Travelling Salesman Problem questions

Use this method for any restricted assignment or TSP question.

  1. 1Write the cost matrix. Check it is square. If not, add a dummy row or column with zero cost.
  2. 2Put M in every prohibited cell. For a TSP, put M in every diagonal cell as well.
  3. 3Subtract the smallest element of each row from that row. Then subtract the smallest element of each column from that column.
  4. 4Cover all zeros with the minimum number of horizontal and vertical lines. If the number of lines equals n, go to step 6.
  5. 5If lines are fewer than n, subtract the smallest uncovered element from all uncovered cells and add it to intersection cells. Go back to step 4.
  6. 6Make the assignment. Start with rows or columns that have a single zero, tick that zero and strike out the rest of its row and column. Repeat. Confirm no M cell is chosen.
  7. 7Add the original costs of the chosen cells to get the total cost.
  8. 8For a TSP, trace the route from the start city. If it returns before visiting every city, you have sub-tours. Forbid one arc of a sub-tour by putting M there and re-solve, or use another zero assignment, until you get one complete tour.

Quickest way: Row-column reduction with an early tour check

When to use it: Use for 4×4 or 5×5 matrices in the written section when time is short.

  1. Fill M in every blocked cell first. Do this before any subtraction so you never subtract from a blocked cell by mistake.
  2. Reduce rows, then columns. Count your lines on the zeros only once.
  3. List the zero cells of each row. Start the assignment from the row with one zero.
  4. For a TSP, trace the loop at once. If it is a single loop, stop. If it is a sub-tour, set M on one arc of the shortest sub-tour, adjust the row or column, and re-solve. Check your final cost by adding the original cells.

Common mistakes in Restricted Assignments and Travelling Salesman Problem

  • Leaving the prohibited cell blank or as 0

    Students treat 'not allowed' as 'no cost'.

    Fix: Write M. A zero would make the prohibited cell the most attractive one.

  • Forgetting the diagonal M in a TSP

    Students copy the distance table and the blank diagonal looks harmless.

    Fix: Put M on every diagonal cell before reducing. Otherwise a city may be sent to itself.

  • Accepting a sub-tour as the final answer

    The lines equal n and the assignment looks complete, so students stop.

    Fix: Trace the route from the starting city. Stop only if one loop covers all cities.

  • Calculating total cost from the reduced matrix

    Students add the zeros or reduced numbers.

    Fix: Add the original costs of the chosen cells, or add all reductions made including matrix revisions.

  • Subtracting from M and treating the result as a small number

    Students try to do arithmetic with M as if it were a normal figure.

    Fix: Keep M as M. Ignore it when finding minima and when counting uncovered elements.

  • Drawing too many lines when covering zeros

    Students draw one line per zero instead of searching for the minimum cover.

    Fix: Use lines through rows or columns with the most zeros first. Check by trying the assignment.

Worked examples

Example 1

Four workers A, B, C and D are to be assigned to four jobs J1 to J4, one each. The cost (₹ '000) is: A: 12, 10, 15, 22. B: 16, 18, –, 20. C: 14, 12, 16, 18. D: 20, 14, 18, –. Worker B cannot do J3 and worker D cannot do J4. Find the assignment with minimum total cost.

Show the solution
  1. Put M in the prohibited cells. Row B is 16, 18, M, 20 and row D is 20, 14, 18, M.
  2. Row minima are 10, 16, 12 and 14. After subtracting: A: 2, 0, 5, 12. B: 0, 2, M, 4. C: 2, 0, 4, 6. D: 6, 0, 4, M.
  3. Column minima are 0, 0, 4 and 4. After subtracting: A: 2, 0, 1, 8. B: 0, 2, M, 0. C: 2, 0, 0, 2. D: 6, 0, 0, M.
  4. The zeros can be covered by 3 lines only: columns J2 and J3 and row B. This is less than 4, so revise.
  5. The smallest uncovered element is 2. Subtract 2 from uncovered cells and add 2 at the intersections of row B with J2 and J3.
  6. New matrix: A: 0, 0, 1, 6. B: 0, 4, M, 0. C: 0, 0, 0, 0. D: 4, 0, 0, M. Now 4 lines are needed, so it is optimal.
  7. Assign B to J4 (only row-B zero left once J1 is used by A), A to J1, D to J2 and C to J3. No M cell is used.
  8. Cost: A–J1 12 + B–J4 20 + C–J3 16 + D–J2 14 = 62.

Answer: A–J1, B–J4, C–J3, D–J2 with minimum total cost ₹62,000. An alternative with the same cost is A–J2, B–J1, C–J4, D–J3.

Example 2

A salesman starts from city A and must visit B, C and D once each and return to A. The distances (km), the same in both directions, are: A–B 4, A–C 7, A–D 3, B–C 6, B–D 3, C–D 7. Find the shortest route.

Show the solution
  1. Write the matrix with M on the diagonal. A: M, 4, 7, 3. B: 4, M, 6, 3. C: 7, 6, M, 7. D: 3, 3, 7, M.
  2. Row minima are 3, 3, 6 and 3. After subtracting: A: M, 1, 4, 0. B: 1, M, 3, 0. C: 1, 0, M, 1. D: 0, 0, 4, M.
  3. Column minima are 0, 0, 3 and 0. Subtract 3 from column C: A: M, 1, 1, 0. B: 1, M, 0, 0. C: 1, 0, M, 1. D: 0, 0, 1, M.
  4. The only zero assignment is A→D, D→A, B→C, C→B. Cost 3 + 3 + 6 + 6 = 18. It forms two sub-tours (A–D–A and B–C–B), so it is not a valid route.
  5. Forbid A→D by putting M there. Row A becomes M, 1, 1, M. Subtract 1 from row A: M, 0, 0, M.
  6. Zeros now allow C→B, A→C, B→D, D→A. This is the single loop A→C→B→D→A.
  7. Cost: A–C 7 + C–B 6 + B–D 3 + D–A 3 = 19 km.
  8. Check by listing all tours of four cities: A-B-C-D-A is 4 + 6 + 7 + 3 = 20, A-B-D-C-A is 4 + 3 + 7 + 7 = 21, A-C-B-D-A is 19. So 19 is the least.

Answer: Shortest route A → C → B → D → A (or the reverse) with total distance 19 km. The first assignment of 18 km was rejected because it formed two sub-tours.

Exam tips

  • Write the M cells first and show them in your matrix. Examiners give marks for correct handling of the restriction.
  • In a TSP, always add a line stating whether the assignment forms a single tour. Do this even if it does.
  • Show each stage: row reduction, column reduction, line cover, revision. Method marks are given even if one number is wrong.
  • Quote the final cost from the original matrix and write the route in full, such as A → C → B → D → A, with units.
  • Section A may ask whether an M cell can be in the optimal answer, or what a dummy city does. Know the rules, not just the steps.

Practice questions from Assignment

Restricted Assignments and Travelling Salesman Problem in other exams

The same ground in other exams, if you are preparing for more than one or want another angle on it.

Restricted Assignments and Travelling Salesman Problem: frequently asked questions

What value should I use for a prohibited assignment?

Use a very large cost M in a minimisation problem so that the cell is never chosen. You do not need a number. Keep it as M throughout and ignore it when finding minima.

Why is the travelling salesman problem solved as an assignment problem?

Each city needs exactly one next city and one previous city, which is what an assignment does. The diagonal is set to M so no city goes to itself. The result must still be checked for sub-tours, because the assignment method does not guarantee a single loop.

What do I do if the TSP solution has sub-tours?

Choose one arc from a sub-tour and forbid it by putting M in that cell. Then re-reduce and re-solve. Repeat until the answer is one complete tour. For small matrices you can also check the possible tours directly.

How do I handle a restricted assignment in a maximisation problem?

Convert the matrix to a minimisation first, usually by subtracting every value from the largest value. The prohibited cell should stay unattractive. Give it a very high cost in the converted matrix, or treat it as a very large negative profit before converting.