scijit.optimize.linear_sum_assignment

scijit.optimize.linear_sum_assignment(cost_matrix, maximize=False)

Solve the linear sum assignment problem.

Choose one entry from each row and each column so that the total is as small as possible: the least-cost way to give nr jobs to nc workers, one each.

Parameters:

cost_matrixarray_like, shape (nr, nc)

Cost matrix. From the interpreter, anything numpy converts to a 2-D numeric array: a list of lists, a tuple of tuples, an integer or boolean array, a Fortran-ordered array, a strided view. A masked array contributes its data and its mask is ignored. Inside @njit it has to be a 2-D array already, of any numeric dtype; strided and Fortran-ordered arrays are accepted there too. An empty matrix is legal and yields two empty index arrays.

maximizebool, optional

If True maximize the total instead of minimizing it. Default False. Implemented by negating the matrix.

Returns:

(row_ind, col_ind)two int64 arrays of length min(nr, nc)

The assignment, as one entry per chosen row and column. row_ind is sorted ascending, and cost_matrix[row_ind, col_ind].sum() is its total cost.

Raises:

ValueError

If cost_matrix has a rank other than 2 once converted; if it holds a NaN or a -inf, checked after the optional negation for maximize; or if no finite perfect matching of the short side exists.

TypeError

If an array is passed whose dtype does not cast to float64 under numpy’s 'safe' rule, such as a complex, object or string array.

See also

scipy.optimize.linear_sum_assignment

The scipy routine this mirrors.

Notes

Solved by the modified Jonker-Volgenant shortest augmenting path algorithm. The tie-breaking rule is fixed so the index pairs are determined, not only the total cost: the work list is filled in reverse order, so a constant cost matrix returns the identity assignment, and among equal shortest-path costs a candidate that opens a new unmatched column wins.

Rank and container are compile-time properties of an argument, so inside @njit a rank other than 2 is a TypingError where the interpreter raises ValueError, and a list or a tuple is a TypingError where the interpreter converts it. The rank refusal carries the rank it was given; the container refusal names cost_matrix and the spelling to use instead.

No module state, no callback and no globals, so many independent assignment problems can be solved concurrently inside a numba.prange loop.

Examples

>>> import numpy as np
>>> from numba import njit
>>> from scijit.optimize import linear_sum_assignment
>>> cost = np.array([[4.0, 1.0, 3.0],
...                  [2.0, 0.0, 5.0],
...                  [3.0, 2.0, 2.0]])
>>> @njit
... def run():
...     return linear_sum_assignment(cost)
>>> row_ind, col_ind = run()
>>> row_ind
array([0, 1, 2])
>>> col_ind
array([1, 0, 2])

From the interpreter the same problem can be written as a list of lists:

>>> linear_sum_assignment([[4, 1, 3], [2, 0, 5], [3, 2, 2]])[1]
array([1, 0, 2])

numba rejects indexing one array with two index arrays, so the total is summed in a loop rather than as cost[row_ind, col_ind].sum():

>>> @njit
... def total():
...     r, c = linear_sum_assignment(cost)
...     s = 0.0
...     for k in range(r.size):
...         s += cost[r[k], c[k]]
...     return s
>>> total()
5.0