LAPJV implementation issue?

lapjv
algorithm
implementation

#1

For a python project, I needed to implement the Jonker-Volgenant linear assignment algorithm:

R. Jonker, A. Volgenant, “A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems”, Computing 38, p 325-340, 1987

I found and tested the MATLAB implementation by Dr. Yi Cao at Cranfield University (http://ch.mathworks.com/matlabcentral/fileexchange/26836-lapjv-jonker-volgenant-algorithm-for-linear-assignment-problem-v3-0) that seems to be working fine.

I then came across your implementation in CellProfiler (lapjy.py, _lapjv.pyx) and tested it as well. In a series of tests, the two implementation returned the same solution (with the same total solution cost).

The cost matrix in the CellProfiler implementation, however, is forced to be square (why?). To solve an assignment problem with following 5x4 cost matrix (it’s MATLAB’s magic(5) without the last column):

costs = [
[17, 24, 1, 8],
[23, 5, 7, 14],
[ 4, 6, 13, 20],
[10, 12, 19, 21],
[11, 18, 25, 2]]

I extended it with a 5th column full of np.Inf:

costs = [
[17, 24, 1, 8, np.Inf],
[23, 5, 7, 14, np.Inf],
[ 4, 6, 13, 20, np.Inf],
[10, 12, 19, 21, np.Inf],
[11, 18, 25, 2, np.Inf]]

The MATLAB solution (0-based for comparison) is:

[2, 1, 0, 4, 3]

whereas the CellProfiler solution is:

[2, 1, 0, 3, 4]

The MATLAB implementation picks the columns with costs: 1, 5, 4, Inf, 2.
The CellProfiler implementation picks the columns with costs: 1, 5, 4, 21, Inf.

Leaving the two Infs aside, the CellProfiler implementation picked a solution with larger global cost. Is there an issue in the implementation? Or am I missing something?


#2

On more comment (and kind of solution to my own problem :wink: ): the MATLAB implementation replaces the Infs with a max cost larger than the maximum cost present in the cost matrix. When I do the same in the CellProfiler implementation, then the solution is the same as in MATLAB.