Combinatorial properties of~the~bounded~knapsack~problem

M. S. A. Volkov

Prikladnaâ diskretnaâ matematika, no. 1 (2024), pp. 117-130.

Résumé

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.

Détail

Keywords: knapsack problem, generating functions, NP-complete problems, deduction, decomposition methods.
Mots-clés : coefficient method

Bibliographie

[1] Kellerer H., Pferschy U., and Pisinger D., Knapsack Problems, Springer, Berlin, 2004, 548 pp. | MR | Zbl

[2] Egorychev G. P., Integral Representation and the Computation of Combinatorial Sums, Nauka, Novosibirsk, 1977, 285 pp. (in Russian)

[3] Zhang H., Han W., Lai X., et al., “Survey on cyberspace security”, Sci. China Inform. Sci., 58:11 (2015), 1–43 | MR

[4] Lyubashevsky V., Palacio A., and Segev G., “Public-key cryptographic primitives provably as secure as subset sum”, LNCS, 5978, 2010, 382–400 | MR | Zbl

[5] Ranjith J. and Mahantesh K., “Blockchain-based knapsack system for security and privacy preserving to medical data”, SN Comput. Sci., v. 2, 2021 https://www.researcher-app.com/paper/7553542

[6] Martello S. and Toth P., Knapsack Problems: Algorithms and Computer Implementations, John Wiley Sons, N.Y., 1990, 308 pp. | MR | Zbl

[7] Zhang X., Huang S., Hu Y., et al., “Solving 0-1 knapsack problems based on amoeboid organism algorithm”, Appl. Math. Comput., 219:19 (2013), 9959–9970 | MR | Zbl

[8] Kulkarni A. J. and Shabir H., “Solving 0-1 knapsack problem using Cohort Intelligence Algorithm”, Int. J. Mach. Learn. Cyber., 7 (2014), 427–441 | DOI

[9] Rezoug A., Bader-El-Den M., and Boughaci D., “Guided genetic algorithm for the multidimensional knapsack problem”, Memetic Computing, 10 (2018), 29–42 | DOI

[10] Kong X., Gao L., Ouyang H., and Li S., “Solving large-scale multidimensional knapsack problems with a new binary harmony search algorithm”, Computers Operations Res., 63 (2015), 7–22 | DOI | MR | Zbl

[11] Lv J., Wang X., Huang M., et al., “Solving 0-1 knapsack problem by greedy degree and expectation efficiency”, Appl. Soft Comput., 41 (2016), 94–103 | DOI

[12] Chen Y. and Hao J.-K., “A “reduce and solve” approach for the multiple-choice multidimensional knapsack problem”, Europ. J. Operational Res., 239:2 (2014), 312–322 | DOI | MR

[13] Voß S. and Lalla-Ruiz E., “A set partitioning reformulation for the multiple-choice multidimensional knapsack problem”, Engin. Optimization, 48:5 (2016), 831–850 | DOI | MR

[14] Dang C. and Ye Y., “A fixed point iterative approach to integer programming and its distributed computation”, Fixed Point Theory Appl., 2015 | DOI | MR

[15] Pesant G., “Counting solutions of CSPs: A structural spproach”, Proc. IJCAI'05 (Edinburgh, Scotland, 2005), 260–265

[16] Louveaux Q. and Weismantel R., “Polyhedral properties for the intersection of two knapsacks”, Math. Program., 113 (2008), 15–37 | DOI | MR | Zbl

[17] Hojny C., Gally T., Habeck O., et al., “Knapsack polytopes: a survey”, Ann. Oper. Res., 292 (2020), 469–517 | DOI | MR | Zbl

[18] Leont'ev V. K. and Gordeev E. N., “The generating functions in the knapsack problem”, Doklady Akademii Nauk, 481:5 (2018), 478–480 (in Russian) | DOI | Zbl

[19] Gordeev E. N. and Leont'ev V. K., “On combinatorial properties of the knapsack problem”, Comput. Math. Math. Phys., 59:8 (2019), 1380–1388 | DOI | DOI | MR | Zbl

[20] Leontiev V. K. and Gordeev E. N., “On the number of solutions to a system of Boolean equations”, Autom. Remote Control, 82:9 (2021), 1581–1596 | DOI | MR | Zbl

[21] Leont'ev V. K. and Gordeev E. N., “On some features of the problem of solvability of Boolean equations systems”, Voprosy Kiberbezopasnosti, 2021, no. 1(41), 18–28 (in Russian)

[22] Leontiev V. K., “On pseudo-Boolean polynomials”, Comput. Math. Math. Phys., 55:11 (2015), 1926–1932 | DOI | DOI | MR | Zbl

[23] Leont'ev V. K., Gordeev E. N., and Volkov M. S. A., “Classical continuity and its discrete variant”, Prikladnaya Fizika i Matematika, 2022, no. 1, 31–37 (in Russian)