A simple dual algorithm for the generalised assignment problem

✍ Scribed by John M. Wilson

• Publisher: Springer US
• Year: 1997
• Tongue: English
• Weight: 415 KB
• Volume: 2
• Category: Article
• ISSN: 1381-1231
• DOI: 10.1007/bf00132501

✦ Synopsis

A new algorithm for the generalised assignment problem is described in this paper. The dual-type algorithm uses a simple heuristic derived from a relaxation of the problem. The algorithm has been tested on generalised assignment problems of substantial size and compared to an exact integer programming approach and a wellestablished heuristic approach. Computational results look promising in terms of speed and solution quality.