IDEAS home Printed from https://ideas.repec.org/a/spr/coopap/v66y2017i2d10.1007_s10589-016-9863-8.html
   My bibliography  Save this article

Fast algorithm for singly linearly constrained quadratic programs with box-like constraints

Author

Listed:
  • Meijiao Liu

    (Shenyang Aerospace University)

  • Yong-Jin Liu

    (Shenyang Aerospace University)

Abstract

This paper focuses on a singly linearly constrained class of convex quadratic programs with box-like constraints. We propose a new fast algorithm based on parametric approach and secant approximation method to solve this class of quadratic problems. We design efficient implementations for our proposed algorithm and compare its performance with two state-of-the-art standard solvers called Gurobi and Mosek. Numerical results on a variety of test problems demonstrate that our algorithm is able to efficiently solve the large-scale problems with the dimension up to fifty million and it substantially outperforms Gurobi and Mosek in terms of the running time.

Suggested Citation

  • Meijiao Liu & Yong-Jin Liu, 2017. "Fast algorithm for singly linearly constrained quadratic programs with box-like constraints," Computational Optimization and Applications, Springer, vol. 66(2), pages 309-326, March.
    • Handle: RePEc:spr:coopap:v:66:y:2017:i:2:d:10.1007_s10589-016-9863-8
    DOI: 10.1007/s10589-016-9863-8
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10589-016-9863-8
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10589-016-9863-8?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. Gabriel R. Bitran & Arnoldo C. Hax, 1981. "Disaggregation and Resource Allocation Using Convex Knapsack Problems with Bounded Variables," Management Science, INFORMS, vol. 27(4), pages 431-441, April.
    3. Steven Cosares & Dorit S. Hochbaum, 1994. "Strongly Polynomial Algorithms for the Quadratic Transportation Problem with a Fixed Number of Sources," Mathematics of Operations Research, INFORMS, vol. 19(1), pages 94-111, February.
    4. K. C. Kiwiel, 2007. "On Linear-Time Algorithms for the Continuous Quadratic Knapsack Problem," Journal of Optimization Theory and Applications, Springer, vol. 134(3), pages 549-554, September.
    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. 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).
    2. 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.
    3. 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.
    4. 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.
    5. Hezhi Luo & Xianye Zhang & Huixian Wu & Weiqiang Xu, 2023. "Effective algorithms for separable nonconvex quadratic programming with one quadratic and box constraints," Computational Optimization and Applications, Springer, vol. 86(1), pages 199-240, September.
    6. 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.
    7. 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.
    8. Walter, Rico & Boysen, Nils & Scholl, Armin, 2013. "The discrete forward–reserve problem – Allocating space, selecting products, and area sizing in forward order picking," European Journal of Operational Research, Elsevier, vol. 229(3), pages 585-594.
    9. Chunli Liu & Jianjun Gao, 2015. "A polynomial case of convex integer quadratic programming problems with box integer constraints," Journal of Global Optimization, Springer, vol. 62(4), pages 661-674, August.
    10. Muralidharan S. Kodialam & Hanan Luss, 1998. "Algorithms for Separable Nonlinear Resource Allocation Problems," Operations Research, INFORMS, vol. 46(2), pages 272-284, April.
    11. Bretthauer, Kurt M. & Ross, Anthony & Shetty, Bala, 1999. "Nonlinear integer programming for optimal allocation in stratified sampling," European Journal of Operational Research, Elsevier, vol. 116(3), pages 667-680, August.
    12. P. Tseng & S. Yun, 2009. "Block-Coordinate Gradient Descent Method for Linearly Constrained Nonsmooth Separable Optimization," Journal of Optimization Theory and Applications, Springer, vol. 140(3), pages 513-535, March.
    13. De Waegenaere, A.M.B. & Wielhouwer, J.L., 2001. "A Partial Ranking Algorithm for Resource Allocation Problems," Other publications TiSEM 8b2e0185-36f9-43df-8a3d-d, Tilburg University, School of Economics and Management.
    14. Aboolian, Robert & Berman, Oded & Krass, Dmitry, 2021. "Optimizing facility location and design," European Journal of Operational Research, Elsevier, vol. 289(1), pages 31-43.
    15. Bintong Chen & Charles L. Munson, 2004. "Resource allocation with lumpy demand: To speed or not to speed?," Naval Research Logistics (NRL), John Wiley & Sons, vol. 51(3), pages 363-385, April.
    16. Vogel, Sebastian & Meyr, Herbert, 2015. "Decentral allocation planning in multi-stage customer hierarchies," European Journal of Operational Research, Elsevier, vol. 246(2), pages 462-470.
    17. De Waegenaere, A.M.B. & Wielhouwer, J.L., 2001. "A Partial Ranking Algorithm for Resource Allocation Problems," Discussion Paper 2001-40, Tilburg University, Center for Economic Research.
    18. Kameshwaran, S. & Narahari, Y., 2009. "Nonconvex piecewise linear knapsack problems," European Journal of Operational Research, Elsevier, vol. 192(1), pages 56-68, January.
    19. Zhang, Bin & Hua, Zhongsheng, 2008. "A unified method for a class of convex separable nonlinear knapsack problems," European Journal of Operational Research, Elsevier, vol. 191(1), pages 1-6, November.
    20. 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.

    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:spr:coopap:v:66:y:2017:i:2:d:10.1007_s10589-016-9863-8. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.