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) [Polska Akademia Nauk (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
ScoreMinisterial score = 35.0, 04-02-2019, ArticleFromJournal
Ministerial score (2013-2016) = 35.0, 04-02-2019, ArticleFromJournal
Publication indicators Scopus SNIP (Source Normalised Impact per Paper): 2016 = 1.323; WoS Impact Factor: 2017 = 1.413 (2) - 2017=1.742 (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