We consider a generalization of the assignment problem in which an int
eger k is given and one wants to assign k rows to k columns so that th
e sum of the corresponding costs is a minimum. The problem can be seen
as a 2-matroid intersection, hence is solvable in polynomial time; im
mediate algorithms for it can be obtained from transformation to min-c
ost flow or from classical shortest augmenting path techniques. We int
roduce original preprocessing techniques for finding optimal solutions
in which g less than or equal to k rows are assigned, for determining
rows and columns which must be assigned in an optimal solution and fo
r reducing the cost matrix. A specialized primal algorithm is finally
presented. The average computational efficiency of the different appro
aches is evaluated through computational experiments.