bghungar

Hungarian algorithm to solve the square assignment problem.

Description

"Hungarian algorithm" to solve the square assignment problem (original & pure MATLAB implementation). The Hungarian algorithm can also be used as a sub-solver in a B&B solver for the travelling salesman problem.

How to match N (e.g. N=6) pairs of signals from 2 experiments? Build full reordering lists based on the PERMS(1:N) MATLAB function? But the complexity of this approach would be N! = prod(1:6) = 720 for a single run! That of the Hungarian algorithm is just N^3 = 6^3 = 216
i.e. it is many times more efficient!

This code is similar in purpose to the central part of assignprob: hungarian.m, v1.0 96-06-14, adapted by Niclas Borlin, [e-mail].
Unlike latter code which is an adaptation from a 1980 ACM algorithm in Fortran IV, this is original code written directly according to [1], and specially for MATLAB (and very portable across different R's of MATLAB). It has only few, hence efficient lines.

» help bghungar

 BGHUNGAR "Hungarian algorithm" to solve the square assignment problem
 
  ========
  For:
  --------
  C = a square profit/cost matrix.
 
  the call:
  --------
            [izSol, ifail, D] = bghungar(C);
 
  Returns:
  --------
 
  izSol = the optimal assignment: MAXIMIZES total profit
 
  ifail = 0: success;
        > 0: various failure triggers, according to the algorithm's sub-section
 
  D = the square matrix equivalent to C at the end of iteration [1]
 
  ========
  *** Notes:
  1) For assignments that MINIMIZE cost, just invert
         the sign of the cost matrix:
                    ... = bghungar(-C);
 
  2) Coding decisions are annotated, and debugging commands are provided
     (just remove the comments) to resolve intricate use cases.

• MATLAB release: MATLAB 5.3 (R11)

[shunguang wu]

(i) the results is wrong when we try to find the minimum cost by set -C.
(ii)for some data, there is infinite loop inside the code.

[Martin Law]

It helps if the authors add the following line to the documentation on how to interpret the output

% The i-th row is matched to the iz(i)-th column

[kunpeng du]

there exist some data which make the code infinit loop

[Elliot Rice]

I still seem to be able to hang the program by calling [iz, unfeas, D] = bghungar(-C) on
a 14x14 matrix. However, it works well for maximising.

[joel kole]

It seems like a BUG :
please correct me if i wrong :
input : mat = [0.1 0.89 0.74 ; 0.62 0.69 0.28; 0.64 0.95 0.36].'
output = [ 2 1 3]
and the correct output should be = [2 3 1]
am i right ?

[M Ng]

It is quite slow. It took 0.5 second for a random 100*100 matrix. For a 400*400 matrix, it tooks 70s.

It seems to hang out forever for the following matrix: repmat(mat, 2,2) with
mat = [0.1 0.89 0.74 ; 0.62 0.69 0.28; 0.64 0.95 0.36]';

[Nedialko I. Krouchev]

Thanks for the reviews, following the code update in 2004.
Unfortunately, not much truth was contained in them.
Hence, the rather low average review score is therefore an artefact,
which does not reflect the true merits of this algorithm/code.

On the upside and for quite some time now,
bghugar.m has been successfully used within 'serious' academic training
(e.g. http://math.mit.edu/~goemans/18433.html)
which is most rewarding.

Actions taken:

#3 I'd invite Elliot Rice to submit his 14x14 matrix case
so that further analysis can be performed on it.

#2 This native Matlab code is neither meant for, nor can it be made compatible with very large
problems, such as described by M Ng;
The fact that such Matlab code is interpreted, as well as amounts of memory would require
compiled code, optimized for memory use.
As for the test case with a degenerate matrix, suggested by M Ng, it has very limited use.

#1 Tested the case:
C = [0.1 0.89 0.74 ; 0.62 0.69 0.28; 0.64 0.95 0.36];
N.B. Joel Kole claimed obtaining iz = [2 1 3], which is false
see also: t1.m
Pre-Test:
Check the objective value as suggested by Joel Kole:
i = [1 2 3]; j0 = [3 1 2]; j1 = [2 3 1]; k0 = 3*(j0-1) + i; k1 = 3*(j1-1) + i;
[ sum(C(k0)), sum(C(k1)) ]
ans = 2.3100 1.8100
Since we want to maximise the match as suggested by Joel Kole is no solution at all.

#0 Added the line:
The <em>i-th row</em> is matched to the <em>iz(i)-th column </em>.
into the Description

[Nedialko I. Krouchev]

It has held on remarkably well
for the number of issues I found
concerning the style and choices in this algorithmic implementation.
More than 8 years ago I knew far less about Matlab programming, yet it somehow did the job...

However, there will be a refurbished version soon!

[Nedialko I. Krouchev]

Finally the new release!

Let us also use the opportunity to kindly invite
Dr Michel Goemans - a Leighton Family Professor of Applied Mathematics @ MIT,
to kindly acknowledge using this code in his "18.433 Combinatorial Optimization"
course, since the Fall'05 semester.
 
--------

The screen-shot is from the dual-criterion (skills+personal affinity)
team-assignment in my GBM3310 lab class at Ecole Polytechnique de Montreal.

This example brings about a very interesting algorithmic point:
Even if the hybrid performance matrix is asymmetric
(due to the TWO DIFFERENT original costs & their respective weights),
and even if the number of students is ODD,
the solution obtained is as close as it gets to symmetric (*)
and the hybrid performance is better than the alternative Matlab implementation
of the Hungarian method, distributed with EEGLAB.

(*) The 'love-triangle', as indicated by the red crosses,
is the inevitable consequence of the odd number of students used.
However this 'triangle' is formed at the 'end of the list',
where preferences are most 'fuzzy', and 'no-shows' are most likely.