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!
cited_by cdi_FETCH-LOGICAL-c335t-49e6502216fe06b454f270baebfd61b8540533ea2f7c2902972b051dca878b133
cites cdi_FETCH-LOGICAL-c335t-49e6502216fe06b454f270baebfd61b8540533ea2f7c2902972b051dca878b133
container_end_page 747
container_issue 7
container_start_page 740
container_title IEEE transactions on communications
container_volume 37
creator Ross, K.W.
Tsang, D.H.K.
description 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.< >
doi_str_mv 10.1109/26.31166
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_crossref_primary_10_1109_26_31166</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>31166</ieee_id><sourcerecordid>25519715</sourcerecordid><originalsourceid>FETCH-LOGICAL-c335t-49e6502216fe06b454f270baebfd61b8540533ea2f7c2902972b051dca878b133</originalsourceid><addsrcrecordid>eNqF0L1PwzAQBXALgUQpSKxMdAGxpJztnD9GVPElVWIps2W7ZzU0bUqcDvz3tKSCkemG--k96TF2yWHMOdh7ocaSc6WO2IAjmgIM6mM2ALBQKK3NKTvL-QMASpBywK5nCxrlrokLn7sqjpZrv8k-Lkebtgk1rc7ZSfJ1povDHbL3p8fZ5KWYvj2_Th6mRZQSu6K0pBCE4CoRqFBimYSG4CmkueLBYAkoJXmRdBQWhNUiAPJ59EabwKUcsts-d9f7uaXcuVWVI9W1X1OzzU4YpQwq9T9E5FZz3MG7Hsa2ybml5DZttfLtl-Pg9lM5odzPVDt6c8j0Ofo6tX4dq_znLRpu5d5d9a4iot93n_ENeNltZw</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>25519715</pqid></control><display><type>article</type><title>The stochastic knapsack problem</title><source>IEEE Xplore (Online service)</source><creator>Ross, K.W. ; Tsang, D.H.K.</creator><creatorcontrib>Ross, K.W. ; Tsang, D.H.K.</creatorcontrib><description>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.&lt; &gt;</description><identifier>ISSN: 0090-6778</identifier><identifier>EISSN: 1558-0857</identifier><identifier>DOI: 10.1109/26.31166</identifier><identifier>CODEN: IECMBT</identifier><language>eng</language><publisher>New York, NY: IEEE</publisher><subject>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</subject><ispartof>IEEE transactions on communications, 1989-07, Vol.37 (7), p.740-747</ispartof><rights>1991 INIST-CNRS</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c335t-49e6502216fe06b454f270baebfd61b8540533ea2f7c2902972b051dca878b133</citedby><cites>FETCH-LOGICAL-c335t-49e6502216fe06b454f270baebfd61b8540533ea2f7c2902972b051dca878b133</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://ieeexplore.ieee.org/document/31166$$EHTML$$P50$$Gieee$$H</linktohtml><link.rule.ids>314,780,784,27924,27925,54796</link.rule.ids><backlink>$$Uhttp://pascal-francis.inist.fr/vibad/index.php?action=getRecordDetail&amp;idt=19581936$$DView record in Pascal Francis$$Hfree_for_read</backlink></links><search><creatorcontrib>Ross, K.W.</creatorcontrib><creatorcontrib>Tsang, D.H.K.</creatorcontrib><title>The stochastic knapsack problem</title><title>IEEE transactions on communications</title><addtitle>TCOMM</addtitle><description>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.&lt; &gt;</description><subject>Applied sciences</subject><subject>Bandwidth</subject><subject>Communication switching</subject><subject>Communications Society</subject><subject>Dynamic programming</subject><subject>Exact sciences and technology</subject><subject>Heuristic algorithms</subject><subject>Optimal control</subject><subject>Stochastic processes</subject><subject>Systems, networks and services of telecommunications</subject><subject>Telecommunication traffic</subject><subject>Telecommunications</subject><subject>Telecommunications and information theory</subject><subject>Teletraffic</subject><subject>Traffic control</subject><issn>0090-6778</issn><issn>1558-0857</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>1989</creationdate><recordtype>article</recordtype><recordid>eNqF0L1PwzAQBXALgUQpSKxMdAGxpJztnD9GVPElVWIps2W7ZzU0bUqcDvz3tKSCkemG--k96TF2yWHMOdh7ocaSc6WO2IAjmgIM6mM2ALBQKK3NKTvL-QMASpBywK5nCxrlrokLn7sqjpZrv8k-Lkebtgk1rc7ZSfJ1povDHbL3p8fZ5KWYvj2_Th6mRZQSu6K0pBCE4CoRqFBimYSG4CmkueLBYAkoJXmRdBQWhNUiAPJ59EabwKUcsts-d9f7uaXcuVWVI9W1X1OzzU4YpQwq9T9E5FZz3MG7Hsa2ybml5DZttfLtl-Pg9lM5odzPVDt6c8j0Ofo6tX4dq_znLRpu5d5d9a4iot93n_ENeNltZw</recordid><startdate>19890701</startdate><enddate>19890701</enddate><creator>Ross, K.W.</creator><creator>Tsang, D.H.K.</creator><general>IEEE</general><general>Institute of Electrical and Electronics Engineers</general><scope>IQODW</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><scope>7SP</scope></search><sort><creationdate>19890701</creationdate><title>The stochastic knapsack problem</title><author>Ross, K.W. ; Tsang, D.H.K.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c335t-49e6502216fe06b454f270baebfd61b8540533ea2f7c2902972b051dca878b133</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>1989</creationdate><topic>Applied sciences</topic><topic>Bandwidth</topic><topic>Communication switching</topic><topic>Communications Society</topic><topic>Dynamic programming</topic><topic>Exact sciences and technology</topic><topic>Heuristic algorithms</topic><topic>Optimal control</topic><topic>Stochastic processes</topic><topic>Systems, networks and services of telecommunications</topic><topic>Telecommunication traffic</topic><topic>Telecommunications</topic><topic>Telecommunications and information theory</topic><topic>Teletraffic</topic><topic>Traffic control</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Ross, K.W.</creatorcontrib><creatorcontrib>Tsang, D.H.K.</creatorcontrib><collection>Pascal-Francis</collection><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><collection>Electronics &amp; Communications Abstracts</collection><jtitle>IEEE transactions on communications</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Ross, K.W.</au><au>Tsang, D.H.K.</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>The stochastic knapsack problem</atitle><jtitle>IEEE transactions on communications</jtitle><stitle>TCOMM</stitle><date>1989-07-01</date><risdate>1989</risdate><volume>37</volume><issue>7</issue><spage>740</spage><epage>747</epage><pages>740-747</pages><issn>0090-6778</issn><eissn>1558-0857</eissn><coden>IECMBT</coden><abstract>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.&lt; &gt;</abstract><cop>New York, NY</cop><pub>IEEE</pub><doi>10.1109/26.31166</doi><tpages>8</tpages></addata></record>
fulltext fulltext
identifier ISSN: 0090-6778
ispartof IEEE transactions on communications, 1989-07, Vol.37 (7), p.740-747
issn 0090-6778
1558-0857
language eng
recordid cdi_crossref_primary_10_1109_26_31166
source IEEE Xplore (Online service)
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
title The stochastic knapsack problem
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-28T14%3A43%3A18IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=The%20stochastic%20knapsack%20problem&rft.jtitle=IEEE%20transactions%20on%20communications&rft.au=Ross,%20K.W.&rft.date=1989-07-01&rft.volume=37&rft.issue=7&rft.spage=740&rft.epage=747&rft.pages=740-747&rft.issn=0090-6778&rft.eissn=1558-0857&rft.coden=IECMBT&rft_id=info:doi/10.1109/26.31166&rft_dat=%3Cproquest_cross%3E25519715%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c335t-49e6502216fe06b454f270baebfd61b8540533ea2f7c2902972b051dca878b133%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=25519715&rft_id=info:pmid/&rft_ieee_id=31166&rfr_iscdi=true