optimization Package

linear_assignment Module

This module contains an algorithm to solve the Linear Assignment Problem

class LinearAssignment(costs, epsilon=-1e-06)

Bases: object

This class finds the solution to the Linear Assignment Problem. It finds a minimum cost matching between two sets, given a cost matrix.

This class is an implementation of the LAPJV algorithm described in: R. Jonker, A. Volgenant. A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems. Computing 38, 325-340 (1987)

Args:

costs:

The cost matrix of the problem. cost[i,j] should be the cost of matching x[i] to y[j]. The cost matrix must be square

epsilon:

tolerance for determining if solution vector is < 0

min_cost

Returns the cost of the best assignment