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?