Document Type

Working Paper

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.

Publication Date

1-4-2001

Publisher

Indian Institute of Management Bangalore

Relation

IIMB Working Paper-166

Download

Share

COinS