Commenced in January 2007
Frequency: Monthly
Edition: International
Paper Count: 1

interval reduction Related Publications

1 The Knapsack Sharing Problem: A Tree Search Exact Algorithm

Authors: Mhand Hifi, Hedi Mhalla


In this paper, we study the knapsack sharing problem, a variant of the well-known NP-Hard single knapsack problem. We investigate the use of a tree search for optimally solving the problem. The used method combines two complementary phases: a reduction interval search phase and a branch and bound procedure one. First, the reduction phase applies a polynomial reduction strategy; that is used for decomposing the problem into a series of knapsack problems. Second, the tree search procedure is applied in order to attain a set of optimal capacities characterizing the knapsack problems. Finally, the performance of the proposed optimal algorithm is evaluated on a set of instances of the literature and its runtime is compared to the best exact algorithm of the literature.

Keywords: combinatorial optimization, Heuristics, branch and bound, knapĀ¬sack, knapsack sharing, interval reduction

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1227