Spotting difficult weakly correlated binary knapsack problems

Abstract

We examine in this paper that the possibility of quickly deciding whether or not an instance of a binary knapsack problem is difficult for branch and bound algorithms. We first observe that the distribution of the objective function values is smooth and unimodal. We define a measure of difficulty of solving knapsack problems through branch and bound algorithms, and examine of the relationship between the degree of correlation between profit and cost values, the skew ness of the distribution of objective function and values and the difficulty in solving weakly correlated binary knapsack problems. We see that the even thought it is unlikely that an exact relationship exists for individual problem instances; some aggregate relationships may be observed.