bundles / scipy 1.17.1 / scipy / optimize / _lsap / linear_sum_assignment
built-in
scipy.optimize._lsap:linear_sum_assignment
Summary
Solve the linear sum assignment problem.
Parameters
cost_matrix: arrayThe cost matrix of the bipartite graph.
maximize: bool (default: False)Calculates a maximum weight matching if true.
Returns
row_ind, col_ind: arrayAn array of row indices and one of corresponding column indices giving the optimal assignment. The cost of the assignment can be computed as
cost_matrix[row_ind, col_ind].sum(). The row indices will be sorted; in the case of a square cost matrix they will be equal tonumpy.arange(cost_matrix.shape[0]).
Notes
The linear sum assignment problem [1] is also known as minimum weight matching in bipartite graphs. A problem instance is described by a matrix C, where each C[i,j] is the cost of matching vertex i of the first partite set (a 'worker') and vertex j of the second set (a 'job'). The goal is to find a complete assignment of workers to jobs of minimal cost.
Formally, let X be a boolean matrix where iff row i is assigned to column j. Then the optimal assignment has cost
where, in the case where the matrix X is square, each row is assigned to exactly one column, and each column to exactly one row.
This function can also solve a generalization of the classic assignment problem where the cost matrix is rectangular. If it has more rows than columns, then not every row needs to be assigned to a column, and vice versa.
This implementation is a modified Jonker-Volgenant algorithm with no initialization, described in ref. [2].
Examples
import numpy as np cost = np.array([[4, 1, 3], [2, 0, 5], [3, 2, 2]]) from scipy.optimize import linear_sum_assignment row_ind, col_ind = linear_sum_assignment(cost) col_ind✓
cost[row_ind, col_ind].sum()
✗See also
- scipy.sparse.csgraph.min_weight_full_bipartite_matching
for sparse inputs
Aliases
-
scipy.optimize.linear_sum_assignment