IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v15y1969i9p494-505.html
   My bibliography  Save this article

Discrete Dynamic Programming and Capital Allocation

Author

Listed:
  • G. L. Nemhauser

    (The Johns Hopkins University)

  • Z. Ullmann

    (Stanford Research Institute, Menlo Park, California)

Abstract

Dynamic programming algorithms are developed for optimal capital allocation subject to budget constraints. We extend the work of Weingartner [Weingartner, H. M. 1966. Capital budgeting of interrelated projects: Survey and synthesis. Management Sci. 12(7, March) 485-516.] and Weingartner and Ness [Weingartner, H. M., D. N. Ness. 1967. Methods for the solution of the multi-dimensional 0/1 knapsack problem. Oper. Res. 15(1, January-February) 83-108.] by including multilevel projects, reinvesting returns, borrowing and lending, capital deferrals, and project interactions. We are able to handle dynamic programming models with several state variables because the optimal returns are monotone non-decreasing step functions. Computational experience with a variety of problems is reported.

Suggested Citation

  • G. L. Nemhauser & Z. Ullmann, 1969. "Discrete Dynamic Programming and Capital Allocation," Management Science, INFORMS, vol. 15(9), pages 494-505, May.
    • Handle: RePEc:inm:ormnsc:v:15:y:1969:i:9:p:494-505
    DOI: 10.1287/mnsc.15.9.494
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.15.9.494
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.15.9.494?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
    ---><---

    Citations

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


    Cited by:

    1. Malaguti, Enrico & Monaci, Michele & Paronuzzi, Paolo & Pferschy, Ulrich, 2019. "Integer optimization with penalized fractional values: The Knapsack case," European Journal of Operational Research, Elsevier, vol. 273(3), pages 874-888.
    2. Raquel Sanchis & Raúl Poler, 2019. "Enterprise Resilience Assessment—A Quantitative Approach," Sustainability, MDPI, vol. 11(16), pages 1-13, August.
    3. Fritz Bökler & Markus Chimani & Mirko H. Wagner, 2022. "On the rectangular knapsack problem," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 96(1), pages 149-160, August.
    4. Santhanam, Radhika & Kyparisis, George J., 1996. "A decision model for interdependent information system project selection," European Journal of Operational Research, Elsevier, vol. 89(2), pages 380-399, March.
    5. Setzer, Thomas & Blanc, Sebastian M., 2020. "Empirical orthogonal constraint generation for Multidimensional 0/1 Knapsack Problems," European Journal of Operational Research, Elsevier, vol. 282(1), pages 58-70.
    6. Fujimoto, Masako & Yamada, Takeo, 2006. "An exact algorithm for the knapsack sharing problem with common items," European Journal of Operational Research, Elsevier, vol. 171(2), pages 693-707, June.
    7. Wilbaut, Christophe & Todosijevic, Raca & Hanafi, Saïd & Fréville, Arnaud, 2023. "Heuristic and exact reduction procedures to solve the discounted 0–1 knapsack problem," European Journal of Operational Research, Elsevier, vol. 304(3), pages 901-911.
    8. Bagloee, Saeed Asadi & Asadi, Mohsen, 2015. "Prioritizing road extension projects with interdependent benefits under time constraint," Transportation Research Part A: Policy and Practice, Elsevier, vol. 75(C), pages 196-216.
    9. Evgenii Burashnikov, 2024. "Branch-and-Bound and Dynamic Programming Approaches for the Knapsack Problem," SN Operations Research Forum, Springer, vol. 5(4), pages 1-19, December.
    10. Medaglia, Andres L. & Graves, Samuel B. & Ringuest, Jeffrey L., 2007. "A multiobjective evolutionary approach for linearly constrained project selection under uncertainty," European Journal of Operational Research, Elsevier, vol. 179(3), pages 869-894, June.
    11. Christian Meier & Dennis Kundisch & Jochen Willeke, 2017. "Is it Worth the Effort?," Business & Information Systems Engineering: The International Journal of WIRTSCHAFTSINFORMATIK, Springer;Gesellschaft für Informatik e.V. (GI), vol. 59(2), pages 81-95, April.
    12. Vinay Dharmadhikari, 1975. "Decision-Stage Method: Convergence Proof, Special Application, and Computation Experience," NBER Working Papers 0094, National Bureau of Economic Research, Inc.
    13. Vöcking, Berthold, 2019. "A universally-truthful approximation scheme for multi-unit auctions," Games and Economic Behavior, Elsevier, vol. 113(C), pages 4-16.
    14. Freville, Arnaud, 2004. "The multidimensional 0-1 knapsack problem: An overview," European Journal of Operational Research, Elsevier, vol. 155(1), pages 1-21, May.
    15. Ye Tian & Miao Sun & Zuoliang Ye & Wei Yang, 2016. "Expanded models of the project portfolio selection problem with loss in divisibility," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 67(8), pages 1097-1107, August.
    16. Jamain, Florian, 2014. "Représentations discrètes de l'ensemble des points non dominés pour des problèmes d'optimisation multi-objectifs," Economics Thesis from University Paris Dauphine, Paris Dauphine University, number 123456789/14002 edited by Bazgan, Cristina.
    17. Bazgan, Cristina & Hugot, Hadrien & Vanderpooten, Daniel, 2009. "Implementing an efficient fptas for the 0-1 multi-objective knapsack problem," European Journal of Operational Research, Elsevier, vol. 198(1), pages 47-56, October.
    18. Alexandre D. Jesus & Luís Paquete & Arnaud Liefooghe, 2021. "A model of anytime algorithm performance for bi-objective optimization," Journal of Global Optimization, Springer, vol. 79(2), pages 329-350, February.
    19. José Figueira & Luís Paquete & Marco Simões & Daniel Vanderpooten, 2013. "Algorithmic improvements on dynamic programming for the bi-objective {0,1} knapsack problem," Computational Optimization and Applications, Springer, vol. 56(1), pages 97-111, September.

    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:inm:ormnsc:v:15:y:1969:i:9:p:494-505. 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.

    We have no bibliographic references for this item. You can help adding them by using 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.