Spotting Difficult Weakly Correlated Binary Knapsack Problems

Diptesh Ghosh () and Tathagata Bandyopadhyay

No WP2006-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.

Date: 2006-01-04
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.iima.ac.in/sites/default/files/rnpfiles/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: https://EconPapers.repec.org/RePEc:iim:iimawp:wp01928

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.
Bibliographic data for series maintained by ().