The classical multiple knapsack problem selects a set of items and assigns each to one of the knapsacks so as to maximize the total profit. The knapsacks have limited capacities. The cardinality constrained multiple knapsack problem assumes limits on the number of items that are to be put in each knapsack, as well. Despite many efforts on the classical multiple knapsack problem, the research on the cardinality constrained multiple knapsack problem is scarce.
In this study we consider the cardinality constrained multiple knapsack problem. We propose heuristic and optimization procedures that rely on the optimal solutions of the linear programming relaxation problem. Our computational results on the large-sized problem instances have shown the satisfactory performances of our algorithms.
| Identifer | oai:union.ndltd.org:METU/oai:etd.lib.metu.edu.tr:http://etd.lib.metu.edu.tr/upload/12610131/index.pdf |
| Date | 01 November 2008 |
| Creators | Aslan, Murat |
| Contributors | Azizoglu, Meral |
| Publisher | METU |
| Source Sets | Middle East Technical Univ. |
| Language | English |
| Detected Language | English |
| Type | M.S. Thesis |
| Format | text/pdf |
| Rights | To liberate the content for public access |
Page generated in 0.0021 seconds