The combinatorial properties of the set of solutions to the bounded knapsack problem are considered. As in the general case, this problem is an NP-complete combinatorial optimization problem and its exact solution requires the use of search algorithms with the decomposition of a set of feasible solutions. In this regard, the question of determining and evaluating the properties of the set of acceptable solutions to the problem is relevant. In this paper, formulas are obtained which allow to calculate the average value of the functional of a problem on the set of its feasible solutions and the power of this set through the number of solutions of subtasks of smaller dimension. The basic technique for obtaining results is the method of generating functions. We also consider the knapsack problem with arbitrary values of variables, in which the coefficients of the constraint vector and the objective function coincide. For this, the “continuity” of the set of solutions is assumed. Estimates of the values of the functional in this problem are found. The results may be of interest for the design of computational algorithms for finding and estimating the number of solutions and the value of the functional for optimal solutions. The expressions found can also be used in auxiliary procedures to evaluate the optimality of the solution in decomposition or heuristic algorithms for solving the knapsack problem.
Download file
Counter downloads: 90
- Title Combinatorial properties of the bounded knapsack problem
- Headline Combinatorial properties of the bounded knapsack problem
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 63
- Date:
- DOI 10.17223/20710410/63/8
Keywords
knapsack problem, generating functions, NP-complete problems, coefficient method, deduction, decomposition methodsAuthors
References
Kellerer Н., Pferschy U., and Pisinger D. Knapsack Problems. Berlin: Springer, 2004. 548 p.
Егорычев Г. П. Интегральное представление и вычисление комбинаторных сумм. Новосибирск: Наука, 1977. 285 с.
Zhang Н., Plan W., Lai X., et al. Survey on cyberspace security // Sci. China Inform. Sci. 2015. V. 58. No. 11. P.1-43.
Lyubashevsky V., Palacio A., and Segev G. Public-key cryptographic primitives provablv as secure as subset sum // LNCS. 2010. V. 5978. P. 382-400'.
Ranjith J. and Mahantesh K. Blockchain-based knapsack system for security and privacy preserving to medical data // SN Comput. Sci. 2021. V. 2. https://www.researcher-app.com/paper/7553542.
Martello S. and Toth P. Knapsack Problems: Algorithms and Computer Implementations. N.Y.: John Wiley & Sons, 1990. 308 p.
Zhang X., Huang S., Hu Y., et al. Solving 0-1 knapsack problems based on amoeboid organism algorithm // Appl. Math.Comput. 2013. V.219. No. 19. P.9959-9970.
Kulkarni A.J. and Shabir H. Solving 0-1 knapsack problem using Cohort Intelligence Algorithm // Int. J. Mach. Learn. & Cyber. 2014. V. 7. P.427-441.
Rezoug A., Bader-El-Den M., and Boughaci D. Guided genetic algorithm for the multidimensional knapsack problem // Memetic Computing. 2018. V. 10. P.29-42.
Kong X., Gao L., Ouyang H., and Li S. Solving large-scale multidimensional knapsack problems with a new binary harmony search algorithm // Computers k, Operations Res. 2015. V.63. P.7-22.
Lv J., Wang X., Huang M., et al. Solving 0-1 knapsack problem by greedy degree and expectation efficiency // Appl. Soft Comput. 2016. V.41. P.94-103.
Chen Y. and Hao J.-K. A “reduce and solve” approach for the multiple-choice multidimensional knapsack problem // Europ. J. Operational Res. 2014. V. 239. No. 2. P. 312- 322.
Voβ S. and Lalla-Ruiz E. A set partitioning reformulation for the multiple-choice multidimensional knapsack problem // Engin. Optimization. 2016. V. 48. No. 5. P. 831 850.
Dang C. and Ye Y. A fixed point iterative approach to integer programming and its distributed computation // Fixed Point Theory Appl. 2015. https://fixedpointtheoryand_algorithms.springeropen.com/articles/10.1186/sl3663-015-0429-8.
Pesant G. Counting solutions of CSPs: A structural spproach // Proc. IJCAF05. Edinburgh, Scotland, 2005. P.260-265.
Louveaux Q. and Weismantel R. Polyhedral properties for the intersection of two knapsacks // Math. Program. 2008. V. 113. P. 15-37.
Hojny C., Gaily T., Habeck O., et al. Knapsack polvtopes: a survey // Ann. Oper. Res. 2020. V.292. P.469-517.
Леонтьев В. К., Гордеев Э. Н. Производящие функции в задаче о ранце // Доклады Академии наук. 2018. Т. 481. №5. С. 478-480.
Гордеев Э.Н., Леонтьев В. К. О некоторых комбинаторных свойствах задачи о рюкзаке // Ж. вычисл. матем. и матем. физ. 2019. Т. 59. №8. С. 1439-1447.
Леонтьев В. К., Гордеев Э. Н. О числе решений системы булевых уравнений // Автоматика и телемеханика. 2021. №9. С. 150-168.
Леонтьев В. К., Гордеев Э.Н. О некоторых особенностях задачи разрешимости систем булевых уравнений j j Вопросы кибербезопасности. 2021. №1(41). С. 18-28.
Леонтьев В. К. О псевдобулевых полиномах // Ж. вычисл. матем. и матем. физ. 2015. Т. 55. №11. С. 1952-1958.
Леонтьев В. К., Гордеев Э. Н., Волков М. С. А. Классическая непрерывности и ее дискретный вариант // Прикладная физика и математика. 2022. №1. С. 31-37.
Combinatorial properties of the bounded knapsack problem | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2024. № 63. DOI: 10.17223/20710410/63/8
Download full-text version
Counter downloads: 104