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

Shenshen Gu and Xinyi Chen
Additional contact information
Shenshen Gu: School of Mechatronic Engineering and Automation, Shanghai University, Shanghai 200444, China
Xinyi Chen: School of Mechatronic Engineering and Automation, Shanghai University, Shanghai 200444, China

Mathematics, 2020, vol. 8, issue 1, 1-16

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.

Keywords: zero-one quadratic problem; combinatorial optimization; k -diagonal matrix; power system (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/8/1/138/pdf (application/pdf)
https://www.mdpi.com/2227-7390/8/1/138/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:8:y:2020:i:1:p:138-:d:310488

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().