An exact constructive algorithm for the knapsack sharing problem. (3rd September 2017)

• Record Type: Journal Article
• Authors: Mhalla, Hedi
• Is Part Of: Optimization methods and software. Volume 32:Number 5(2017)
• Page Start: 1078
• Page End: 1094
• Publication Date: 2017-09-03
• Subjects: Branch and bound -- combinatorial optimization -- knapsack sharing -- heuristics -- interval reduction -- optimization; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2016.1240795
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : In this paper, we study the knapsack sharing problem (KSP), a variant of the well-known NP-hard single knapsack problem. We propose an exact constructive tree search that combines two complementary procedures: a reduction interval search and a branch and bound. The reduction search has three phases. The first phase applies a polynomial reduction strategy that decomposes the problem into a series of knapsack problems. The second phase is a size reduction strategy that makes the resolution more efficient. The third phase is an interval reduction search that identifies a set of optimal capacities characterizing the knapsack problems. Experimental results provide computational evidence of the better performance of the proposed exact algorithm in comparison to KSPs best exact algorithm, to Cplex and to KSPs latest heuristic approach. Furthermore, they emphasize the importance of the reduction strategies.