Applications and Formulation

Hungarian Algorithm
Auction Algorithm

Lecture 4-5: Assignment Problem

Feng Pan
University of Arizona, LANL

1/26/2012, 1/31/2012

Feng Pan

Survey of Optimization Methods

Applications and Formulation

Hungarian Algorithm
Auction Algorithm

Outline

Applications and Formulation

Hungarian Algorithm

Auction Algorithm

Feng Pan

Survey of Optimization Methods

Applications and Formulation

Hungarian Algorithm
Auction Algorithm

Select Swim Team

Form a team for 4 100 medley relay.

Assign swimmers to each stroke:
Swimmer
Mike (1)
Eric (2)
Tom (3)
Jeff (4)

Breaststroke (1)
7
6
5
8

Backstroke (2)
6
10
7
5

Butterfly (3)
5
7
10
6

Find an assignment with the minimum total time.

Feng Pan

Survey of Optimization Methods

Freestyle (4)
5
4
7
10

Applications and Formulation

Hungarian Algorithm
Auction Algorithm

LP Formulation
Let I = {1, 2, 3, 4} be the index set for the swimmers and
J = {1, 2, 3, 4} be the index set for strokes.
Let aij be the average time for 100 meter by swimmer i with
stroke j.
xij is a binary decision variable. xij = 1 if assigning swimmer i to
stroke j.
min
x

s.t.

XX

aij xij

(1)

iI jJ

xij = 1,

i I

(2)

xij = 1,

j J

(3)

i I, j J.

(4)

jJ

X
iI

xij 0,
Feng Pan

Survey of Optimization Methods

Applications and Formulation

Hungarian Algorithm
Auction Algorithm

Job Assignment

There are five factories and four products.

The production rates are given as
Factory
Factory 1
Factory 2
Factory 3
Factory 4
Factory 5

Product 1
12
6
8
9
10

Product 2
6
8
11
12
7

Product 3
8
7
12
6
12

Product 4
7
10
5
11
9

Assign products to factories to achieve the highest production

rate.

Feng Pan

Survey of Optimization Methods

Applications and Formulation

Hungarian Algorithm
Auction Algorithm

LP Formulation
Let I = {1, 2, 3, 4, 5} be the index set for the factories and
J = {1, 2, 3, 4, 5} be the index set for the products with 5 being a
dummy product.
Let aij be production rate of product j at factory i. Set ai5 = 0 for
i I.
xij is a binary decision variable. xij = 1 if factory i manufacture
product j.
max
x

s.t.

XX

aij xij

(5)

iI jJ

xij = 1,

i I

(6)

xij = 1,

j J

(7)

i I, j J.

(8)

jJ

X
iI

xij 0,
Feng Pan

Survey of Optimization Methods

Applications and Formulation

Hungarian Algorithm
Auction Algorithm

Conversion between Max and Min

Consider an N N assignment problem.

Let L maxi,j {aij }.
From max to min,
XX
XX
max
aij xij = (min
(L aij )xij NL).
x

iI jJ

iI jJ

From min to max:

XX
XX
min
aij xij = (max
(L aij )xij NL).
x

iI jJ

Feng Pan

iI jJ

Survey of Optimization Methods

Applications and Formulation

Hungarian Algorithm
Auction Algorithm

Hungarian Algorithm
Given the cost matrix for an n n assignment problem.
1

For each row, subtract the minimum row value.

For each column, subtract the the minimum column value.

Find the minimum number of lines to cover all zeros.

If the minimum number is n, stop and make the optimal

assignment.

Find the minimum value of the uncovered numbers. Update the

cost matrix by
subtracting the uncovered numbers by the minimum value,
keeping the covered numbers the same,
adding the minimum value to the twice covered numbers.

Goto step 3.

Feng Pan

Survey of Optimization Methods

Applications and Formulation

Hungarian Algorithm
Auction Algorithm

Example 1a

2
6
2

3
3
7

0
1
3
0

1
5
6

0
2
0
5

0
0
2
4

1
3
2

For each row, subtract the minimum row value.

For each column, subtract the the minimum column value.
Minimum number of lines to cover 0s is 3.
We found an optimal solution: x13 = 1, x22 = 1, x31 = 1. The
optimal objective is 7.

Feng Pan

Survey of Optimization Methods

Applications and Formulation

Hungarian Algorithm
Auction Algorithm

Subtract Row and Column Minimum

Is an optimal solution to the modified table optimal to the original

table?
Yes. The optimal solutions are the same. The objective values differ
with a constant.
Row subtraction:
X
X
X
aij xij =
(aij )xij =
aij xij , i I
jJ

jJ

jJ

Column subtraction is similar.

Feng Pan

Survey of Optimization Methods

Applications and Formulation

Hungarian Algorithm
Auction Algorithm

Example 1b-1

2
6
7

3
3
2

1
0
2
4

1
5
6

0
2
0
0

0
0
2
4

1
3
2

For each row, subtract the minimum row value.

For each column, subtract the the minimum column value.
Find the minimum number of covering lines is 2.
No a complete assignment.

Feng Pan

Survey of Optimization Methods

Applications and Formulation

Hungarian Algorithm
Auction Algorithm

Example 1b-2
0
2
4

2
0
0

2
4

X
X

Find the minimum number of lines to cover all zeros.

1

For each row with one 0, circle the 0 and cross out the 0s in the
column.

For each column with one 0, circle the 0 and cross out the 0s in
the row.

Check the unassigned rows.

For checked rows, check the columns of 0s in that row.

For checked columns, if there is an assigned 0, check the row.

Repeat 4-5 until no new checked rows or columns.

Feng Pan

Survey of Optimization Methods

Applications and Formulation

Hungarian Algorithm
Auction Algorithm

Example 1b-3
X
0
2
4

2
0
0

0
0

2
4

0
2

X
X

4
0
0

0
2

X
X

Cross out checked columns and unchecked rows: row 1 and

column 2.
It results minimum lines to cover all zeros.
Find the minimum value of the uncovered numbers. Update the
cost matrix by
subtracting the uncovered numbers by the minimum value,
keeping the covered numbers the same,
adding the minimum value to the twice covered numbers.

Feng Pan

Survey of Optimization Methods

Applications and Formulation

Hungarian Algorithm
Auction Algorithm

Example 1b-3

Subtracting the uncovered numbers by the minimum value,

Keeping the covered numbers the same,
Adding the minimum value to the twice covered numbers.
These steps are same as
Subtracting the uncovered rows by the minimum value.
Adding the minimum value to covered column.
Therefore, the steps dont alter optimal solutions.

Feng Pan

Survey of Optimization Methods

Applications and Formulation

Hungarian Algorithm
Auction Algorithm

Example 1b

0
0

0
2

Complete assignment: x11 = 1, x23 = 1, x32 = 1.

Optimal objective is 9.

Feng Pan

Survey of Optimization Methods

Applications and Formulation

Hungarian Algorithm
Auction Algorithm

Primal-Dual Algorithm: Initial Dual Solution

Hungarian algorithm is primal-dual method.
2
6
7

3
3
2

1
0
2
4

1
5
6

0
2
0
0

0
0
2
4

1
3
2

Find feasible dual variables .

Dual variables for rows are u, dual variables for columns are v .
Initial dual feasible solution u = (1, 3, 2) and v = (1, 0, 0).
K is the set of binding dual constraints,
K = {(i, j)|aij ui vj = 0, 1 i 3, 1 j 3}.

Feng Pan

Survey of Optimization Methods

Applications and Formulation

Hungarian Algorithm
Auction Algorithm

Primal-Dual Solution: RP

0
2
4

2
0
0

2
4

X
X

Construct RP an DRP from the above table. Find optimal dual

solution for DRP,
.
Cross out row 1 and column 2.
1 = 1 and v2 = 1 and all other dual variables of DRP to
Set u
1.
The dual objective value is 2.

Feng Pan

Survey of Optimization Methods

Applications and Formulation

Hungarian Algorithm
Auction Algorithm

Update Dual Feasible Solution

0
0
2

4
0
0

0
2

X
X

= +

i + vj = 0 if (i, j) 6= (1, 2), u

1 + v2 = 2.
For covered cell (i, j), u
i + vj 0
Since all 0s are covered, for (i, j) J, u
For (i, j)
/ J and not covered, ui + vj = 2.
Let = min{(cij ui vj )}.
i + vj )} = /2.
= min{(cij ui vj )/(u
i + vj = ui + vj +
u

Feng Pan

Survey of Optimization Methods

Applications and Formulation

Hungarian Algorithm
Auction Algorithm

Update Dual Feasible Solution

0
0
2

4
0
0

0
2

X
X

= +

Subtracting the uncovered rows by the minimum value:

i + vj ) = c12 (u1 + v2 ) .
cij (u
Adding the minimum value to covered column:
1 + v2 ) = c12 (u1 + v2 ) + .
c12 (u

Feng Pan

Survey of Optimization Methods

Applications and Formulation

Hungarian Algorithm
Auction Algorithm

Example 2a

7
6
5
8

6
10
7
5

5
7
10
6

0
2
2
0
3

5
4
7
10

0
1
6
2
0

0
0
3
5
1

0
0
0
2
5

5
4
5
5

For each row, subtract the minimum row value.

For each column, subtract the the minimum column value.
Minimum number of covering lines is 4.
Complete assignment. Optimal objective value is 19.

Feng Pan

Survey of Optimization Methods

Applications and Formulation

Hungarian Algorithm
Auction Algorithm

Example 2b-1

7
7
8
8

6
10
7
6

5
7
10
10

2
0
1
1
1

5
4
5
5

1
0
5
1
0

0
0
3
5
5

0
0
0
0
0

5
4
5
5

For each row, subtract the minimum row value.

For each column, subtract the the minimum column value.

Feng Pan

Survey of Optimization Methods

Applications and Formulation

Hungarian Algorithm
Auction Algorithm

Example 2b-2
2
0
1
1
1

X
5

3
5

0
0

4
5

1
1

5
1
0

5
1
0

3
5

0
0

X
X

Find the minimum number of lines to cover all zeros.

1
For each row with one 0, circle the 0 and cross out the 0s in the
column.
2
For each column with one 0, circle the 0 and cross out the 0s in
the row.
3
Check the unassigned rows.
4
For checked rows, check the columns of 0s in that row.
5
For checked columns, if there is an assigned 0, check the row.
6
Repeat 4-5 until no new checked rows or columns.
Feng Pan

Survey of Optimization Methods

Applications and Formulation

Hungarian Algorithm
Auction Algorithm

Example 2b-3
X
0

1
1

5
1
0

3
5

0
0
0

X
X
X

0
0

4
0
0

2
4

1
0
0

X
X

Cross out checked columns and unchecked rows: row 1, 4, and

column 4.
It results minimum lines to cover all zeros
Find the minimum value of the uncovered numbers. Update the
cost matrix by
subtracting the uncovered numbers by the minimum value,
keeping the covered numbers the same,
adding the minimum value to the twice covered numbers.
Feng Pan

Survey of Optimization Methods

Applications and Formulation

Hungarian Algorithm
Auction Algorithm

Example 2b
7
7
8
8

6
10
7
6

5
7
10
10

5
4
5
5

0
0

0
0

For each row with one 0, circle the 0 and cross out the 0s in the
column.

For each column with one 0, circle the 0 and cross out the 0s in
the row.

Check the unassigned rows.

For checked rows, check the columns of 0s in that row.

For checked columns, if there is an assigned 0, check the row.

Repeat 4-5 until no new checked rows or columns.

Feng Pan

Survey of Optimization Methods

Applications and Formulation

Hungarian Algorithm
Auction Algorithm

Auction Algorithm
Consider a maximum assignment problem.
XX
max
aij xij
x

s.t.

(9)

iI jJ

xij = 1,

i I

(10)

xij = 1,

j J

(11)

i I, j J.

(12)

jJ

X
iI

xij 0,

cij is the prize of item j to person i.

Persons bid for items.
In the end, everyone is happy.
Feng Pan

Survey of Optimization Methods

Applications and Formulation

Hungarian Algorithm
Auction Algorithm

Example 1a-1
Convert Example 1a to a maximum assignment problem. Rows are
people and columns are items. The number cij is the prize of item j to
person i.
6
2
6

5
5
1

7
3
2

For person 1, item 3 has the highest prize.

How much will person 1 bid?
Assume the initial prices for items are (0, 0, 0). To win item 3,
person 1 bids 1.

Feng Pan

Survey of Optimization Methods

Applications and Formulation

Hungarian Algorithm
Auction Algorithm

Auction Algorithm: Bidding Phase

Input Assignment table c, current price for the items (p1 , , pn ), a set
of assigned persons S.
Bidding The profit of item j to person i is
cij pj .
For person i
/ S (unassigned person), assume that j is the item
with highest profit, i.e.,
cij pj = max{cij pj }.
j

The difference between the highest profit and the second highest
profit is
ij = (cij pj ) max
{cij pj }.

j6=j

The largest amount person i is willing to bid on j is the current

price plus ij ,
bij = pj + ij .
Output Bid bij for i
/ S.
Feng Pan

Survey of Optimization Methods

Applications and Formulation

Hungarian Algorithm
Auction Algorithm

Auction Algorithm: Assignment Phase

Input Bid bij for i

/ S.
Assign. Set T includes the items with new bids. For each j T , do
1
2
3

assign j to the person with the highest bid, say i , add i to S,

remove the previous holder of j from S,
set price of j to bi j : pj = bi j .

Output Set of assigned persons S and price (p1 , , pn ).

Feng Pan

Survey of Optimization Methods

Applications and Formulation

Hungarian Algorithm
Auction Algorithm

Auction Algorithm

Initialize S = and pi = 0 for i = 1, , n.

While |S| =
6 n: do
perform the bidding.
perform assignment.

Feng Pan

Survey of Optimization Methods

Applications and Formulation

Hungarian Algorithm
Auction Algorithm

Example 1a-2

6
2
6

5
5
1

7
3
2

Sequential bidding: only one unassigned person bits.

bidding person

bid bij

1
2
3

b13 = 1
b2,2 = 3
b31 = 5

Feng Pan

price
(0,0,0)
(0, 0, 1)
(0,3,1)
(5,3,1)

assignment
{(1, 3)}
{(1, 3), (2, 2)}
{(1, 3), (2, 2), (3, 1)}

Survey of Optimization Methods

Applications and Formulation

Hungarian Algorithm
Auction Algorithm

Example 1a-3

6
2
6

5
5
1

7
3
2

Parallel bidding: every unassigned individual bids

1

Initial costs are (0, 0, 0).

Bidding: b13 = 1, b22 = 2, b31 = 4

Assignment: {(1, 3), (2, 2), (3, 1)} and prices: (1,2,4).

Feng Pan

Survey of Optimization Methods

Applications and Formulation

Hungarian Algorithm
Auction Algorithm

Example 1b-1:Sequential Bidding

The modified prize table:
6
2
1
person

bid bij

1
2
3
2

b13 = 1
b22 = 3
b32 = 3 + 2
b21 = 0

5
5
6

7
3
2

price
(0,0,0)
(0,0,1)
(0,3,1)
(0,5,1)
(0,5,1)

Feng Pan

assignment
{(1, 3)}
{(1, 3), (2, 2)}
{(1, 3), (3, 2)}
{(1, 3), (3, 2), (2, 1)}

Survey of Optimization Methods

Applications and Formulation

Hungarian Algorithm
Auction Algorithm

Example 1b-2: Parallel Bidding

6
2
1
1
2
3

5
5
6

7
3
2

Initial costs are (0, 0, 0).

Bidding: b13 = 1, b22 = 2, b32 = 4.
Assignment (Item 2 and 3 have bid.):
The highest bid of item 2 is 4, assign it to person 3, and p2 = 4.
The highest bid of item 3 is 1, assign it to person 1, andp3 = 1.

4
5

Assignment: {(1, 3), (3, 2)}, assigned individuals: S = {1, 3},

and the price: (0, 4, 1).
Bidding: b21 = 0.
Assignment: Item 1 has bid. The highest bid of item 1 is 0 and
assign it to person 2. Set price p1 = 0.
Assignment: {(1, 3), (2, 1), (3, 2)}, assigned individuals:
S = {1, 2, 3}, and the price: (0, 4, 1).
|S| = 3, stop.
Feng Pan

Survey of Optimization Methods

Applications and Formulation

Hungarian Algorithm
Auction Algorithm

Example 1b-2: Infinite Loops

6
2
1

5
5
6

7
3
2

Not so ideal case:

person

bid bij

1
2
3
2
1
2

b13 = 1
b22 = 3
b32 = 3 + 2
b23 = 1 + 0
b13 = 1 + 0
b23 = 1 + 0
..
.

price
(0,0,0)
(0,0,1)
(0,3,1)
(0,5,1)
(0,5,1)
(0,5,1)
(0,5,1)

assignment
{(1, 3)}
{(1, 3), (2, 2)}
{(1, 3), (3, 2)}
{(2, 3), (3, 2)}
{(1, 3), (3, 2)}
{(2, 3), (3, 2)}

Naive bidding may cause an endless loop.

Feng Pan

Survey of Optimization Methods

Applications and Formulation

Hungarian Algorithm
Auction Algorithm

Nonzero Increment in Bid

Zero price increment causes problems.
Add  amount to every bid, where  > 0.
In the bidding phase,
The difference between the highest profit and the second highest
profit is
{cij pj }.
ij = (cij pj ) max

j6=j

The largest amount person i is willing to bid on j is the current

price plus ij ,
bij = pj + ij + .

A new happiness definition

complementary slackness
An assignment (i, j) satisfies complementary slackness if
cij pj max {cik pk } .
kA(i)

Feng Pan

Survey of Optimization Methods

Applications and Formulation

Hungarian Algorithm
Auction Algorithm

Example 1b-3
Two items have the same value for two persons. Bidding price is
not changing.
Break the tie by adding  = 0.2 to each bid.
6
2
1

person

bid bij

1
2
3
2

b13 = 0 + 1 + 0.2
b22 = 0 + 3 + 0.2
b32 = 3.2 + 1.8 + 0.2
b21 = 0 + 0.2 + 0.2
Feng Pan

5
5
6

7
3
2

price
(0,0,0)
(0,0,1.2)
(0,3.2,1.2)
(0,5.2,1.2)
(0.4,5.2,1.2)

assignment
{(1, 3)}
{(1, 3), (2, 2)}
{(1, 3), (3, 2)}
{(1, 3), (3, 2), (2, 3)}

Survey of Optimization Methods

Applications and Formulation

Hungarian Algorithm
Auction Algorithm

Some Properties of Auction Algorithm

At each each iteration, complementary slackness is satisfied.

Once an item is assigned, item remains assigned throughout the
algorithm.
Each bid increases an item price by a positive amount.
The profit for a person is decreasing after a number of bids.
The algorithm terminates at a feasible solution within n of being
optimal.

Feng Pan

Survey of Optimization Methods