IDEAS home Printed from https://ideas.repec.org/a/wly/navres/v40y1993i2p161-173.html
   My bibliography  Save this article

An algorithm for maximizing target achievement in the stochastic knapsack problem with normal returns

Author

Listed:
  • Robert L. Carraway
  • Robert L. Schmidt
  • Lawrence R. Weatherford

Abstract

We consider the stochastic linear knapsack problem in which costs are known with certainty but returns are independent, normally distributed random variables. The objective is to maximize the probability that the overall return equals or exceeds a specified target value. A previously proposed preference order dynamic programming‐based algorithm has been shown to be potentially suboptimal. We offer an alternative hybrid DP/branch‐and‐bound algorithm that both guarantees optimality and significantly outperforms generating the set of Pareto optimal returns.© 1993 John Wiley & Sons, Inc.

Suggested Citation

  • Robert L. Carraway & Robert L. Schmidt & Lawrence R. Weatherford, 1993. "An algorithm for maximizing target achievement in the stochastic knapsack problem with normal returns," Naval Research Logistics (NRL), John Wiley & Sons, vol. 40(2), pages 161-173, March.
    • Handle: RePEc:wly:navres:v:40:y:1993:i:2:p:161-173
    DOI: 10.1002/nav.3220400203
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/nav.3220400203
    Download Restriction: no
    File URL: https://libkey.io/10.1002/nav.3220400203?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Thomas L. Morin & Roy E. Marsten, 1976. "Branch-and-Bound Strategies for Dynamic Programming," Operations Research, INFORMS, vol. 24(4), pages 611-627, August.
    2. Arthur M. Geoffrion, 1967. "Solving Bicriterion Mathematical Programs," Operations Research, INFORMS, vol. 15(1), pages 39-54, February.
    3. L. G. Mitten, 1964. "Composition Principles for Synthesis of Optimal Multistage Processes," Operations Research, INFORMS, vol. 12(4), pages 610-619, August.
    4. Henig, Mordechai I., 1986. "The shortest path problem with two objective functions," European Journal of Operational Research, Elsevier, vol. 25(2), pages 281-291, May.
    5. Robert L. Carraway & Thomas L. Morin & Herbert Moskowitz, 1989. "Generalized Dynamic Programming for Stochastic Combinatorial Optimization," Operations Research, INFORMS, vol. 37(5), pages 819-829, October.
    6. Bawa, Vijay S., 1975. "Optimal rules for ordering uncertain prospects," Journal of Financial Economics, Elsevier, vol. 2(1), pages 95-121, March.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Yasemin Merzifonluoglu & Joseph Geunes, 2021. "The Risk-Averse Static Stochastic Knapsack Problem," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 931-948, July.
    2. Will Ma, 2018. "Improvements and Generalizations of Stochastic Knapsack and Markovian Bandits Approximation Algorithms," Mathematics of Operations Research, INFORMS, vol. 43(3), pages 789-812, August.
    3. Brian C. Dean & Michel X. Goemans & Jan Vondrák, 2008. "Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity," Mathematics of Operations Research, INFORMS, vol. 33(4), pages 945-964, November.
    4. Anton J. Kleywegt & Jason D. Papastavrou, 2001. "The Dynamic and Stochastic Knapsack Problem with Random Sized Items," Operations Research, INFORMS, vol. 49(1), pages 26-41, February.
    5. Taylan İlhan & Seyed M. R. Iravani & Mark S. Daskin, 2011. "TECHNICAL NOTE---The Adaptive Knapsack Problem with Stochastic Rewards," Operations Research, INFORMS, vol. 59(1), pages 242-248, February.
    6. Jian Li & Amol Deshpande, 2019. "Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems," Mathematics of Operations Research, INFORMS, vol. 44(1), pages 354-375, February.
    7. Stefanie Kosuch & Abdel Lisser, 2010. "Upper bounds for the 0-1 stochastic knapsack problem and a B&B algorithm," Annals of Operations Research, Springer, vol. 176(1), pages 77-93, April.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Oliver Linton & Esfandiar Maasoumi & Yoon-Jae Wang, 2002. "Consistent testing for stochastic dominance: a subsampling approach," CeMMAP working papers 03/02, Institute for Fiscal Studies.
    2. Malavasi, Matteo & Ortobelli Lozza, Sergio & Trück, Stefan, 2021. "Second order of stochastic dominance efficiency vs mean variance efficiency," European Journal of Operational Research, Elsevier, vol. 290(3), pages 1192-1206.
    3. Gérard Colson, 1993. "Prenons-nous assez de risque dans les théories du risque?," L'Actualité Economique, Société Canadienne de Science Economique, vol. 69(1), pages 111-141.
    4. Härdle, Wolfgang Karl & Schulz, Rainer & Xie, Taojun, 2019. "Cooling Measures and Housing Wealth: Evidence from Singapore," IRTG 1792 Discussion Papers 2019-001, Humboldt University of Berlin, International Research Training Group 1792 "High Dimensional Nonstationary Time Series".
    5. Atwood, Joseph & Shaik, Saleem, 2020. "Theory and statistical properties of Quantile Data Envelopment Analysis," European Journal of Operational Research, Elsevier, vol. 286(2), pages 649-661.
    6. Furman, Edward & Landsman, Zinoviy, 2010. "Multivariate Tweedie distributions and some related capital-at-risk analyses," Insurance: Mathematics and Economics, Elsevier, vol. 46(2), pages 351-361, April.
    7. Rui Pedro Brito & Hélder Sebastião & Pedro Godinho, 2016. "Efficient skewness/semivariance portfolios," Journal of Asset Management, Palgrave Macmillan, vol. 17(5), pages 331-346, September.
    8. Elie Matta & Jean McGuire, 2008. "Too Risky to Hold? The Effect of Downside Risk, Accumulated Equity Wealth, and Firm Performance on CEO Equity Reduction," Organization Science, INFORMS, vol. 19(4), pages 567-580, August.
    9. Raymond H. Chan & Ephraim Clark & Xu Guo & Wing-Keung Wong, 2020. "New development on the third-order stochastic dominance for risk-averse and risk-seeking investors with application in risk management," Risk Management, Palgrave Macmillan, vol. 22(2), pages 108-132, June.
    10. Brogan, Anita J. & Stidham Jr., Shaler, 2008. "Non-separation in the mean-lower-partial-moment portfolio optimization problem," European Journal of Operational Research, Elsevier, vol. 184(2), pages 701-710, January.
    11. Yao, Haixiang & Huang, Jinbo & Li, Yong & Humphrey, Jacquelyn E., 2021. "A general approach to smooth and convex portfolio optimization using lower partial moments," Journal of Banking & Finance, Elsevier, vol. 129(C).
    12. Roxana Chiriac & Valeri Voev, 2011. "Modelling and forecasting multivariate realized volatility," Journal of Applied Econometrics, John Wiley & Sons, Ltd., vol. 26(6), pages 922-947, September.
    13. Tavakoli Baghdadabad, Mohammad Reza, 2014. "Average drawdown risk reduction and risk tolerances," Research in Economics, Elsevier, vol. 68(3), pages 264-276.
    14. Luo, Yao, 2020. "Unobserved heterogeneity in auctions under restricted stochastic dominance," Journal of Econometrics, Elsevier, vol. 216(2), pages 354-374.
    15. Cristiano Arbex Valle & John E Beasley & Nigel Meade, 2024. "Subset second-order stochastic dominance for enhanced indexation with diversification enforced by sector constraints," Papers 2404.16777, arXiv.org, revised Nov 2024.
    16. Wolfgang Karl Hardle & Rainer Schulz & Taojun Sie, 2021. "Cooling Measures and Housing Wealth: Evidence from Singapore," Papers 2108.11915, arXiv.org.
    17. Ortobelli, Sergio & Rachev, Svetlozar & Schwartz, Eduardo, 2000. "The Problem of Optimal Asset Allocation with Stable Distributed Returns," University of California at Los Angeles, Anderson Graduate School of Management qt3zd6q86c, Anderson Graduate School of Management, UCLA.
    18. Franklin G. Mixon Jr. & Richard J. Cebula, 2022. "Property Rights Freedom and Innovation: Eponymous Skills in Women's Gymnastics," Journal of Sports Economics, , vol. 23(4), pages 407-430, May.
    19. Danielsson, Jon & Jorgensen, Bjorn N. & Sarma, Mandira & de Vries, Casper G., 2006. "Comparing downside risk measures for heavy tailed distributions," Economics Letters, Elsevier, vol. 92(2), pages 202-208, August.
    20. Boddiford, Ashley N. & Kaufman, Daniel E. & Skipper, Daphne E. & Uhan, Nelson A., 2023. "Approximating a linear multiplicative objective in watershed management optimization," European Journal of Operational Research, Elsevier, vol. 305(2), pages 547-561.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:wly:navres:v:40:y:1993:i:2:p:161-173. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Wiley Content Delivery (email available below). General contact details of provider: https://doi.org/10.1002/(ISSN)1520-6750 .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.