Theoretical Paper
Journal of the Operational Research Society (2003) 54, 970–983. doi:10.1057/palgrave.jors.2601596
Binary knapsack problems with random budgets
- 1QM&IS Area, Indian Institute of Management, Bangalore, India
- 2P&QM Area, Indian Institute of Management, Ahmedabad, India
Correspondence: S Das, QM&IS Area, Faculty Block C, 2nd Floor, IIM Bangalore, Bannerghatta Road, Bangalore 560076, India. E-mail: shubho@iimb.ernet.in
Received April 2002; Accepted April 2003.
Abstract
The binary knapsack problem is a combinatorial optimization problem in which a subset of a given set of elements needs to be chosen in order to maximize profit, given a budget constraint. 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 infeasibility, and propose an exact algorithm and a local search-based heuristic to solve the problems represented by these formulations. We also present the results from some computational experiments.
Keywords:
static stochastic knapsack problem, random budget, branch and bound
