Skip to Main content Skip to Navigation
Journal articles

Heuristic and exact reduction procedures to solve the discounted 0–1 knapsack problem

Abstract : In this paper we consider the discounted 0–1 knapsack problem (DKP), which is an extension of the classical knapsack problem where a set of items is decomposed into groups of three items. At most one item can be chosen from each group and the aim is to maximize the total profit of the selected items while respecting the knapsack capacity constraint. The DKP is a relatively recent problem in the literature. It was considered in several recent works where metaheuristics are implemented to solve instances from the literature. In this paper we propose a two-phase approach in which the problem is reduced by applying exact and / or heuristic fixation rules in a first phase that can be viewed as a preprocessing phase. The remaining problem can then be solved by dynamic programming. Experiments performed on available instances in the literature show that the fixation techniques are very useful to solve these instances. Indeed, the preprocessing phase greatly reduces the size of these instances, leading to a significant reduction in the time required for dynamic programming to provide an optimal solution. Then, we generate a new set of instances that are more difficult to solve by exact methods. The hardness of these instances is confirmed experimentally by considering both the use of CPLEX solver and our approach.
Document type :
Journal articles
Complete list of metadata

https://hal-uphf.archives-ouvertes.fr/hal-03723560
Contributor : Christophe Wilbaut Connect in order to contact the contributor
Submitted on : Friday, July 15, 2022 - 11:03:58 AM
Last modification on : Tuesday, August 30, 2022 - 5:14:20 PM

File

 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2022-10-28

Please log in to resquest access to the document

Identifiers

Collections

Citation

Christophe Wilbaut, Raca Todosijevic, Saïd Hanafi, Arnaud Fréville. Heuristic and exact reduction procedures to solve the discounted 0–1 knapsack problem. European Journal of Operational Research, Elsevier, In press, ⟨10.1016/j.ejor.2022.04.036⟩. ⟨hal-03723560⟩

Share

Metrics

Record views

13