Spotting Difficult Weakly Correlated Binary Knapsack Problems

Diptesh Ghosh () and Bandopadhyay Tathagata

No 2006-01-04, IIMA Working Papers from Indian Institute of Management Ahmedabad, Research and Publication Department

Abstract: In this paper, we examine 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 the relationship between the degree of correlation between profit and cost values, the skewness of the distribution of objective function values and the difficulty in solving weakly correlated binary knapsack problems. We see that the even though it is unlikely that an exact relationship exists for individual problem instances, some aggregate relationships may be observed. Key words: Binary Knapsack Problems; Skewness; Computational Experiments.

New Economics Papers: this item is included in nep-cmp
Date: 2006-01-23
View list of references

Downloads: (external link)
http://www.iimahd.ernet.in/publications/data/2006-01-04dghosh.pdf English Version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: http://EconPapers.repec.org/RePEc:iim:iimawp:2006-01-04

Access Statistics for this paper

More papers in IIMA Working Papers from Indian Institute of Management Ahmedabad, Research and Publication Department
Contact information at EDIRC.
Series data maintained by ().