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 primaldual 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
nonnegative. 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. 
