Analysis of Divide-and-Conquer strategies for the 0-1 minimization knapsack problem

We introduce and asses several Divide-and-Conquer heuristic strategies, aimed at solving large instances of the 0-1 Minimization Knapsack Problem. The method subdivides a large problem in two smaller ones (or recursive iterations of the same procedure), in order to lower down the global computational complexity of the original problem, at the expense of a moderate loss of quality in the solution. Theoretical mathematical results are presented to assure a successful algorithmic application of the method and to suggest the potential strategies for its implementation. In contrast, due to the lack of theoretical results, the solution's quality deterioration is measured empirically by means of Monte Carlo simulations for several types and values of the chosen strategies. Finally, introducing parameters of efficiency we suggest the best strategies depending on the data input.