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.

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

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!

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]';