Section6.3The Assignment Problem and Hungarian Algorithm
We consider the assignment problem, where each source and sink have supply and demand 1, and an alternative algorithm to solve these sort of problems.
Exploration6.3.1.
Supose we have 3 jobs and 3 contractors, and we wish to assign jobs to contractors at the minimum price. How can we distribute the jobs amongst the contractors? (Costs are in thousands of dollars)
Job 1
Job 2
Job 3
Contractor 1
10
9
12
?
Contractor 2
9
9
10
?
Contractor 3
10
7
9
?
?
?
?
?
(a)
What are the “supply” and “demand” of each job and contractor?
Could there have been an easier way to approach this problem?
Definition6.3.2.
An assignment problem is a transportation problem where the supply and demands are all 1.
Note that in Exploration 6.3.1, while we were able to solve this as a transportation problem, the restriction to supplies and demands of 1 ought to yield a simpler way to find a solution.
Definition6.3.3.
Let \(T\) be a tableau for a balanced assignment problem. A permutation set of zeroes is a subset of zero cells for \(T\) so that each row and column contains exactly one zero cell.
Activity6.3.4.
We explore some features of the assignment tableau that can help shed light on what an appropriate algorithm would look like.
\(a_{11}\)
\(a_{12}\)
\(a_{13}\)
\(a_{21}\)
\(a_{22}\)
\(a_{23}\)
\(a_{31}\)
\(a_{32}\)
\(a_{33}\)
(a)
If we multiply each entry by \(2\text{,}\) would that change our optimal solution? What about by \(-1\text{?}\) What values \(k\) could I multiply the tableau by to preserve the optimal solution?
(b)
If we add or subtract \(2\) from each entry, does it change the optimal solution? What about \(n\text{?}\)
(c)
Suppose we had an optimal solution to the assignment problem. Explain why adding \(k\) to each entry in a row does not change the optimal solution.
Hint.
How would this compare to solving the original problem and adding \(k\) to the cost?
(d)
What would change if we did this to a different row? A column?
(e)
Suppose I subtracted the smallest value in each row from every entry of that row. If there was a permutation set of zeroes, what would that entail?
(f)
Suppose I subtracted the smallest value in each column from every entry of that column. If there was a permutation set of zeroes, what would that entail?
(g)
If we had a tableau with all rational values, how could I change this to a tableau of all integer values with the same optimal solution?
(h)
If we had a tableau with all integer values, how could I change this to a tableau of all non-negative integer values with the same optimal solution?
Definition6.3.5.
We state here the steps of the Hungarian Algorithm. We start with an \(n\times n\) assignment tableau \(T\text{.}\)
IF the entries of \(T\) are rational but not all integeral, \(a_{ij} =\frac{p_{ij}}{q_{ij}}, q_{ij}>0 \text{:}\)
THEN multiply each entry of \(T\) by the lowest common multiple of the denominators, \(\displaystyle \underset{ i, j}{\lcm} q_{ij}\text{.}\)
IF the entries of \(T\) are not all non-negative:
THEN add to every entry of \(T\) the smallest value of \(T\text{,}\)\(\displaystyle \min_{i,j}a_{ij}\text{.}\)
Subtract from each row the smallest entry in that row.
Subtract from each column the smallest entry in that column.
IF \(T\) has a permutation set of zeroes: STOP
Draw a minimum\(^*\) number of lines through \(T\) covering an entire row or column such that all \(0\)’s are covered.
Let \(M\) be the value of the smallest uncovered entry. Subtract all uncovered entries by \(M\text{,}\) and add \(M\) to the entries corresponding to intersections of the lines.
GOTO 5.
Activity6.3.6.
(a)
In step 6 of Definition 6.3.5, suppose we draw \(k\) lines. Could \(k\) be greater than \(n\text{?}\)
(b)
Suppose that the zeroes of the tableau in a given step do not form a permutation set of zeroes. Show that \(k<n\text{.}\)
(c)
What would it mean if \(k=n\text{?}\)
(d)
Show that step 7 is equivalent to subtracting \(M\) from each uncovered row, and adding \(M\) to each covered column. (Or subtracting \(M\) from each uncovered column, and adding \(M\) to each covered row.)
(e)
Why does step 7 not change the optimal assignment?
Suppose 4 students are picking 4 research topics. The four topics are to be distributed one each amongst the four students. They rated the topics on a scale of 1-10.
Topic 1
Topic 2
Topic 3
Topic 4
Student 1
6
9
10
8
Student 2
2
8
9
7
Student 3
7
7
8
9
Student 4
6
8
9
8
We want to maximize the total “enjoyment”.
(a)
This is a maximization problem, and the assignment problem is a minimization problem, how might we convert it to a minimization problem?
(b)
After converting, use the Hungarian Algorithm Definition 6.3.5 to solve the problem.
