Determining the K-best solutions of knapsack problems |
| |
| Affiliation: | 1. Department of ECE, SRM Institute of Science and Technology, Vadapalani, Chennai, Tamil Nadu, India;2. Department of ECE, SRM Institute of Science and Technology, Kattankulathur, Chennai, Tamil Nadu, India;1. Huazhong Agricultural University, Wuhan, Hubei, China;2. Wuhan Vocational College of Software and Engineering, Hubei, China;3. Huazhong Agricultural University, Wuhan, Hubei, China;4. Huazhong Agricultural University, Wuhan, Hubei, China;1. Operations Research Center, MIT, 77 Massachusetts Ave, Cambridge, MA 02139, USA;2. Civil & Environmental Engineering, MIT, 77 Massachusetts Ave, Cambridge, MA 02139, USA;3. Electrical Engineering & Computer Science, MIT, 77 Massachusetts Ave, Cambridge, MA 02139, USA |
| |
| Abstract: | It is well-known that knapsack problems arise as subproblems of a number of large-scale integer optimization problems. In order to solve these large problems, it is necessary to solve the subproblems efficiently, and for many of them it can be useful to determine the K-best solutions. In this paper, a branch-and-bound method for the unbounded knapsack problem described in the literature is extended to determine the K-best solutions of unbounded and bounded knapsack problems. We show that the proposed extension determines exactly the K-best solutions and we solve important classical instances using high values of K. |
| |
| Keywords: | Knapsack problems Branch-and-bound Best solutions |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
