Linear Assignment Problem - Freeware

  Codes SEMIMOD and LAPJVRCT: Jonker and Volgenant (direct download)  

  These codes are based on, or derived from, the algorithms described in R. Jonker and A. Volgenant, A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems, Computing 38, 325-340, 1987, and A. Volgenant, Linear and Semi Assignment Problems: a core oriented approach, Computers & Operations Research 23 917-932, 1996. The codes solve, respectively, the semi-assignment problem (see Section 5.4.3) and the linear assignment problem on rectangular matrices (see Section 5.4.4). The choice of the constant inf has to be such that it is much larger than the largest cost coefficient. The cost matrices are defined for integers. Defining them for reals is possible, although other variable types have to be changed too. Further, a tolerance interval has to be chosen to be used when comparing two real values. The effect of using real cost values on the speed of the algorithm will depend on the used computer. Comments and remarks on the use of the algorithms are appreciated by the authors. Contact
  Code SEMIMOD for the semi-assignment problem
  Code LAPJVRCT for linear assignment problems on rectangular matrices
  Download sizes: 3 Kb, 2 Kb
  Language: Pascal