IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v8y2020i3p315-d326742.html
   My bibliography  Save this article

Output-Space Branch-and-Bound Reduction Algorithm for a Class of Linear Multiplicative Programs

Author

Listed:
  • Bo Zhang

    (School of Mathematics and Statistics, Ningxia University, Yinchuan 750021, China)

  • Yuelin Gao

    (Ningxia Province Cooperative Innovation Center of Scientific Computing and Intelligent Information Processing, North Minzu University, Yinchuan 750021, China
    Ningxia Province Key Laboratory of Intelligent Information and Data Processing, North Minzu University, Yinchuan 750021, China)

  • Xia Liu

    (School of Mathematics and Statistics, Ningxia University, Yinchuan 750021, China)

  • Xiaoli Huang

    (Ningxia Province Cooperative Innovation Center of Scientific Computing and Intelligent Information Processing, North Minzu University, Yinchuan 750021, China
    Ningxia Province Key Laboratory of Intelligent Information and Data Processing, North Minzu University, Yinchuan 750021, China)

Abstract

In this paper, a new relaxation bounding method is proposed for a class of linear multiplicative programs. Although the 2 p − 1 variable is introduced in the construction of equivalence problem, the branch process of the algorithm is only carried out in p − dimensional space. In addition, a super-rectangular reduction technique is also given to greatly improve the convergence rate. Furthermore, we construct an output-space branch-and-bound reduction algorithm based on solving a series of linear programming sub-problems, and prove the convergence and computational complexity of the algorithm. Finally, to verify the feasibility and effectiveness of the algorithm, we carried out a series of numerical experiments and analyzed the advantages and disadvantages of the algorithm by numerical results.

Suggested Citation

  • Bo Zhang & Yuelin Gao & Xia Liu & Xiaoli Huang, 2020. "Output-Space Branch-and-Bound Reduction Algorithm for a Class of Linear Multiplicative Programs," Mathematics, MDPI, vol. 8(3), pages 1-34, March.
    • Handle: RePEc:gam:jmathe:v:8:y:2020:i:3:p:315-:d:326742
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/8/3/315/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/8/3/315/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Maranas, C. D. & Androulakis, I. P. & Floudas, C. A. & Berger, A. J. & Mulvey, J. M., 1997. "Solving long-term financial planning problems via global optimization," Journal of Economic Dynamics and Control, Elsevier, vol. 21(8-9), pages 1405-1425, June.
    2. H. P. Benson, 2005. "Decomposition Branch-and-Bound Based Algorithm for Linear Programs with Additional Multiplicative Constraints," Journal of Optimization Theory and Applications, Springer, vol. 126(1), pages 41-61, July.
    3. H. P. Benson & G. M. Boger, 2000. "Outcome-Space Cutting-Plane Algorithm for Linear Multiplicative Programming," Journal of Optimization Theory and Applications, Springer, vol. 104(2), pages 301-322, February.
    4. H. P. Benson & G. M. Boger, 1997. "Multiplicative Programming Problems: Analysis and Efficient Point Search Heuristic," Journal of Optimization Theory and Applications, Springer, vol. 94(2), pages 487-510, August.
    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. Gao, YueLin & Zhang, Bo, 2023. "Output-space branch-and-bound reduction algorithm for generalized linear fractional-multiplicative programming problem," Chaos, Solitons & Fractals, Elsevier, vol. 175(P1).

    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. Gao, YueLin & Zhang, Bo, 2023. "Output-space branch-and-bound reduction algorithm for generalized linear fractional-multiplicative programming problem," Chaos, Solitons & Fractals, Elsevier, vol. 175(P1).
    2. 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.
    3. Lizhen Shao & Matthias Ehrgott, 2014. "An objective space cut and bound algorithm for convex multiplicative programmes," Journal of Global Optimization, Springer, vol. 58(4), pages 711-728, April.
    4. Peiping Shen & Kaimin Wang & Ting Lu, 2020. "Outer space branch and bound algorithm for solving linear multiplicative programming problems," Journal of Global Optimization, Springer, vol. 78(3), pages 453-482, November.
    5. Hongwei Jiao & Binbin Li & Wenqiang Yang, 2024. "A criterion-space branch-reduction-bound algorithm for solving generalized multiplicative problems," Journal of Global Optimization, Springer, vol. 89(3), pages 597-632, July.
    6. H. P. Benson & G. M. Boger, 2000. "Outcome-Space Cutting-Plane Algorithm for Linear Multiplicative Programming," Journal of Optimization Theory and Applications, Springer, vol. 104(2), pages 301-322, February.
    7. Yuichi Takano & Renata Sotirov, 2012. "A polynomial optimization approach to constant rebalanced portfolio selection," Computational Optimization and Applications, Springer, vol. 52(3), pages 645-666, July.
    8. Rong, Aiying & Lahdelma, Risto, 2007. "CO2 emissions trading planning in combined heat and power production via multi-period stochastic optimization," European Journal of Operational Research, Elsevier, vol. 176(3), pages 1874-1895, February.
    9. Tokat, Yesim & Rachev, Svetlozar T. & Schwartz, Eduardo, 2000. "The Stable non-Gaussian Asset Allocation: A Comparison with the Classical Gaussian Approach," University of California at Santa Barbara, Economics Working Paper Series qt9ph6b5gp, Department of Economics, UC Santa Barbara.
    10. Peiping Shen & Dianxiao Wu & Kaimin Wang, 2023. "Globally minimizing a class of linear multiplicative forms via simplicial branch-and-bound," Journal of Global Optimization, Springer, vol. 86(2), pages 303-321, June.
    11. T. Kuno, 1999. "Solving a Class of Multiplicative Programs with 0–1 Knapsack Constraints," Journal of Optimization Theory and Applications, Springer, vol. 103(1), pages 121-135, October.
    12. Tokat, Yesim & Rachev, Svetlozar T. & Schwartz, Eduardo S., 2003. "The stable non-Gaussian asset allocation: a comparison with the classical Gaussian approach," Journal of Economic Dynamics and Control, Elsevier, vol. 27(6), pages 937-969, April.
    13. Mustapha El Moudden & Ahmed El Ghali, 2018. "A new reduced gradient method for solving linearly constrained multiobjective optimization problems," Computational Optimization and Applications, Springer, vol. 71(3), pages 719-741, December.
    14. Benati, Stefano, 2003. "The optimal portfolio problem with coherent risk measure constraints," European Journal of Operational Research, Elsevier, vol. 150(3), pages 572-584, November.
    15. Yuichi Takano & Jun-ya Gotoh, 2011. "Constant Rebalanced Portfolio Optimization Under Nonlinear Transaction Costs," Asia-Pacific Financial Markets, Springer;Japanese Association of Financial Economics and Engineering, vol. 18(2), pages 191-211, May.
    16. Dormidontova, Yulia & Nazarov, Vladimir & A. Tikhonova, 2014. "Analysis of Approaches of Participants of Pension Products Market to the Development of Optimal Investment Strategies of Pension Savings," Published Papers r90227, Russian Presidential Academy of National Economy and Public Administration.
    17. Ruth Misener & Christodoulos Floudas, 2013. "GloMIQO: Global mixed-integer quadratic optimizer," Journal of Global Optimization, Springer, vol. 57(1), pages 3-50, September.
    18. Daniele Depetrini & Marco Locatelli, 2009. "A FPTAS for a class of linear multiplicative problems," Computational Optimization and Applications, Springer, vol. 44(2), pages 275-288, November.
    19. Alberto Caprara & Marco Locatelli & Michele Monaci, 2016. "Theoretical and computational results about optimality-based domain reductions," Computational Optimization and Applications, Springer, vol. 64(2), pages 513-533, June.
    20. Benson, Harold P. & Sun, Erjiang, 2009. "Branch-and-reduce algorithm for convex programs with additional multiplicative constraints," European Journal of Operational Research, Elsevier, vol. 199(1), pages 1-8, November.

    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:gam:jmathe:v:8:y:2020:i:3:p:315-:d:326742. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.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.