Binary knapsack problems with random budgets

Document Type

Article

Publication Title

Journal of the Operational Research Society

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.

Publication Date

1-4-2003

Publisher

Operational Research Society||Taylor and Francis

Volume

Vol.54

Issue

Iss.9

This document is currently not available here.

Request Access

Share

COinS