IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v123y2000i2p394-407.html
   My bibliography  Save this article

Unbounded knapsack problem: Dynamic programming revisited

Author

Listed:
  • Andonov, R.
  • Poirriez, V.
  • Rajopadhye, S.

Abstract

No abstract is available for this item.

Suggested Citation

  • Andonov, R. & Poirriez, V. & Rajopadhye, S., 2000. "Unbounded knapsack problem: Dynamic programming revisited," European Journal of Operational Research, Elsevier, vol. 123(2), pages 394-407, June.
    • Handle: RePEc:eee:ejores:v:123:y:2000:i:2:p:394-407
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(99)00265-9
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Djangir A. Babayev & Fred Glover & Jennifer Ryan, 1997. "A New Knapsack Solution Approach by Integer Equivalent Aggregation and Consistency Determination," INFORMS Journal on Computing, INFORMS, vol. 9(1), pages 43-50, February.
    2. Valerio de Carvalho, J. M. & Guimaraes Rodrigues, A. J., 1995. "An LP-based approach to a two-stage cutting stock problem," European Journal of Operational Research, Elsevier, vol. 84(3), pages 580-589, August.
    3. P. C. Gilmore & R. E. Gomory, 1966. "The Theory and Computation of Knapsack Functions," Operations Research, INFORMS, vol. 14(6), pages 1045-1074, December.
    4. Prabhakant Sinha & Andris A. Zoltners, 1979. "The Multiple-Choice Knapsack Problem," Operations Research, INFORMS, vol. 27(3), pages 503-515, June.
    5. P. C. Gilmore & R. E. Gomory, 1963. "A Linear Programming Approach to the Cutting Stock Problem---Part II," Operations Research, INFORMS, vol. 11(6), pages 863-888, December.
    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. Jooken, Jorik & Leyman, Pieter & De Causmaecker, Patrick, 2023. "Features for the 0-1 knapsack problem based on inclusionwise maximal solutions," European Journal of Operational Research, Elsevier, vol. 311(1), pages 36-55.
    2. Liu, Yipeng & Koehler, Gary J., 2010. "Using modifications to Grover's Search algorithm for quantum global optimization," European Journal of Operational Research, Elsevier, vol. 207(2), pages 620-632, December.
    3. Rong, Aiying & Figueira, José Rui, 2013. "A reduction dynamic programming algorithm for the bi-objective integer knapsack problem," European Journal of Operational Research, Elsevier, vol. 231(2), pages 299-313.
    4. Leonardo Boncinelli & Alessio Muscillo & Paolo Pin, 2022. "Efficiency and Stability in a Process of Teams Formation," Dynamic Games and Applications, Springer, vol. 12(4), pages 1101-1129, December.
    5. Kohli, Rajeev & Krishnamurti, Ramesh & Mirchandani, Prakash, 2004. "Average performance of greedy heuristics for the integer knapsack problem," European Journal of Operational Research, Elsevier, vol. 154(1), pages 36-45, April.
    6. Y-J Seong & Y-G G & M-K Kang & C-W Kang, 2004. "An improved branch and bound algorithm for a strongly correlated unbounded knapsack problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(5), pages 547-552, May.
    7. Becker, Henrique & Buriol, Luciana S., 2019. "An empirical analysis of exact algorithms for the unbounded knapsack problem," European Journal of Operational Research, Elsevier, vol. 277(1), pages 84-99.
    8. Zhang-Hua Fu & Jin-Kao Hao, 2015. "Dynamic Programming Driven Memetic Search for the Steiner Tree Problem with Revenues, Budget, and Hop Constraints," INFORMS Journal on Computing, INFORMS, vol. 27(2), pages 221-237, May.
    9. Cui, Yaodong, 2006. "Generating optimal multi-segment cutting patterns for circular blanks in the manufacturing of electric motors," European Journal of Operational Research, Elsevier, vol. 169(1), pages 30-40, February.
    10. Hao, Xinye & Zheng, Li & Li, Na & Zhang, Canrong, 2022. "Integrated bin packing and lot-sizing problem considering the configuration-dependent bin packing process," European Journal of Operational Research, Elsevier, vol. 303(2), pages 581-592.
    11. Yang Yang, 2024. "An Improved Unbounded-DP Algorithm for the Unbounded Knapsack Problem with Bounded Coefficients," Mathematics, MDPI, vol. 12(12), pages 1-12, June.
    12. Huang, Ping H. & Lawley, Mark & Morin, Thomas, 2011. "Tight bounds for periodicity theorems on the unbounded Knapsack problem," European Journal of Operational Research, Elsevier, vol. 215(2), pages 319-324, December.

    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. Becker, Henrique & Buriol, Luciana S., 2019. "An empirical analysis of exact algorithms for the unbounded knapsack problem," European Journal of Operational Research, Elsevier, vol. 277(1), pages 84-99.
    2. Hoto, Robinson & Arenales, Marcos & Maculan, Nelson, 2007. "The one dimensional Compartmentalised Knapsack Problem: A case study," European Journal of Operational Research, Elsevier, vol. 183(3), pages 1183-1195, December.
    3. Song, X. & Chu, C.B. & Nie, Y.Y. & Bennell, J.A., 2006. "An iterative sequential heuristic procedure to a real-life 1.5-dimensional cutting stock problem," European Journal of Operational Research, Elsevier, vol. 175(3), pages 1870-1889, December.
    4. François Vanderbeck, 2001. "A Nested Decomposition Approach to a Three-Stage, Two-Dimensional Cutting-Stock Problem," Management Science, INFORMS, vol. 47(6), pages 864-879, June.
    5. Gomory, Ralph, 2016. "Origin and early evolution of corner polyhedra," European Journal of Operational Research, Elsevier, vol. 253(3), pages 543-556.
    6. Sierra-Paradinas, María & Soto-Sánchez, Óscar & Alonso-Ayuso, Antonio & Martín-Campo, F. Javier & Gallego, Micael, 2021. "An exact model for a slitting problem in the steel industry," European Journal of Operational Research, Elsevier, vol. 295(1), pages 336-347.
    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. Johnston, Robert E. & Khan, Lutfar R., 1995. "Bounds for nested knapsack problems," European Journal of Operational Research, Elsevier, vol. 81(1), pages 154-165, February.
    9. Yuen, Boon J., 1995. "Improved heuristics for sequencing cutting patterns," European Journal of Operational Research, Elsevier, vol. 87(1), pages 57-64, November.
    10. Leão, Aline A.S. & Santos, Maristela O. & Hoto, Robinson & Arenales, Marcos N., 2011. "The constrained compartmentalized knapsack problem: mathematical models and solution methods," European Journal of Operational Research, Elsevier, vol. 212(3), pages 455-463, August.
    11. Tao Wu & Kerem Akartunal? & Raf Jans & Zhe Liang, 2017. "Progressive Selection Method for the Coupled Lot-Sizing and Cutting-Stock Problem," INFORMS Journal on Computing, INFORMS, vol. 29(3), pages 523-543, August.
    12. Ben Messaoud, Said & Chu, Chengbin & Espinouse, Marie-Laure, 2008. "Characterization and modelling of guillotine constraints," European Journal of Operational Research, Elsevier, vol. 191(1), pages 112-126, November.
    13. Suliman, Saad M. A., 2001. "Pattern generating procedure for the cutting stock problem," International Journal of Production Economics, Elsevier, vol. 74(1-3), pages 293-301, December.
    14. Ralph E. Gomory, 2002. "Early Integer Programming," Operations Research, INFORMS, vol. 50(1), pages 78-81, February.
    15. Muter, İbrahim & Sezer, Zeynep, 2018. "Algorithms for the one-dimensional two-stage cutting stock problem," European Journal of Operational Research, Elsevier, vol. 271(1), pages 20-32.
    16. Nonas, Sigrid Lise & Thorstenson, Anders, 2000. "A combined cutting-stock and lot-sizing problem," European Journal of Operational Research, Elsevier, vol. 120(2), pages 327-342, January.
    17. Wang, Danni & Xiao, Fan & Zhou, Lei & Liang, Zhe, 2020. "Two-dimensional skiving and cutting stock problem with setup cost based on column-and-row generation," European Journal of Operational Research, Elsevier, vol. 286(2), pages 547-563.
    18. Arbib, Claudio & Marinelli, Fabrizio, 2005. "Integrating process optimization and inventory planning in cutting-stock with skiving option: An optimization model and its application," European Journal of Operational Research, Elsevier, vol. 163(3), pages 617-630, June.
    19. Zak, Eugene J., 2002. "Modeling multistage cutting stock problems," European Journal of Operational Research, Elsevier, vol. 141(2), pages 313-327, September.
    20. Mhand Hifi & Hedi Mhalla & Slim Sadfi, 2005. "Sensitivity of the Optimum to Perturbations of the Profit or Weight of an Item in the Binary Knapsack Problem," Journal of Combinatorial Optimization, Springer, vol. 10(3), pages 239-260, November.

    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:eee:ejores:v:123:y:2000:i:2:p:394-407. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.