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

The Basic Algorithm for the Constrained Zero-One Quadratic Programming Problem with k -diagonal Matrix and Its Application in the Power System

Author

Listed:
  • Shenshen Gu

    (School of Mechatronic Engineering and Automation, Shanghai University, Shanghai 200444, China
    Current address: 99 Shangda Road, Shanghai 200444, China.)

  • Xinyi Chen

    (School of Mechatronic Engineering and Automation, Shanghai University, Shanghai 200444, China)

Abstract

Zero-one quadratic programming is a classical combinatorial optimization problem that has many real-world applications. However, it is well known that zero-one quadratic programming is non-deterministic polynomial-hard (NP-hard) in general. On one hand, the exact solution algorithms that can guarantee the global optimum are very time consuming. And on the other hand, the heuristic algorithms that generate the solution quickly can only provide local optimum. Due to this reason, identifying polynomially solvable subclasses of zero-one quadratic programming problems and their corresponding algorithms is a promising way to not only compromise these two sides but also offer theoretical insight into the complicated nature of the problem. By combining the basic algorithm and dynamic programming method, we propose an effective algorithm in this paper to solve the general linearly constrained zero-one quadratic programming problem with a k -diagonal matrix. In our algorithm, the value of k is changeable that covers different subclasses of the problem. The theoretical analysis and experimental results reveal that our proposed algorithm is reasonably effective and efficient. In addition, the placement of the phasor measurement units problem in the power system is adopted as an example to illustrate the potential real-world applications of this algorithm.

Suggested Citation

  • Shenshen Gu & Xinyi Chen, 2020. "The Basic Algorithm for the Constrained Zero-One Quadratic Programming Problem with k -diagonal Matrix and Its Application in the Power System," Mathematics, MDPI, vol. 8(1), pages 1-16, January.
    • Handle: RePEc:gam:jmathe:v:8:y:2020:i:1:p:138-:d:310488
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. W. X. Zhu, 2003. "Penalty Parameter for Linearly Constrained 0–1 Quadratic Programming," Journal of Optimization Theory and Applications, Springer, vol. 116(1), pages 229-239, January.
    2. Katayama, Kengo & Narihisa, Hiroyuki, 2001. "Performance of simulated annealing-based heuristic for the unconstrained binary quadratic programming problem," European Journal of Operational Research, Elsevier, vol. 134(1), pages 103-119, October.
    3. D. Li & X. Sun & C. Liu, 2012. "An exact solution method for unconstrained quadratic 0–1 programming: a geometric approach," Journal of Global Optimization, Springer, vol. 52(4), pages 797-829, April.
    4. D. J. Laughhunn, 1970. "Quadratic Binary Programming with Application to Capital-Budgeting Problems," Operations Research, INFORMS, vol. 18(3), pages 454-461, June.
    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. Gary Kochenberger & Jin-Kao Hao & Fred Glover & Mark Lewis & Zhipeng Lü & Haibo Wang & Yang Wang, 2014. "The unconstrained binary quadratic programming problem: a survey," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 58-81, July.
    2. Gili Rosenberg & Mohammad Vazifeh & Brad Woods & Eldad Haber, 2016. "Building an iterative heuristic solver for a quantum annealer," Computational Optimization and Applications, Springer, vol. 65(3), pages 845-869, December.
    3. Wang, Yang & Lü, Zhipeng & Glover, Fred & Hao, Jin-Kao, 2012. "Path relinking for unconstrained binary quadratic programming," European Journal of Operational Research, Elsevier, vol. 223(3), pages 595-604.
    4. 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.
    5. Billionnet, Alain & Calmels, Frederic, 1996. "Linear programming for the 0-1 quadratic knapsack problem," European Journal of Operational Research, Elsevier, vol. 92(2), pages 310-325, July.
    6. 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.
    7. Yi Liao & Ali Diabat & Chaher Alzaman & Yiqiang Zhang, 2020. "Modeling and heuristics for production time crashing in supply chain network design," Annals of Operations Research, Springer, vol. 288(1), pages 331-361, May.
    8. Richard J. Forrester & Warren P. Adams & Paul T. Hadavas, 2010. "Concise RLT forms of binary programs: A computational study of the quadratic knapsack problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 57(1), pages 1-12, February.
    9. Lü, Zhipeng & Glover, Fred & Hao, Jin-Kao, 2010. "A hybrid metaheuristic approach to solving the UBQP problem," European Journal of Operational Research, Elsevier, vol. 207(3), pages 1254-1262, December.
    10. Zhuqi Miao & Balabhaskar Balasundaram, 2020. "An Ellipsoidal Bounding Scheme for the Quasi-Clique Number of a Graph," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 763-778, July.
    11. Lin, Shih-Wei & Ying, Kuo-Ching & Lu, Chung-Cheng & Gupta, Jatinder N.D., 2011. "Applying multi-start simulated annealing to schedule a flowline manufacturing cell with sequence dependent family setup times," International Journal of Production Economics, Elsevier, vol. 130(2), pages 246-254, April.
    12. S. Lucidi & F. Rinaldi, 2010. "Exact Penalty Functions for Nonlinear Integer Programming Problems," Journal of Optimization Theory and Applications, Springer, vol. 145(3), pages 479-488, June.
    13. Xiaojin Zheng & Xiaoling Sun & Duan Li & Yong Xia, 2010. "Duality Gap Estimation of Linear Equality Constrained Binary Quadratic Programming," Mathematics of Operations Research, INFORMS, vol. 35(4), pages 864-880, November.
    14. Billionnet, Alain & Faye, Alain & Soutif, Eric, 1999. "A new upper bound for the 0-1 quadratic knapsack problem," European Journal of Operational Research, Elsevier, vol. 112(3), pages 664-672, February.
    15. Marianna De Santis & Sven de Vries & Martin Schmidt & Lukas Winkel, 2022. "A Penalty Branch-and-Bound Method for Mixed Binary Linear Complementarity Problems," INFORMS Journal on Computing, INFORMS, vol. 34(6), pages 3117-3133, November.
    16. Sourour Elloumi & Amélie Lambert & Arnaud Lazare, 2021. "Solving unconstrained 0-1 polynomial programs through quadratic convex reformulation," Journal of Global Optimization, Springer, vol. 80(2), pages 231-248, June.
    17. M. Santis & F. Rinaldi, 2012. "Continuous Reformulations for Zero–One Programming Problems," Journal of Optimization Theory and Applications, Springer, vol. 153(1), pages 75-84, April.
    18. C. Helmberg & F. Rendl & R. Weismantel, 2000. "A Semidefinite Programming Approach to the Quadratic Knapsack Problem," Journal of Combinatorial Optimization, Springer, vol. 4(2), pages 197-215, June.

    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:1:p:138-:d:310488. 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.