Spotting difficult weakly correlated binary knapsack problems
View/ Open
Date
2010-04-16Author
Ghosh, Diptesh
Bandyopadhyay, Tathagata
Metadata
Show full item recordAbstract
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.
Collections
- Working Papers [2627]