The stochastic knapsack problem

The problem of packing a knapsack of integer volume F with objects from K different classes to maximize profit is studied. Optimization is carried out over the class of coordinate convex policies. For the case of K=2, it is shown for a wide range of parameters that the optimal control is of the thre...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on communications 1989-07, Vol.37 (7), p.740-747
Main Authors: Ross, K.W., Tsang, D.H.K.
Format: Article
Language:English
Subjects:
Applied sciences
Bandwidth
Communication switching
Communications Society
Dynamic programming
Exact sciences and technology
Heuristic algorithms
Optimal control
Stochastic processes
Systems, networks and services of telecommunications
Telecommunication traffic
Telecommunications
Telecommunications and information theory
Teletraffic
Traffic control
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The problem of packing a knapsack of integer volume F with objects from K different classes to maximize profit is studied. Optimization is carried out over the class of coordinate convex policies. For the case of K=2, it is shown for a wide range of parameters that the optimal control is of the threshold type. In the case of Poisson arrivals and of knapsack and object volumes being integer multiples of each other, it is shown that the optimal policy is always of the double-threshold type. An O(F) algorithm to determine the revenue of threshold policies is also given. For the general case of K classes, the problem of the optimal static control where for each class a portion of the knapsack is dedicated is considered. An efficient finite-stage dynamic programming algorithm for locating the optimal static control is presented. Furthermore, variants of the optimal static control which allow some sharing among classes are also discussed.< >
ISSN:0090-6778
1558-0857
DOI:10.1109/26.31166