Algorithm to solve an assignment or matching with a constraint

Question

Here is the problem. Suppose we have N workers and N jobs. We want to assign each job exactly one worker. For each worker i, he could do some jobs on some cost. Our goal is to minimize the total cost on the condition that any single cost should be less than some value.

For example, 10 workers and 10 jobs. Worker 1 can do job 1 with $0.8, job 2 with $2.3, job 3 with $15.8, jobs 4 to 8 with $100, job 9 with $3.2, job 10 with $15.3.

Worker 2 can do job 1 with $3.5, job 2 with $2.3, job 3 with $4.6, job 4 with $17, etc.

Our goal is to find a matching or we can call it an assignment such that the total cost is minimized but any single cost of the corresponding pair/matching between work i and job i is less than a value like $50.

I would very much like to solve it in MATLAB if possible.

Answer 1

This is a slight variation of the Assignment Problem. To handle your additional constraint that no single job cost should be more than some value, just change all entries in the matrix of costs that are greater than this threshold to a huge value (bigger than the sum of all other entries will suffice), and solve as usual, using e.g. the Hungarian Algorithm.