Linear Assignment Problem - Freeware

  Code CTCS: Carpaneto and Toth (direct download)  

  The initialization phase is identical to that of APC. If the number of assignments in the primal partial solution is smaller than 0.6 n, a standard shortest path technique is used to complete the solution. Otherwise, the algorithm constructs a sparse matrix by heuristically selecting a subset of elements from the original cost matrix C.
Using a sparse implementation of the shortest path search, an attempt is made to complete the solution: if a complete assignment does not exists on the sparse matrix, some elements from C are heuristically added and the process is iterated. If instead an optimal primal-dual pair for the sparse matrix is found, it is necessary to verify if this is optimal for C: specifically, a check is performed to test if all the reduced costs on C are non-negative. If there are negative reduced costs, the corresponding elements are added to the sparse matrix and the process is iterated. CTCS is a Fortran subroutine that receives the complete cost matrix describing the input instance as a formal parameter.
  Code CTCS
  Download size: 6 Kb
  Language: Fortran
  Download freeware Fortran compilers and IDEs here.