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.