A multi-criteria approach to approximate solution to multiple-choice knapsack problem

Ewa Bednarczuk , Janusz Miroforidis , Przemysław Pyzel

Abstract

We propose a method for finding approximate solutions to multiple-choice knapsack problems. To this aim we transform the multiple-choice knapsack problem into a bi-objective optimization problem whose solution set contains solutions of the original multiple-choice knapsack problem. The method relies on solving a series of suitably defined linearly scalarized bi-objective problems. The novelty which makes the method attractive from the computational point of view is that we are able to solve explicitly those linearly scalarized bi-objective problems with the help of the closed-form formulae.
Author Ewa Bednarczuk (FMIS / DCSDCAM) - Systems Research Institute (IBS PAN) [Polish Academy of Sciences (PAN)]
Ewa Bednarczuk,,
- Department of CAD/CAM Systems Design and Computer-Aided Medicine
, Janusz Miroforidis
Janusz Miroforidis,,
-
, Przemysław Pyzel
Przemysław Pyzel,,
-
Journal seriesComputational Optimization and Applications, ISSN 0926-6003, (A 35 pkt)
Issue year2018
Vol70
No3
Pages889-910
Publication size in sheets1.05
Keywords in Polishzagadnienie załadunku, optymalizacja wielo-kryterialna, zagadnienie załadunku z wyborem, liniowa skalaryzacja
Keywords in EnglishKnapsack, Multi-objective optimization, Multiple-choice knapsack, Linear scalarization
ASJC Classification2604 Applied Mathematics; 2605 Computational Mathematics; 2606 Control and Optimization
Abstract in PolishZaproponowana została metoda znajdowania rozwiązań przybliżonych zadania załadunku z wyborem.
DOIDOI:10.1007/s10589-018-9988-z
URL https://link.springer.com/article/10.1007/s10589-018-9988-z
Languageen angielski
Score (nominal)35
Score sourcejournalList
ScoreMinisterial score = 35.0, 31-12-2019, ArticleFromJournal
Publication indicators WoS Citations = 1; Scopus SNIP (Source Normalised Impact per Paper): 2018 = 1.206; WoS Impact Factor: 2018 = 1.906 (2) - 2018=2.064 (5)
Citation count*
Cite
Share Share

Get link to the record


* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back
Confirmation
Are you sure?