Solving the k-cardinality assignment problem by transformation

The k-cardinality Linear Assignment Problem (k-LAP) with k a given integer is a generalization of the linear assignment problem: one wants to assign k rows (a free choice out of more rows) to k columns (a free choice out of more columns) minimizing the sum of the corresponding costs. For this polynomially solvable problem special algorithms are known based on transformation to min-cost flow or on shortest augmenting paths. We describe a transformation that enables to solve the k-LAP by any standard linear assignment algorithm. The transformation can be modified to solve the group assignment problem as a standard problem. Computational results for random test instances up to size n=500 with various k-values and randomly drawn cost coefficients show that the transformation approach is suited to solve the k-LAP within short computer times on a standard personal computer.