bmat ← ##.assign costs                      ⍝ Hungarian method cost assignment.

[assign] is a classic algorithm  implemented in the D style.  H.W.Kuhn published
a  pencil  and paper version in 1955, which was followed by J.R.Munkres' execut-
able  version  in 1957. The algorithm is sometimes referred to as the "Hungarian
method".

The  method  indicates  an  optimal assignment of a set of resources to a set of
requirements,  given  a  "cost"  of  each potential match. Examples might be the
allocation  of workers to tasks; the supply of goods by factories to warehouses;
or the matching of brides with grooms. The function takes a cost matrix as argu-
ment and returns a boolean assignment matrix result.

The  following  table  shows an optimal assignment of factories F, G, H to ware-
houses W, X, Y, given that the cost of transportation from F to W is 72 units, F
to X is 99 units, ···, G to W is 23 units, ··· and so on.

      W    X    Y
    ┌────┬────┬────┐
  F │[72]│ 99 │ 88 │       Minimum-cost assignment marked [.]:
    ├────┼────┼────┤
  G │ 23 │ 30 │[35]│       Factory F supplies warehouse W,
    ├────┼────┼────┤          ··   G   ··  ··  ··  ··   Y,
  H │ 51 │[59]│ 84 │          ··   H   ··  ··  ··  ··   X.
    └────┴────┴────┘

Notice that if the problem requires maximizing a benefit, rather than minimizing
a cost, then a negative cost matrix is used. See below for an example.

Technical notes:

Munkres' algorith may be described in words as follows:

Step 0:
Ensure the costs matrix has at least as many rows as columns, by appending extra
0-item rows if necessary. Go to Step 1.

Step 1:
Subtract the smallest item in each row from the row. Go to Step 2.

Step 2:
Select a set of "independent" zeros in the matrix and mark them with a star (*).
To do this, star leading zeros in each row and column, ignoring rows and columns
already  containing stars; repeat this process until apart from ignored rows and
columns, no more zeros remain. Go to Step 3.

Step 3:
Draw  a  line through (cover) each column containing a starred zero. If all col-
umns  are  covered,  the  starred zeros represent an optimal assignment. In this
case, return a boolean matrix with the positions of the stars, as result. Other-
wise, go to Step 4.

Step 4:
Find  an uncovered zero. If there is none, go to Step 6 passing the smallest un-
covered value as a parameter. Otherwise, mark the zero with a prime (') and call
it  P0. If there is a starred zero (S1) in the row containing P0, cover this row
and  uncover  the column containing S1, then repeat Step 4. Otherwise, (if there
is no starred zero in P0's row) go to Step 5.

Step 5:
Find  a  path  through alternating primes and stars. Starting with the uncovered
prime  (P0) found in Step 4, find a star S1 (if  any) in its column. Then find a
prime  P2  (there  must be one) in S1's row, followed by  a  star S3 (if any) in
P2's  column,  ··· and so on until a prime (Pn) is found that has no star in its
column.  In  the  series P0, S1, P2, S3, ··· Pn, unstar each starred zero Si and
star  each  primed zero Pj. Finally, unprime all primed zeros in the matrix, un-
cover all rows and columns. Go to Step 3.

Step 6:
Add  the  minimum  cost  value passed from Step 4 to each twice-covered (row and
column  covered)  item, and subtract it from each uncovered item. Preserving all
stars, primes and covering lines, go to Step 4.

The approach uses a rather convoluted "stepping algorithm", which can be repres-
ented as a flowchart:

        step0       after step:0, go to step:1.
          ↓
          │
        step1       after step:1, go to step:2.
          ↓
          │
        step2       after step:2, go to step:3.
          ↓
          │
      ┌→step3───→   after step:3, go to step:4 or exit.
      │   │
    ┌─│─→─↓─←───┐
    │ │   │     ↑
    │ │ step4─→─┤   after step:4, go to step:4 or step:5 or step:6.
    ↑ ↑   │     ↓
    │ │   ↓─←─┐ │
    │ │   │   │ │
    │ └─step5─┘ │   after step:5, go to step:5 or step:3.
    ↑     ┌─←───┘
    │     ↓
    │   step6       after step:6, go to step:4.
    │     ↓
    └──←──┘

The algorithm is implemented by coding each step as a separate sub-function, and
tail-calling from one step to the next. This is as close as we come to branching
in D!

Notice  that  nearly  all  of the primitive and defined functions in [##.assign]
deal in matrices - a tribute to APL's native array-handling.

The state is represented by 3 matrices at each step:

    costs:  the current cost matrix.

    zeros:  marked zeros: 0-not a zero, 1-unmarked zero, 2-starred, 3-primed.

    covers: 0-uncovered  item, 1-item covered by horizontal (row covering) line,
            2-item covered by vertical (column covering) line, 3-item covered by
            both horizontal and vertical lines.

In  addition, step 5 takes a boolean matrix left argument, indicating the posit-
ion of the first primed zero.

Using the example cost matrix from above, the following trace shows the state of
play between each step ─[n]─.

  ┌──────────┐   ┌──────────┐   ┌──────────┐   ┌──────────┐   ┌──────────┐
  │72  99  88│   │ 0  27  16│   │*0  27  16│   │*0│ 27  16│   │*0│ 27  16│
  │23  30  35├[1]┤ 0   7  12├[2]┤ 0   7  12├[3]┤ 0│  7  12├[4]┤ 0│  7  12├[6]─··
  │51  59  84│   │ 0   8  33│   │ 0   8  33│   │ 0│  8  33│   │ 0│  8  33│(7)
  └──────────┘   └──────────┘   └──────────┘   └──────────┘   └──────────┘
  ┌──────────┐   ┌──────────┐   ┌──────────┐   ┌──────────┐   ┌──────────┐
  │*0│ 20   9│   │*0│ 20   9│   │*0  20   9│   │*0│ 20│  9│   │*0│ 20│  9│
··┤ 0│  0   5├[4]┤ 0│['0]  5├[5]┤ 0  *0   5├[3]┤ 0│ *0│  5├[4]┤ 0│ *0│  5├[6]─··
  │ 0│  1  26│   │ 0│  1  26│   │ 0   1  26│   │ 0│  1│ 26│   │ 0│  1│ 26│(5)
  └──────────┘   └──────────┘   └──────────┘   └──────────┘   └──────────┘
  ┌──────────┐   ┌──────────┐   ┌──────────┐   ┌──────────┐   ┌──────────┐
  │*0│ 20│  4│   │*0│ 20   4│   │*0│ 19   3│   │*0│ 19   3│   │*0  19   3│
··┤ 0│ *0│  0├[4]┤ 0┼─*0──'0├[6]┤─1┼─*0──'0├[4]┤─1┼[*0]['0├[5]┤ 1   0  *0├[3]─··
  │ 0│  1│ 21│   │ 0│  1  21│(1)│ 0│  0  20│   │ 0│['0] 20│   │ 0  *0  20│
  └──────────┘   └──────────┘   └──────────┘   └──────────┘   └──────────┘
  ┌──────────┐
  │ 1   0   0│
··┤ 0   0   1│
  │ 0   1   0│
  └──────────┘

References:

    H.W.Kuhn, The Hungarian method for the assignment problem, Naval Research
    Logistics Quarterly, 2 (1955), pp. 83-97.

    J.R.Munkres, Algorithms for the assignment and transportation problems,
    J. SIAM 5 (1957) 32-38.

Examples:

      costs                         ⍝ example cost matrix.
72 99 88
23 30 35
51 59 84

      assign costs                  ⍝ minimum cost assignment.
1 0 0
0 0 1
0 1 0

      assign -costs                 ⍝ maximum benefit assignment.
0 1 0
1 0 0
0 0 1

      {+/+/⍵×assign ⍵} costs        ⍝ total minimum cost.
166

      {+/+/-⍵×assign ⍵} -costs      ⍝ total maximum benefit.
206

      costs←?6 10⍴50                ⍝ new 6×10 cost matrix.

      costs
 7 38 23 27 11  3 34 34 47 20
26 42  2  3 27 34  1 20  4 21
35 30 47 43 27  5 33 21 36 46
39 14  3 37 17 32 38 50 19 13
50 37 38 33  4 32 45 14 22 39
24 12 14 18  9 25 45 46  4 46

      assign costs                  ⍝ minimum cost assignment.
1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0

      {⍵×assign ⍵} costs            ⍝ cost per assignment.
7 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 5 0 0 0 0
0 0 3 0 0 0 0 0 0 0
0 0 0 0 4 0 0 0 0 0
0 0 0 0 0 0 0 0 4 0

      {+/+/⍵×assign ⍵} costs        ⍝ total minimum cost.
24

      assign -costs                 ⍝ maximum benefit assignment.
0 0 0 0 0 0 0 0 1 0
0 1 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0
1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1

      {-⍵×assign ⍵} -costs          ⍝ cost per assignment.
 0  0  0 0 0 0 0  0 47  0
 0 42  0 0 0 0 0  0  0  0
 0  0 47 0 0 0 0  0  0  0
 0  0  0 0 0 0 0 50  0  0
50  0  0 0 0 0 0  0  0  0
 0  0  0 0 0 0 0  0  0 46

      {+/+/-⍵×assign ⍵} -costs      ⍝ total maximum benefit.
282

      costs←?10 6⍴50                ⍝ new 10×6 cost matrix

      costs
14  1 21  2 36 47
12 10 16 45 33  8
35 20 20 25  8 30
43 30 48 28  8 50
21  8 29 13 25 24
49  7 10 16 32  7
33 32 41 13 24 20
11  2 46 22  8 48
21  7 45  5  9  4
19 13  7 40 23 18

      assign costs                  ⍝ minimum cost assignment.
0 1 0 0 0 0
1 0 0 0 0 0
0 0 0 0 1 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1
0 0 0 1 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 0 0

See also: Graphs X apportion

Back to: contents

Back to: Workspaces