Spotting difficult weakly correlated binary knapsack problems by Diptesh Ghosh and Tathagata Bandopadhyay (Working Paper)

By: Contributor(s): Material type: TextTextPublication details: Ahmedbadad Indian Institute of Management 2006 Description: 10 pSubject(s): DDC classification:
  • WP 2006-01-04 (1926)
Summary: 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
Tags from this library: No tags from this library for this title. Log in to add tags.
Star ratings
    Average rating: 0.0 (0 votes)
Holdings
Item type Current library Call number Status Date due Barcode
Working Paper Vikram Sarabhai Library WP 2006-01-04 (1926) (Browse shelf(Opens below)) Available WP001926

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

There are no comments on this title.

to post a comment.