Please use this identifier to cite or link to this item:
Title: 0-1 Knapsack problems with random budgets
Authors: Das, Shubhabrata 
Ghosh, Diptesh 
Keywords: Static stochastic knapsack;Random budget;Infeasibility;Branch and bound
Issue Date: 2001
Publisher: Indian Institute of Management Bangalore
Series/Report no.: IIMB Working Paper-166
Abstract: Given a set of elements, each having a profit and cost associated with it, and a budget, the 0-1 knapsack problem finds a subset of the elements with maximum possible combined profit subject to the combined cost not exceeding the budget. In this paper we study a stochastic version of the problem in which the budget is random. We propose two different formulations of this problem, based on different ways of handling infeasibilities, and propose exact and heuristic algorithms to solve the problems represented by these formulations. We also present the results from some computational experiments.
Appears in Collections:2001

Files in This Item:
File Description SizeFormat 
wp.iimb.166.pdf2.43 MBAdobe PDFView/Open
Show full item record

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.