Hungarian algorithm as a linear programme

Hungarian algorithm as a linear programme

Spec 2.2 · Edexcel A-Level Further Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • Let xij=1x_{ij}=1 if worker ii does task jj and 0 otherwise: first subscript worker, second task.
  • Minimise cost ∑∑cijxij\sum\sum c_{ij}x_{ij}, or maximise profit ∑∑pijxij\sum\sum p_{ij}x_{ij} directly.
  • Each worker does exactly one task and each task is done by exactly one worker: 2n2n equalities, n2n^2 variables.
  • More workers than tasks: each worker does at most one task.
  • An LP can add conditions the Hungarian algorithm cannot.

Turning it into an LP

Use a binary variable xijx_{ij} for each worker and task pairing: 1 if worker ii does task jj, 0 otherwise.

For nn workers and nn tasks define a binary variable for every pairing:

xij={1if worker i does task j,0otherwise.x_{ij}=\begin{cases}1&\text{if worker }i\text{ does task }j,\\0&\text{otherwise.}\end{cases}

The first subscript is the worker (row of the matrix) and the second is the task (column).

A complete allocation is a choice of values of xijx_{ij}, and the cost is read from the cost matrix.

  • xij=1x_{ij}=1worker ii does task jj
  • First subscriptworker (row)
  • Second subscripttask (column)

What does x32=1x_{32}=1 mean?

The objective function

Only chosen pairings add their cost, so the total is ∑∑cijxij\sum\sum c_{ij}x_{ij}. Minimise it, or maximise profit directly.

Only chosen pairings (xij=1x_{ij}=1) add their cost, so the total cost is

∑i=1n∑j=1ncijxij.\sum_{i=1}^{n}\sum_{j=1}^{n}c_{ij}x_{ij}.

To minimise cost, minimise this. For maximum profit use profits pijp_{ij} and maximise ∑∑pijxij\sum\sum p_{ij}x_{ij}. No conversion is needed in an LP.

  • Minimise cost∑∑cijxij\sum\sum c_{ij}x_{ij}
  • Maximise profit∑∑pijxij\sum\sum p_{ij}x_{ij}

Worked example

Write the objective function for the costs (6985)\begin{pmatrix}6&9\\8&5\end{pmatrix}.

For a profit matrix, what do you do to the objective function?

The constraints

Each worker does exactly one task and each task is done by exactly one worker, with xij∈{0,1}x_{ij}\in\{0,1\}.

Each worker does exactly one task and each task is done by exactly one worker.

  • For each worker ii: xi1+xi2+⋯+xin=1x_{i1}+x_{i2}+\dots+x_{in}=1 (nn constraints).
  • For each task jj: x1j+x2j+⋯+xnj=1x_{1j}+x_{2j}+\dots+x_{nj}=1 (nn constraints).

Also xij∈{0,1}x_{ij}\in\{0,1\}. That is 2n2n equality constraints and n2n^2 variables.

For 3×33\times3: worker 2 gives x21+x22+x23=1x_{21}+x_{22}+x_{23}=1, and task 3 gives x13+x23+x33=1x_{13}+x_{23}+x_{33}=1.

Each worker

Constraint:
xi1+⋯+xin=1x_{i1}+\dots+x_{in}=1
How many:
nn constraints

Each task

Constraint:
x1j+⋯+xnj=1x_{1j}+\dots+x_{nj}=1
How many:
nn constraints

How many equality constraints and variables does a 4×44\times4 allocation problem have?

Unequal numbers and impossible pairings

More workers than tasks means each worker does at most one task. An impossible pairing is left out or set to 0.

Unequal numbers. With more workers than tasks, every task is done exactly once, but each worker does at most one: xi1+⋯+xin≤1x_{i1}+\dots+x_{in}\le1. Equalities for every worker would be impossible. This does the same job as a dummy task.

Impossible pairing. If worker ii cannot do task jj, leave xijx_{ij} out, or add xij=0x_{ij}=0. This does the same job as the large number MM.

Maximising. Keep the profit matrix and maximise ∑∑pijxij\sum\sum p_{ij}x_{ij}.

More workers than tasks

In the LP:
Workers: at most one task
In the algorithm:
Dummy task

Impossible pairing

In the LP:
Leave out xijx_{ij} or set it 0
In the algorithm:
Large number MM

Maximising

In the LP:
Maximise profits directly
In the algorithm:
Subtract from largest

There are 4 workers and 3 tasks. What is the constraint for worker ii?

A worked example

An LP can add any linear condition, such as x11+x33≤1x_{11}+x_{33}\le1, which is not a row or column condition.

Three technicians and three tasks have profits as shown (a dash means impossible).

The best choice is x11=x22=x33=1x_{11}=x_{22}=x_{33}=1 with profit 14+13+12=3914+13+12=39.

A condition such as x11+x33≤1x_{11}+x_{33}\le1 (the two pairings cannot both be used) is not a row or column condition, so the Hungarian algorithm cannot handle it, but it can be added to the LP.

It rules out the best allocation. The best remaining is x13=x22=x31=1x_{13}=x_{22}=x_{31}=1 with profit 9+13+10=329+13+10=32.

Task 1

Technician 1:
14
Technician 2:
8
Technician 3:
10

Task 2

Technician 1:
11
Technician 2:
13
Technician 3:
7

Task 3

Technician 1:
9
Technician 2:
–
Technician 3:
12

Worked example

Formulate the profit matrix as an LP.

The extra condition x11+x33≤1x_{11}+x_{33}\le1 is added. What is the new maximum profit?

Try an exam question

A 3×33\times3 allocation problem has cost matrix entries cijc_{ij} for worker ii doing task jj. Formulate the minimum-cost allocation as a linear programme, defining your variables.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

What does x23=1x_{23}=1 mean?

1 mark, marked against the mark scheme

Revision notes