Algorithms and codes for dense assignment problems: the state of the art

The paper considers the classic linear assignment problem with a min-sum objective function, and the most efficient and easily available codes for its solution, We first give a survey describing the different approaches in the literature, presenting their implementations, and pointing out similarities and differences, Then we select eight codes and we introduce a wide set of dense instances containing both randomly generated and benchmark problems. Finally we discuss the results of extensive computational experiments obtained by solving the above instances with the eight codes, both on a workstation with Unix operating system and on a personal computer running under Windows 95. (C) 2000 Elsevier Science B.V. All rights reserved.