Experimental evaluation of some approximate algorithms of solving the multidimensional knapsack problem

Piotr A. Kisała, Birute I. Yuhimenko, Svitlana V. Kornilova, Інна Олексіївна Асаулюк, Saule Luganskaya, Indira Shedreyeva

2019

Жабық қол жеткізу Метадеректер (CSL-JSON)
DOI 10.1117/12.2523175
Деректер сенімділігі 70 орташа
Бұл баға қалай есептеледі

Ол жазбаның өзінің тексерілетін белгілерінен құралады: мақаланың DOI-і бар ма, оның деректерін қанша тәуелсіз дереккөз растады, міндетті өрістер толтырылған ба және соңғы растау қаншалықты жаңа. Дереккөздер арасындағы алшақтық пен идентификатордың болмауы бағаны төмендетеді. 80-нен бастап мән жазбаның қосымша тексерусіз жарияланғанын, 60-тан 79-ға дейін — оның сенімділігі төмен күйде жарияланғанын және қолмен тексеру ұсынылатынын білдіреді. Редактор қолмен тексерген жазбаны қайта есептеу 90-нан төмен түсірмейді. Бұл — мақаланың өзіне емес, ол туралы деректерімізге берілген баға.

Аңдатпа

The results of an experimental study of obtaining approximate solutions of the multidimensional knapsack problem are presented in the paper. Three methods for obtaining these solutions are considered, based on branch-end-bound algorithms with a one-sided branching. One hundred test tasks of different dimensions have been solved for each method. The estimation of the approximation of the solutions obtained in relation to the best solution is provided, as well as the estimation of the computational complexity.