Premium
New reduction strategy in the biobjective knapsack problem
Author(s) -
Daoud Malika,
Chaabane Djamal
Publication year - 2018
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12285
Subject(s) - knapsack problem , reduction (mathematics) , mathematical optimization , computer science , domain (mathematical analysis) , mathematics , order (exchange) , continuous knapsack problem , economics , geometry , mathematical analysis , finance
In this paper, the admissible region of a biobjective knapsack problem is our main interest. Although the reduction of feasible region has been studied by some authors, yet more investigation has to be done in order to deeply explore the domain before solving the problem. We propose, however, a new technique based on extreme supported efficient solutions combined with the dominance relationship between items' efficiency. An illustration of the algorithm by a didactic example is given and some experiments are presented, showing the efficiency of the procedure compared to the previous techniques found in the literature.