Geodesic
Combinatorial properties of~the~bounded~knapsack~problem
Prikladnaâ diskretnaâ matematika, no. 1 (2024), pp. 117-130

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: knapsack problem, generating functions, NP-complete problems, deduction, decomposition methods.
Mots-clés : coefficient method 
@article{PDM_2024_1_a8,
     author = {M. S. A. Volkov},
     title = {Combinatorial properties of~the~bounded~knapsack~problem},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {117--130},
     publisher = {mathdoc},
     number = {1},
     year = {2024},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2024_1_a8/}
}
TY  - JOUR
AU  - M. S. A. Volkov
TI  - Combinatorial properties of~the~bounded~knapsack~problem
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2024
SP  - 117
EP  - 130
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2024_1_a8/
LA  - ru
ID  - PDM_2024_1_a8
ER  - 
%0 Journal Article
%A M. S. A. Volkov
%T Combinatorial properties of~the~bounded~knapsack~problem
%J Prikladnaâ diskretnaâ matematika
%D 2024
%P 117-130
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2024_1_a8/
%G ru
%F PDM_2024_1_a8
M. S. A. Volkov. Combinatorial properties of~the~bounded~knapsack~problem. Prikladnaâ diskretnaâ matematika, no. 1 (2024), pp. 117-130. http://geodesic.mathdoc.fr/item/PDM_2024_1_a8/