A stochastic linear knapsack problem

Shōgo Shiode, Hiroaki Ishi and Toshio Nishida

Naval Research Logistics (NRL), 1987, vol. 34, issue 5, 753-759

Abstract: In this article we consider a stochastic version of the continuous linear knapsack problem, i.e., a model with a random linear constraint, and provide an efficient algorithm for solving it. An original problem Po is first transformed into a deterministic equivalent problem Po. Furthermore, by a change of variables, Po is transformed into P. Then, in order to solve P, a subproblem P(μ.) with positive parameter μ is introduced, and a close relation between P and P(μ) is clarified. Furthermore, an auxiliary problem PR(μ) of P(μ) with positive parameter R is introduced, and a relation between PR(μ) and P(μ) is also clarified. From these relations, a direct relation connecting PR(μ) with P is derived. An efficient algorithm based on this relation for solving P is proposed. It is shown that time complexity of the algorithm is O(n log n), where n is the number of items. Finally, some further research problems are discussed.

Date: 1987
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/1520-6750(198710)34:53.0.CO;2-0

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:34:y:1987:i:5:p:753-759

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().