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, 325340, 1987,
and
A. Volgenant, Linear and Semi Assignment Problems: a core oriented approach,
Computers & Operations Research 23 917932, 1996.
The codes solve, respectively, the semiassignment 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 A.Volgenant@uva.nl 




Code SEMIMOD for the semiassignment problem 


Code LAPJVRCT for linear assignment problems on rectangular matrices 



Download sizes: 3 Kb, 2 Kb 

Language: Pascal 
