0-1 Knapsack problems with random budgets

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.