Article ID: | iaor2001908 |
Country: | Netherlands |
Volume: | 123 |
Issue: | 2 |
Start Page Number: | 325 |
End Page Number: | 332 |
Publication Date: | Jun 2000 |
Journal: | European Journal of Operational Research |
Authors: | Martello Silvano, Toth Paolo, Pisinger David |
Keywords: | programming: dynamic, programming: integer |
While the 1980s were focused on the solution of large sized ‘easy’ knapsack problems (KPs), this decade has brought several new algorithms, which are able to solve ‘hard’ large sized instances. We will give an overview of the recent techniques for solving hard KPs, with special emphasis on the addition of cardinality constraints, dynamic programming, and rudimentary divisibility. Computational results, comparing all recent algorithms, are presented.