Assignment problem

Formulation of the assignment problem.

Application of the simplex method.
Hungarian method.

Assignment problem
Trace back to the origins of linear programming.
This is a special case of the transportation problem and, by
consequently, from the minimum cost flow problem.
The problem consists of assigning the elements of a set to those
from another set according to a bijective approach (one to one)
so that the total cost of the assignments is minimized.
n n
Min Z = cijxij where xij= 1 if i is assigned to j
i=1j=1 0 otherwise.
n
xij= 1  i = 1, 2, …, n cijallocation cost
j=1 from i to j.
n
xij= 1  j = 1, 2, …, n
i=1
xij= 0 or 1  i, j
2
 Network
of a
problem
generic
of allocation jandtask
of (receives only 1 unit of flow)
n employees ieemployee
à emits only 1 unit
n tasks the nice

3
Notes:

Les 2 ensembles à jumeler sont de même taille.

If this is not the case, we can remedy it by adding some

fictitious elements (vertices) and defining cij= 0I or I fictitious.

If i cannot be assigned to j for any reason, then put cij=

and xijwill be 0 in any optimal flow.

Assignment problem 4
Example:
Suppose that in a company, n workers can work
indifferently on n machines, but with more or less efficiency;
efficiency can be measured by the income from the sale of
products made by the various workers working on the different
machines.

Distributing the workers on the machines in the most efficient way is

an assignment problem.

Let n units to be assigned to n tasks; one unit can only be assigned to

a task and a task can only employ one unit.

The unit i performs task j with a cost or profit cij.

How should each unit be assigned to a single task so that the

5
is profitability optimal?
Solution techniques:
Adaptation of the simplex method

The properties of the constraint matrix allow us

to use the simplex method to solve this programming problem
linear in integer numbers.
Disadvantages:

This leads to very large arrays (of order n).

The solution is highly degenerate, i.e. it contains a

the number of positive variables much less than 2n–1,
let n.
The simplex method can be applied but certain
iterations have no impact on the feasible solution
current. Only the base changes: a variable outside the base is
exchanged with a degenerate base variable. 6
Enumeration of all possible solutions.

n=5 120 feasible solutions.

n = 20 A calculator analyzing an assignment by

microsecond working 8 hours a day and
365 days per year would require 2500 centuries for
this work.

Special technique taking into account the particular structure

of the assignment problem.
Hungarian method developed by the mathematician Kuhn.

Kuhn, H.W. "The Hungarian Method for the Assignment Problem".

Naval Research Logistics Quarterly, Vol. 2, pp. 83-97, 1955.

Assignment problem 7
Hungarian method ("primal-dual method")

Custom-tailored algorithm for the assignment problem whose

the main lines are:

start with a feasible solution to the dual problem;

(2) try to determine an assignment (a solutioninachievable

of primal) while respecting the conditions related to
complementary gaps;
if such an assignment is found, the algorithm terminates;
otherwise, we modify the feasible solution of the dual to
approaching an optimal assignment, etc.

Assignment problem 8
Theorem: The original problem is equivalent in the sense of the set.
optimal solutions to the following problem:
n n
Min Z = c'ijxij
i=1j=1
n
xij= 1  i = 1, 2, …, n
j=1
n
xij= 1  j = 1, 2, …, n
i=1
xij= 0 or 1  i, j

where is itij= cij–ui- vj (uiand vjare arbitrary constants)

We can decrease or increase all costs by the same amount.

from the same row (or the same column) without changing the solution
9
optimal of an assignment problem.
Theorem:

The dual of the original problem has the following feasible solution:

ui= min {cij| j = 1, 2, …, n}

vj= min {cijui| i = 1, 2, …, n}.

Let (u,v) be a dual feasible solution, each component of the vector

the relative cost is of the form: cij= cij-ui -vj.

The optimality conditions of the assignment problem are:

xij= 1 the reduced costijequals zero.

Definition: In the cost matrix of the assignment problem, the

case (i, j) is admissible if cij= cij–ui–vj= 0
10
otherwise it is unacceptable.
To try to find a flow x = (xijsatisfying the conditions
of optimality, it is about creating a bipartite graph with 2n + 2 vertices:
admissible arcs
Sources Destinations

1 1

capacity 1
capacity 1 2 2
capacity 1
1 .
s . t

. .

capacity 1 . .
. . capacity 1

n n

An arc (i, j) intermediate between the sources and the destinations exists.
11
if cij= 0 and it has infinite capacity.
The search for an assignment x consists of finding a maximum flow.
from s to t in the previous network using Ford's algorithm
Fulkerson.

If the maximum flow is equal to n,

So the flow in the arcs between the sources and the destinations is
an optimal allocation
otherwise there are not enough intermediate arcs or boxes
admissible.

In order to increase the flow between s and t, it is necessary to create additional arcs.
between the marked sources and the unmarked destinations
marked:
we put = min {cij | I marked, I unmarked.

Note: 0 because the boxes considered in the minimization are

inadmissible. Assignment problem 12
Creation of a new feasible solution of the dual:

uI= ui- if it is not marked

uiif it is marked.

vj= vj+ if j is not marked

vj if j is marked.

The dual solution (u,v) then allows us to calculate the new

reduced cost matrix
cij= cij-ui–vj= c'ij .

Thus, the new relative cost is equal to the old one. or zero, according to
the status of vertices i and j.

Assignment problem 13
 Description of the Hungarian method in a form that allows for
perform all calculations in the data matrix of the problem:

Subtract the minimum element of row i from each element

from row i, for all i = 1, 2, ..., n.

2. Subtract the minimum element of column j from each element

from column j, for all j = 1, 2, ..., n.

3. Examine the rows starting from the first. If there is a

row containing only one unmarked zero, then mark
this zero by framing it to denote an assignment. Eliminate the
other zeros in the same column by marking them (gray boxes).

Répéter ce processus jusqu'à ce que toutes les rangées ne

contain no unmarked zero or at least two zeros
unmarked.
Assignment problem 14
4. Examine the columns starting from the first. If there is a
column with a single unmarked zero, then mark this zero
by enclosing it to denote an assignment. Eliminate the others
unmarked zeros in the same row by marking them (boxes
grays). Repeat this process until all the columns
contain no unmarked zero or at least two zeros
unmarked.
5. Repeat steps 3 and 4 successively until one of the
three conditions must be met.
(a) Each row has an assignment; then this
allocation is optimal. The algorithm ends.
There are at least two unmarked zeros in each
row and each column; then make an assignment
arbitrary to one of these zeros by framing and eliminating
all the other zeros in the same row and the same
marking them (grey boxes) then go to 3.
(c) There are no unmarked zeros and an assignment
completion has not been done; so move on to step 6.15
6. Check all the rows for which assignments
were not made.
7. To check all the columns not yet checked and that have a
zero in checked rows.
8. To check all the rows not yet checked and that have some
affectations in checked columns.
9. Repeat steps 7 and 8 until it is no longer possible to
coach.
10. Draw a line through all the unchecked rows and
all the checked columns.
11. Among all the elements of the matrix that are not covered by
a line, choose the smallest element and subtract it from each
uncovered element and add it to each doubly
covered (by a vertical and horizontal line).
Return to step 3.
Assignment problem 16
Example:
Consider the assignment problem with the following cost matrix:
9 12 9 6 9 6 9 10

7 8 5 4 3 8 15 5

6 3 16 18 3 19 6 8

6 1 17 6 5 11 7 9

5 0 13 4 5 6 1 2

12 13 4 12 3 1 12 14

3 12 3 7 13 6 8 3

13 4 1 5 5 5 4 9

Assignment problem 17
By applying steps 1 and 2, we obtain:

3 6 3 0 3 0 2 4

4 5 2 1 0 5 11 2

3 0 13 15 0 16 2 5

5 0 16 5 4 10 5 8

5 0 13 4 5 6 0 2

11 12 3 11 2 0 10 13

0 9 0 4 10 3 4 0

12 3 0 4 4 4 2 8

Assignment problem 18
By applying step 3, we obtain:
3 6 3 0 3 0 2 4

4 5 2 1 0 5 11 2

3 0 13 15 0 16 2 5

5 0 16 5 4 10 5 8

5 0 13 4 5 6 0 2

11 12 3 11 2 0 10 13

0 9 0 4 10 3 4 0

12 3 0 4 4 4 2 8

Assignment issue 19
By applying step 4, we obtain:

3 6 3 0 3 0 2 4

4 5 2 1 0 5 11 2

3 0 13 15 0 16 2 5

5 0 16 5 4 10 5 8

5 0 13 4 5 6 0 2

11 12 3 11 2 0 10 13

0 9 0 4 10 3 4 0

12 3 0 4 4 4 2 8

Assignment problem 20
No unmarked zero and a complete assignment has not been made;
skip to steps 6 to 9.
3 6 3 0 3 0 2 4

4 5 2 1 0 5 11 2

3 0 13 15 0 16 2 5

5 0 16 5 4 10 5 8

5 0 13 4 5 6 0 2

11 12 3 11 2 0 10 13

0 9 0 4 10 3 4 0

12 3 0 4 4 4 2 8

Assignment problem 21
Let's now apply step 10.

3 6 3 0 3 0 2 4

4 5 2 1 0 5 11 2

3 0 13 15 0 16 2 5

5 0 16 5 4 10 5 8

5 0 13 4 5 6 0 2

11 12 3 11 2 0 10 13

0 9 0 4 10 3 4 0

12 3 0 4 4 4 2 8

Assignment problem 22
Let's apply step 11. The smallest element is 1.
3 7 3 0 4 0 2 4

3 5 1 0 0 4 10 1

2 0 12 14 0 15 1 4

4 0 15 4 4 9 4 7

5 1 13 4 6 6 0 2

11 13 3 11 3 0 10 13

0 10 0 4 11 3 4 0

12 4 0 4 5 4 2 8

Assignment problem 23
Let's go back to steps 3 and 4.
3 7 3 0 4 0 2 4

3 5 1 0 0 4 10 1

2 0 12 14 0 15 1 4

4 0 15 4 4 9 4 7

5 1 13 4 6 6 0 2

11 13 3 11 3 0 10 13

0 10 0 4 11 3 4 0

12 4 0 4 5 4 2 8

Assignment problem 24
No unmarked zero and a complete assignment has not been made;
move to steps 6 to 9.
3 7 3 0 4 0 2 4

3 5 1 0 0 4 10 1

2 0 12 14 0 15 1 4

4 0 15 4 4 9 4 7

5 1 13 4 6 6 0 2

11 13 3 11 3 0 10 13

0 10 0 4 11 3 4 0

12 4 0 4 5 4 2 8

25
Let's apply step 10.

3 7 3 0 4 0 2 4

3 5 1 0 0 4 10 1

2 0 12 14 0 15 1 4

4 0 15 4 4 9 4 7

5 1 13 4 6 6 0 2

11 13 3 11 3 0 10 13

0 10 0 4 11 3 4 0

12 4 0 4 5 4 2 8

26
Let's apply step 11. The smallest element is 1.
2 7 2 0 4 0 1 3

2 5 0 0 0 4 9 0

1 0 11 14 0 15 0 3

3 0 14 4 4 9 3 6

5 2 13 5 7 7 0 2

10 13 2 11 3 0 9 12

0 11 0 5 12 4 4 0

12 5 0 5 6 5 2 8

Assignment problem 27
We return to steps 3 and 4.
2 7 2 0 4 0 1 3

2 5 0 0 0 4 9 0

1 0 11 14 0 15 0 3

3 0 14 4 4 9 3 6

5 2 13 5 7 7 0 2

10 13 2 11 3 0 9 12

0 11 0 5 12 4 4 0

12 5 0 5 6 5 2 8

Assignment problem 28
Each row has an assignment; it is therefore optimal.

The algorithm is finished and we have:

x14= x28= x35= x42= x57= x66= x71= x83= 1; 0 elsewhere.

Assignment problem 29