Share Email Print

Proceedings Paper

Experimental evaluation of some approximate algorithms of solving the multidimensional knapsack problem
Author(s): Birute I. Yuhimenko; Svitlana V. Kornilova; Inna O. Asaulyuk; Piotr Kisała; Saule Luganskaya; Indira Shedreyeva
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

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.

Paper Details

Date Published: 15 March 2019
PDF: 7 pages
Proc. SPIE 11045, Optical Fibers and Their Applications 2018, 1104517 (15 March 2019); doi: 10.1117/12.2523175
Show Author Affiliations
Birute I. Yuhimenko, Odessa National Polytechnic Univ. (Ukraine)
Svitlana V. Kornilova, Odessa National Polytechnic Univ. (Ukraine)
Inna O. Asaulyuk, Vinnytsia State Pedagogical Univ. (Ukraine)
Piotr Kisała, Lublin Univ. of Technology (Poland)
Saule Luganskaya, Lublin Univ. of Technology (Poland)
Indira Shedreyeva, Taraz State Univ. (Kazakhstan)

Published in SPIE Proceedings Vol. 11045:
Optical Fibers and Their Applications 2018
Ryszard S. Romaniuk; Waldemar Wójcik; Andrzej Smolarz, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?