Premium
A stochastic linear knapsack problem
Author(s) -
Shiode Shōgo,
Ishi Hiroaki,
Nishida Toshio
Publication year - 1987
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/1520-6750(198710)34:5<753::aid-nav3220340514>3.0.co;2-0
Subject(s) - knapsack problem , mathematics , relation (database) , change making problem , cutting stock problem , mathematical optimization , constraint (computer aided design) , continuous knapsack problem , order (exchange) , combinatorics , discrete mathematics , time complexity , linear programming , optimization problem , computer science , geometry , finance , database , economics
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 P o is first transformed into a deterministic equivalent problem P o . Furthermore, by a change of variables, P o 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 P R (μ) of P (μ) with positive parameter R is introduced, and a relation between P R (μ) and P (μ) is also clarified. From these relations, a direct relation connecting P R (μ) 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.