Obtaining Near OptimalSolutions for the Binary Knapsack Problem

Diptesh Ghosh () and Goldengorin Boris

No 2002-02-03, IIMA Working Papers from Indian Institute of Management Ahmedabad, Research and Publication Department

Abstract: In this paper we consider the well-known binary knapsack problem. We propose a method of embedding heuristicsi in a branch and bound framework to optain solutions with profits within a pre-specified quality parameter within very short times. Our computational experiements on the more deficult problems show that algorithm can genrate solutions with profits within 0.01% of that of an optimal solution in less than 10% of the time required by exact algorithms based on similar priciples.

Date: 2002-02-01

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:2002-02-03

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 ().