Journal of Computer Science

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

Warut Boonphakdee and Peerayuth Charnsethikul

DOI : 10.3844/jcssp.2016.424.435

Journal of Computer Science

Volume 12, Issue 8

Pages 424-435

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 kth 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.

Copyright

© 2016 Warut Boonphakdee and Peerayuth Charnsethikul. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.