Article ID: | iaor19972079 |
Country: | United Kingdom |
Volume: | 23 |
Issue: | 10 |
Start Page Number: | 917 |
End Page Number: | 932 |
Publication Date: | Oct 1996 |
Journal: | Computers and Operations Research |
Authors: | Volgenant A. |
Keywords: | programming: travelling salesman |
A Linear Assignment Problem (LAP) with a dense cost matrix can be solved by first making this matrix sparse, i.e. the problem is solved on the core of the matrix. For a known LAP algorithm the paper gives the related modifications. Computational results show that the algorithm is then suited to solve large problems. A standard personal computer can solve problem instances up to size 2000 within about 75 seconds. Furthermore, the paper describes versions of the algorithm for non-square problems as well as for semi-assignment problems; computational results for problem instances up to size 2500 show again the success of the core oriented approach for assignment problems.