Linear and semi-assignment problems: A core oriented approach

Linear and semi-assignment problems: A core oriented approach

0.00 Avg rating0 Votes
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:
Keywords: programming: travelling salesman
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.