A Successive Admissible Cell Method for Solving Large Scale Linear Assignment Problem with Dense Cost Matrix

Abstract

Normally, the Linear Assignment Problem (LAP) has been solved by successful algorithms such as Lapjv and Munkres programmed as MATLAB codes. This study presented an improved algorithm for solving large scale LAP. A preprocessing (PP) algorithm was proposed to apply for constructing the k^th transferred reduced cost matrix then this matrix was solved by Lapjvalgorithm. Performances of PP-Lapjvalgorithm were faster than theoriginal Lapjv about 1.90-8.20% when problem sizes are expanded from problem sizes 18000 to 34000 on integer number range [1,10] and [1,1000]. On the other hand, PP-Lapjvalgorithm was inefficient on integer number range [1, 1000000] due to more time-consuming for executing Lapjv.m file in PP-Lapjvalgorithm. The enlargement of number ranges is influenced to the average computation time of Lapjvalgorithm raised about 53.63% and 32.05% when the range is expanded from [1,1000] to [1,1000000] on problem sizes 18000 and 30000,respectively. The limitations of problem size were determined by virtual memory of the tested computer that both algorithms enabled to solve at the maximum problem size of 34000.