Solving the k-cardinality assignment problem by transformation

Solving the k-cardinality assignment problem by transformation

0.00 Avg rating0 Votes
Article ID: iaor20052319
Country: Netherlands
Volume: 157
Issue: 2
Start Page Number: 322
End Page Number: 331
Publication Date: Sep 2004
Journal: European Journal of Operational Research
Authors:
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.