An exact decomposition algorithm for the generalized knapsack sharing problem. (English) Zbl 1346.90699
Summary: This paper presents an exact algorithm for solving the knapsack sharing problem with common items. In literature, this problem is also denominated the Generalized Knapsack Sharing Problem (GKSP). The GKSP is NP-hard because it lays on the 0-1 knapsack problem and the knapsack sharing problem. The proposed exact method is based on a rigorous decomposition technique which leads to an intense simplification of the solution procedure for the GKSP. Furthermore, in order to accelerate the procedure for finding the optimum solution, an upper bound and several reduction strategies are considered. Computational results on two sets of benchmark instances from literature show that the proposed method outperforms the other approaches in most instances.
Software:
KnapsackReferences:
| [1] | Boyer, V.; Baz, D. E.; Elkihel, M., A dynamic programming method with lists for the knapsack sharing problem, Computers & Industrial Engineering, 61, 274-278 (2011) |
| [2] | Brown, J. R., The knapsack sharing, Operations Research, 27, 341-355 (1979) · Zbl 0394.90065 |
| [3] | Conejo, A. J.; Castillo, E.; Minguez, R.; Garcia-Bertrand, R., Decomposition techniques in mathematical programming - Engineering and science applications (2006), Springer-Verlag: Springer-Verlag Berlin, Heidelberg · Zbl 1186.90002 |
| [4] | Fujimoto, M.; Yamada, T., An exact algorithm for the knapsack sharing problem with common items, European Journal of Operational Research, 171, 693-707 (2006) · Zbl 1090.90162 |
| [5] | Haddar, B.; Khemakhem, M.; Hanafi, S.; Wilbaut, C., A hybrid heuristic for the 0-1 knapsack sharing problem, Expert Systems with Applications, 42, 10, 4653-4666 (2015) |
| [6] | Haddar, B.; Khemakhem, M.; Rhimi, H.; Chabchoub, H., A quantum particle swarm optimization for the 0-1 generalized knapsack sharing problem, Natural Computing, 1-12 (2014) |
| [7] | Hifi, M.; M’Halla, H., The knapsack sharing problem: a tree search exact algorithm, Engineering and Technology, 66, 661-664 (2010) |
| [8] | Hifi, M.; M’Halla, H.; Sadfi, S., An exact algorithm for the knapsack sharing problem, Computers & Operations Research, 32, 1311-1324 (2005) · Zbl 1074.90037 |
| [9] | Hifi, M.; M’Hallah, R., Knapsack problems and applications, Computers and Operations Research, 39, 1 (2012) · Zbl 1251.90009 |
| [10] | Hifi, M.; Sadfi, S., The knapsack sharing problem: an exact algorithm, Journal of Combinatorial Optimization, 6, 35-54 (2002) · Zbl 1058.90055 |
| [11] | Hifi, M.; Wu, L., New upper bounds and exact methods for the knapsack sharing problem, Applied Mathematics and Computation, 227, 518-530 (2014) · Zbl 1364.90292 |
| [12] | Horowitz, E.; Sahni, S., Computing partitions with applications to the knapsack problem, Journal of ACM, 21, 277-292 (1974) · Zbl 0329.90046 |
| [13] | Karp, R. M., Reducibility among combinatorial problems, Complexity of Computer Computations, 85-103 (1972), Plenum · Zbl 1467.68065 |
| [14] | Kellerer, H.; Pferschy, U.; Pisinger, D., Knapsack problems (2004), Springer Verlag · Zbl 1103.90003 |
| [15] | Martello, S.; Toth, P., A mixture of dynamic programming and branch-and-bound for the subset-sum problem, Management Science, 30, 765-771 (1984) · Zbl 0555.90073 |
| [16] | Martello, S.; Toth, P., Knapsack problems: Algorithms and computer implementations (1990), Wiley: Wiley Chichester, UK · Zbl 0708.68002 |
| [17] | Pisinger, D., A minimal algorithm for the 0-1 knapsack problem, Operations Research, 45, 758-767 (1997) · Zbl 0902.90126 |
| [18] | Pisinger, D.; Martello, S.; Toth, P., Dynamic programming and strong bounds for the 0-1 knapsack problem, Management Science, 45, 3, 414-424 (1999) · Zbl 1231.90338 |
| [19] | Raidl, G. R., Decomposition based hybrid metaheuristics, European Journal of Operational Research, 244, 66-76 (2015) · Zbl 1346.90827 |
| [20] | Rooderkerk, R. P.; van Heerde, H. J., Robust optimization of the 0-1 knapsack problem: Balancing risk and return in assortment optimization, European Journal of Operational Research, 250, 842-854 (2016) · Zbl 1346.90048 |
| [21] | Wolsey, L. A., Integer programming (1998), Wiley: Wiley New York · Zbl 0930.90072 |
| [22] | Yamada, T.; Futakawa, M.; Kataoka, S., Some exact algorithms for the knapsack sharing problem, European Journal of Operational Research, 106, 177-183 (1998) |
| [23] | Zhang, X.; Yang, Z.; Zhou, Z.; Cai, H.; Chen, L.; Li, X., Free market of crowdsourcing: Incentive mechanism design for mobile sensing, IEEE Transactions on Parallel and Distributed Systems, 25, 12, 3190-3200 (2014) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
