|
Discrete mathematics and Mathematical cybernetics
Algorithm for solving the knapsack problem with certain properties of pareto layers
S. V. Chebakova, L. V. Serebryanayabc a United Institute of Informatics Problems, National Academy of Sciences of Belarus, 6 Surhanava Street, Minsk 220012, Belarus
b Belarusian State University of Informatics and Radioelectronics, 6 P. Brouki Street, Minsk 220013, Belarus
c BIP – University of Law and Social-Information Technologies, 3 Karalia Street, Minsk 220004, Belarus
Abstract:
An algorithm for solving the knapsack problem based on the proposed multicriteria model has been developed. The structure of admissible subsets is presented for the value of the non-dominance depth of the Pareto layer equal to zero. The sum of the resource of the elements of this layer is greater than or equal to the value of the volume of the knapsack. Based on the structure, the form of the optimal admissible subset with the maximum total value of the weight of its elements is determined. It is shown that at a certain stage the developed algorithm includes the solution of a number of knapsack subtasks. Their knapsack volumes are smaller than in the original problem with input data sets. The definition of the redundancy of the set of initial data and the condition for the existence of redundancy for a given value of the depth of non-dominance of the Pareto layer are introduced.
Keywords:
knapsack problem; multicriteria optimisation; Pareto set; Pareto layer.
Received: 20.12.2021 Revised: 10.11.2022 Accepted: 10.11.2022
Citation:
S. V. Chebakov, L. V. Serebryanaya, “Algorithm for solving the knapsack problem with certain properties of pareto layers”, Journal of the Belarusian State University. Mathematics and Informatics, 3 (2022), 54–66
Linking options:
https://www.mathnet.ru/eng/bgumi199 https://www.mathnet.ru/eng/bgumi/v3/p54
|
Statistics & downloads: |
Abstract page: | 41 | Full-text PDF : | 18 | References: | 11 |
|