Geodesic
Algorithm for solving the knapsack problem with certain properties of pareto layers
Journal of the Belarusian State University. Mathematics and Informatics, Tome 3 (2022), pp. 54-66.

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

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. 
@article{BGUMI_2022_3_a4,
     author = {S. V. Chebakov and L. V. Serebryanaya},
     title = {Algorithm for solving the knapsack problem with certain properties of pareto layers},
     journal = {Journal of the Belarusian State University. Mathematics and Informatics},
     pages = {54--66},
     publisher = {mathdoc},
     volume = {3},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/BGUMI_2022_3_a4/}
}
TY  - JOUR
AU  - S. V. Chebakov
AU  - L. V. Serebryanaya
TI  - Algorithm for solving the knapsack problem with certain properties of pareto layers
JO  - Journal of the Belarusian State University. Mathematics and Informatics
PY  - 2022
SP  - 54
EP  - 66
VL  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/BGUMI_2022_3_a4/
LA  - ru
ID  - BGUMI_2022_3_a4
ER  - 
%0 Journal Article
%A S. V. Chebakov
%A L. V. Serebryanaya
%T Algorithm for solving the knapsack problem with certain properties of pareto layers
%J Journal of the Belarusian State University. Mathematics and Informatics
%D 2022
%P 54-66
%V 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/BGUMI_2022_3_a4/
%G ru
%F BGUMI_2022_3_a4
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, Tome 3 (2022), pp. 54-66. http://geodesic.mathdoc.fr/item/BGUMI_2022_3_a4/

[1] S. Martello, P. Toth, Knapsack problems: algorithms and computer implementations, John Wiley and Sons, New York, 1990, 308 pp. | MR

[2] M. A. Posypkin, “Kombinirovannyi parallelnyi algoritm resheniya zadachi o rantse”, Trudy IV Mezhdunarodnoi konferentsii «Parallelnye vychisleniya i zadachi upravleniya» (Moskva, Rossiya), IPU RAN, Moskva, 2008, 177–189

[3] S. V. Chebakov, “Dvukhkriterialnaya model postroeniya optimalnogo podmnozhestva alternativ s maksimalnoi summarnoi veroyatnostyu dostizheniya tseli”, Vestsi Natsyyanalnai akademii navuk Belarusi. Seryya fizika-matematychnykh navuk, 2 (2005), 112–118

[4] S. V. Chebakov, L. V. Serebryanaya, “Opredelenie struktury optimalnogo podmnozhestva v zadache o rantse”, Doklady BGUIR, 6 (2019), 72–79 | DOI

[5] S. V. Chebakov, L. V. Serebryanaya, “Algoritm nakhozhdeniya struktury optimalnogo podmnozhestva na osnove paretovskikh sloev v zadache o rantse”, Zhurnal Belorusskogo gosudarstvennogo universiteta. Matematika. Informatika, 2 (2020), 97–104 | DOI

[6] H. F. Kung, F. Luccio, F. P. Preparata, “On finding the maxima of a set of vectors”, Journal of the ACM, 22(4) (1975), 469–476 | DOI | MR