LinearAssignmentSolver<T>

Models & Types · AiDotNet.Solvers.Assignment

Solves the linear assignment problem: pair every row with a distinct column so that the total cost is as small as possible.

For Beginners

You have workers and jobs, and a table of what each worker costs on each job. Every worker takes exactly one job and every job goes to exactly one worker. Picking the cheapest pair, then the cheapest of what remains, and so on feels sensible but is provably not the best plan — the cheap pair you grabbed first may have been the only affordable option for a job that now costs a fortune. This finds the genuinely cheapest overall plan.

How It Works

Implements the Hungarian algorithm (Kuhn, 1955; Munkres, 1957) in its O(n³) shortest-augmenting- path form, generalized to rectangular cost matrices. The result is the globally optimal assignment, not a good one.

The assignment problem is a linear program whose constraint matrix is totally unimodular, which is why its linear relaxation always has an integral optimum and why a specialized combinatorial algorithm can solve it exactly in polynomial time. The greedy alternative — repeatedly taking the cheapest remaining pair — is not optimal, and the gap is not a rounding detail: committing early to a locally cheap pair can force an arbitrarily expensive one later.

Constructors

Constructor Summary
LinearAssignmentSolver()

Methods

Method Summary
T TotalCost(Matrix<T> cost, Vector<int> assignment) Returns the total cost of an assignment produced by Solve.
Vector<int> Solve(Matrix<T> cost) Finds the minimum-cost assignment of rows to columns.