Binary knapsack problems with random budgets
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.
Collections
- Journal Articles [3727]