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

Augmented Lagrangian algorithms for solving the continuous nonlinear resource allocation problem

Author

Listed:
  • Torrealba, E.M.R.
  • Silva, J.G.
  • Matioli, L.C.
  • Kolossoski, O.
  • Santos, P.S.M.

Abstract

We propose a class of algorithms for solving the continuous nonlinear resource allocation problem which is stated many times in the literature as the Knapsack problem. This problem is known for its diverse gamma of applications and we solve it by using a hybrid approach, i.e., we combine the augmented Lagrangian method with Newton’s method to solve the subproblem generated by it. In other words, at each step we minimize the augment ed Lagrangian using Newton’s method and project the solution on the box. Most of the papers in this area deal with quadratic separable problems. Our proposal is more general in the sense that the problem can be non-quadratic and non-separable. We present and discuss the convergence properties for the proposed method and we show numerical applications illustrating its competitiveness and robustness for solving different Knapsack problems.

Suggested Citation

  • Torrealba, E.M.R. & Silva, J.G. & Matioli, L.C. & Kolossoski, O. & Santos, P.S.M., 2022. "Augmented Lagrangian algorithms for solving the continuous nonlinear resource allocation problem," European Journal of Operational Research, Elsevier, vol. 299(1), pages 46-59.
    • Handle: RePEc:eee:ejores:v:299:y:2022:i:1:p:46-59
    DOI: 10.1016/j.ejor.2021.11.027
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221721009784
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2021.11.027?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
    ---><---

    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. K. C. Kiwiel, 2008. "Variable Fixing Algorithms for the Continuous Quadratic Knapsack Problem," Journal of Optimization Theory and Applications, Springer, vol. 136(3), pages 445-458, March.
    2. M. A. Diniz-Ehrhardt & M. A. Gomes-Ruggiero & J. M. Martínez & S. A. Santos, 2004. "Augmented Lagrangian Algorithms Based on the Spectral Projected Gradient Method for Solving Nonlinear Programming Problems," Journal of Optimization Theory and Applications, Springer, vol. 123(3), pages 497-517, December.
    3. Jong-Shi Pang, 1980. "A New and Efficient Algorithm for a Class of Portfolio Selection Problems," Operations Research, INFORMS, vol. 28(3-part-ii), pages 754-767, June.
    4. Bretthauer, Kurt M. & Shetty, Bala, 2002. "The nonlinear knapsack problem - algorithms and applications," European Journal of Operational Research, Elsevier, vol. 138(3), pages 459-472, May.
    5. Alberto Caprara & David Pisinger & Paolo Toth, 1999. "Exact Solution of the Quadratic Knapsack Problem," INFORMS Journal on Computing, INFORMS, vol. 11(2), pages 125-137, May.
    6. Stuart Smith & Leon Lasdon, 1992. "Solving Large Sparse Nonlinear Programs Using GRG," INFORMS Journal on Computing, INFORMS, vol. 4(1), pages 2-15, February.
    7. Patriksson, Michael, 2008. "A survey on the continuous nonlinear resource allocation problem," European Journal of Operational Research, Elsevier, vol. 185(1), pages 1-46, February.
    8. Patriksson, Michael & Strömberg, Christoffer, 2015. "Algorithms for the continuous nonlinear resource allocation problem—New implementations and numerical studies," European Journal of Operational Research, Elsevier, vol. 243(3), pages 703-722.
    9. Frangioni, Antonio & Gorgone, Enrico, 2013. "A library for continuous convex separable quadratic knapsack problems," European Journal of Operational Research, Elsevier, vol. 229(1), pages 37-40.
    10. Harry Markowitz, 1952. "Portfolio Selection," Journal of Finance, American Finance Association, vol. 7(1), pages 77-91, March.
    Full references (including those not matched with items on IDEAS)

    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. Patriksson, Michael, 2008. "A survey on the continuous nonlinear resource allocation problem," European Journal of Operational Research, Elsevier, vol. 185(1), pages 1-46, February.
    2. Hoto, R.S.V. & Matioli, L.C. & Santos, P.S.M., 2020. "A penalty algorithm for solving convex separable knapsack problems," Applied Mathematics and Computation, Elsevier, vol. 387(C).
    3. Patriksson, Michael & Strömberg, Christoffer, 2015. "Algorithms for the continuous nonlinear resource allocation problem—New implementations and numerical studies," European Journal of Operational Research, Elsevier, vol. 243(3), pages 703-722.
    4. Martijn H. H. Schoot Uiterkamp & Marco E. T. Gerards & Johann L. Hurink, 2022. "On a Reduction for a Class of Resource Allocation Problems," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1387-1402, May.
    5. Hsin-Min Sun & Ruey-Lin Sheu, 2019. "Minimum variance allocation among constrained intervals," Journal of Global Optimization, Springer, vol. 74(1), pages 21-44, May.
    6. Bretthauer, Kurt M. & Shetty, Bala, 2002. "The nonlinear knapsack problem - algorithms and applications," European Journal of Operational Research, Elsevier, vol. 138(3), pages 459-472, May.
    7. ten Eikelder, S.C.M. & van Amerongen, J.H.M., 2023. "Resource allocation problems with expensive function evaluations," European Journal of Operational Research, Elsevier, vol. 306(3), pages 1170-1185.
    8. Jungho Park & Hadi El-Amine & Nevin Mutlu, 2021. "An Exact Algorithm for Large-Scale Continuous Nonlinear Resource Allocation Problems with Minimax Regret Objectives," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 1213-1228, July.
    9. Chen, Wei & Zhang, Wei-Guo, 2010. "The admissible portfolio selection problem with transaction costs and an improved PSO algorithm," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 389(10), pages 2070-2076.
    10. Immanuel Bomze & Chen Ling & Liqun Qi & Xinzhen Zhang, 2012. "Standard bi-quadratic optimization problems and unconstrained polynomial reformulations," Journal of Global Optimization, Springer, vol. 52(4), pages 663-687, April.
    11. Zhang, Wei-Guo & Zhang, Xi-Li & Xiao, Wei-Lin, 2009. "Portfolio selection under possibilistic mean-variance utility and a SMO algorithm," European Journal of Operational Research, Elsevier, vol. 197(2), pages 693-700, September.
    12. Syam, Siddhartha S., 1998. "A dual ascent method for the portfolio selection problem with multiple constraints and linked proposals," European Journal of Operational Research, Elsevier, vol. 108(1), pages 196-207, July.
    13. Sathaye, Nakul & Madanat, Samer, 2011. "A bottom-up solution for the multi-facility optimal pavement resurfacing problem," Transportation Research Part B: Methodological, Elsevier, vol. 45(7), pages 1004-1017, August.
    14. G.-Fivos Sargentis & Theano Iliopoulou & Stavroula Sigourou & Panayiotis Dimitriadis & Demetris Koutsoyiannis, 2020. "Evolution of Clustering Quantified by a Stochastic Method—Case Studies on Natural and Human Social Structures," Sustainability, MDPI, vol. 12(19), pages 1-22, September.
    15. Zhang, Wei-Guo & Xiao, Wei-Lin & Xu, Wei-Jun, 2010. "A possibilistic portfolio adjusting model with new added assets," Economic Modelling, Elsevier, vol. 27(1), pages 208-213, January.
    16. Li, Ting & Zhang, Weiguo & Xu, Weijun, 2015. "A fuzzy portfolio selection model with background risk," Applied Mathematics and Computation, Elsevier, vol. 256(C), pages 505-513.
    17. Ruey-Chyn Tsaur, 2015. "Fuzzy portfolio model with fuzzy-input return rates and fuzzy-output proportions," International Journal of Systems Science, Taylor & Francis Journals, vol. 46(3), pages 438-450, February.
    18. Li, Ting & Zhang, Weiguo & Xu, Weijun, 2013. "Fuzzy possibilistic portfolio selection model with VaR constraint and risk-free investment," Economic Modelling, Elsevier, vol. 31(C), pages 12-17.
    19. Chernonog, Tatyana & Goldberg, Noam, 2018. "On the multi-product newsvendor with bounded demand distributions," International Journal of Production Economics, Elsevier, vol. 203(C), pages 38-47.
    20. Thijs Klauw & Marco E. T. Gerards & Johann L. Hurink, 2017. "Resource allocation problems in decentralized energy management," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 39(3), pages 749-773, July.

    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:299:y:2022:i:1:p:46-59. 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.