Stochastic knapsack problem

Keith W. Ross; Danny Tsang

doi:10.1109/cdc.1988.194387

Stochastic knapsack problem

Keith W. Ross^*, Danny Tsang

^*Corresponding author for this work

Research output: Contribution to journal › Conference article published in journal › peer-review

3 Citations (Scopus)

Abstract

The authors consider a knapsack with integer volume F which is capable of holding K different classes of objects. An object from class-k has integer volume b_k, k = 1,...,K. Objects arrive randomly to the knapsack; interarrivals are exponential with mean depending on the state of the system. The sojourn time of an object has a general class-dependent distribution. An object in the knapsack from class-k accrues revenue at a rate r_k. The problem is to find a control policy in order to accept/reject the arriving objects as a function of the current state in order to maximize the average revenue. Optimization is carried out over the class of coordinate convex policies. Among other results, for the general case of K classes, the authors consider the problem of finding the optimal static control, where for each class a portion of the knapsack is dedicated.

Original language	English
Pages (from-to)	632-633
Number of pages	2
Journal	Proceedings of the IEEE Conference on Decision and Control
DOIs	https://doi.org/10.1109/cdc.1988.194387
Publication status	Published - Dec 1988
Externally published	Yes
Event	Proceedings of the 27th IEEE Conference on Decision and Control - Austin, TX, USA Duration: 7 Dec 1988 → 9 Dec 1988

Access to Document

10.1109/cdc.1988.194387

Cite this

@article{575b840daa884d64b90da3f6816a0047,

title = "Stochastic knapsack problem",

abstract = "The authors consider a knapsack with integer volume F which is capable of holding K different classes of objects. An object from class-k has integer volume bk, k = 1,...,K. Objects arrive randomly to the knapsack; interarrivals are exponential with mean depending on the state of the system. The sojourn time of an object has a general class-dependent distribution. An object in the knapsack from class-k accrues revenue at a rate rk. The problem is to find a control policy in order to accept/reject the arriving objects as a function of the current state in order to maximize the average revenue. Optimization is carried out over the class of coordinate convex policies. Among other results, for the general case of K classes, the authors consider the problem of finding the optimal static control, where for each class a portion of the knapsack is dedicated.",

author = "Ross, \{Keith W.\} and Danny Tsang",

year = "1988",

month = dec,

doi = "10.1109/cdc.1988.194387",

language = "English",

pages = "632--633",

journal = "Proceedings of the IEEE Conference on Decision and Control",

issn = "0191-2216",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

note = "Proceedings of the 27th IEEE Conference on Decision and Control ; Conference date: 07-12-1988 Through 09-12-1988",

}

TY - JOUR

T1 - Stochastic knapsack problem

AU - Ross, Keith W.

AU - Tsang, Danny

PY - 1988/12

Y1 - 1988/12

N2 - The authors consider a knapsack with integer volume F which is capable of holding K different classes of objects. An object from class-k has integer volume bk, k = 1,...,K. Objects arrive randomly to the knapsack; interarrivals are exponential with mean depending on the state of the system. The sojourn time of an object has a general class-dependent distribution. An object in the knapsack from class-k accrues revenue at a rate rk. The problem is to find a control policy in order to accept/reject the arriving objects as a function of the current state in order to maximize the average revenue. Optimization is carried out over the class of coordinate convex policies. Among other results, for the general case of K classes, the authors consider the problem of finding the optimal static control, where for each class a portion of the knapsack is dedicated.

AB - The authors consider a knapsack with integer volume F which is capable of holding K different classes of objects. An object from class-k has integer volume bk, k = 1,...,K. Objects arrive randomly to the knapsack; interarrivals are exponential with mean depending on the state of the system. The sojourn time of an object has a general class-dependent distribution. An object in the knapsack from class-k accrues revenue at a rate rk. The problem is to find a control policy in order to accept/reject the arriving objects as a function of the current state in order to maximize the average revenue. Optimization is carried out over the class of coordinate convex policies. Among other results, for the general case of K classes, the authors consider the problem of finding the optimal static control, where for each class a portion of the knapsack is dedicated.

UR - http://www.scopus.com/inward/record.url?scp=0024177864&partnerID=8YFLogxK

U2 - 10.1109/cdc.1988.194387

DO - 10.1109/cdc.1988.194387

M3 - Conference article published in journal

AN - SCOPUS:0024177864

SN - 0191-2216

SP - 632

EP - 633

JO - Proceedings of the IEEE Conference on Decision and Control

JF - Proceedings of the IEEE Conference on Decision and Control

T2 - Proceedings of the 27th IEEE Conference on Decision and Control

Y2 - 7 December 1988 through 9 December 1988

ER -

Stochastic knapsack problem

Abstract

Access to Document

Other files and links

Fingerprint

Cite this