1 Fully and partially distributed Quantum Generalized Benders Decomposition for Unit Commitment Problems

2025-04-24 0 0 2.16MB 30 页 10玖币

侵权投诉

Fully and partially distributed Quantum Generalized Benders

Decomposition for Unit Commitment Problems

Fang Gao1, Dejian Huang1, Ziwei Zhao1, Wei Dai1, *, Mingyu Yang1, Qing Gao2 and Yu Pan3

1School of Electrical Engineering, Guangxi University, Nanning, 530004, China

2Hangzhou Innovation Institute of Beihang University, Hangzhou, 310051, China

3College of Control Science and Engineering, Zhejiang University, Hangzhou 310027, China

A series of hybrid quantum-classical generalized Benders decomposition (GBD) algorithms are

proposed to address unit commitment (UC) problems under centralized, distributed, and

partially distributed frameworks. In the centralized approach, the quantum GBD transforms the

master problem (MP) into a quadratic unconstrained binary optimization form suitable for

quantum computing. For distributed systems, the distributed consensus quantum GBD employs

an average consensus strategy to reformulate subproblems into local subproblems. By

leveraging the dual information, local cutting planes are constructed to decompose the MP into

local master problems (LMPs). This approach reduces the qubit overhead and addresses the

partitioning requirements. The consensus-inspired quantum GBD (CIQGBD) and its partially

distributed variant, D-CIQGBD are proposed based on optimizing the allocation of relaxation

variables directly, the algorithms construct more rational cutting planes, thereby enhancing the

minimum eigenenergy gap of the system Hamiltonian during quantum annealing and improving

the computational efficiency. Extensive experiments under various UC scenarios validate the

performance of the above-mentioned hybrid algorithms. Compared to the classical solver

Gurobi, D-CIQGBD demonstrates a speed advantage in solving the security-constrained UC

problem on the IEEE-RTS 24-bus system. These results provide new perspectives on leveraging

quantum computing for the distributed optimization of power systems.

Keywords: Quantum computing, Quantum annealing, Benders decomposition, Unit

commitment, Consensus-inspired

1. Introduction

Quantum computing is recognized as a potent tool for solving optimization problems for

addressing classically challenging problems by using quantum superposition and entanglement

[1]. Across various fields seeking quantum acceleration, the primary focus is on addressing

constrained combinatorial optimization problems [2], whose fundamental challenge stems from

the combinatorial growth of discrete variables within the feasible domain space. Traditional

methods swiftly encounter computational bottlenecks when confronting this challenge. The

expansive search space and parallel computing characteristics have propelled the advancement

of quantum computing in addressing constrained combinatorial optimization problems.

Quantum algorithms tailored for specific problems, such as the quantum approximate

optimization algorithm (QAOA) [3] and quantum annealing, can be implemented on real

quantum hardware to address constrained combinational optimization problems based on the

Ising model [4], which can be transformed into a quadratic unconstrained binary optimization

(QUBO) problem [5], specifically expressed as , where , . Despite notable

min X QX

 

X 0,1





* Corresponding author

E-mail address: fgao@gxu.edu.cn (F. Gao), djhuang@st.gxu.edu.cn (D. Huang),

1021313804@qq.com (Z. Zhao), weidai2019@163.com (W. Dai), myyang@st.gxu.edu.cn

(M. Yang), gaoqing@buaa.edu.cn (Q. Gao), ypan@zju.edu.cn (Y. Pan)

progress in quantum hardware and algorithms in recent years, the currently accessible quantum

hardware is still situated in the era of noisy intermediate-scale quantum (NISQ) [6]. The

quantity of available qubits and the error rate of quantum gates are insufficient for effectively

tackling practical problems. Meanwhile, developed in the frame of adiabatic quantum

computing, quantum annealing incorporates quantum fluctuations to expedite convergence

toward the optimal solution and is easier to converge to the global optimal value than classical

annealing [7]. Utilizing quantum annealers like D-WAVE significantly expands the scale of

QUBO problems that can be tackled. At present, the D-WAVE quantum annealing machine has

found practical application in diverse scenarios, including protein structure design [8-10],

manufacturing logistics scheduling, path planning [11], and financial portfolio optimization

[12,13].

In the domain of power systems, numerous discrete variables associated with logical choices

for describing equipment states exist, including decisions like the on/off operations of generator

units and the topology of transmission lines. Consequently, constrained combinatorial

optimization is prevalent in the field of power systems, with typical examples encompassing

the unit commitment (UC) problem. UC is a very significant optimization problem in power

system dispatching, falling under the realm of mixed-integer nonlinear programming (MINLP).

The UC problem is nonconvex and NP-Hard because of the 0-1 variables. With the proliferation

of distributed energy resources (DERs), the computational burden arising from a substantial

quantity of binary variables experiences exponential growth, which poses computational

challenges to traditional classical techniques. A groundbreaking solving strategy is crucial to

effectively solve the UC problem in this context.

Within the framework of the Alternating Direction Method of Multipliers (ADMM), the

Quantum ADMM (QADMM) [14] decomposes the UC problem based on variable types. It

formulates QUBO subproblems, solvable using QAOA on a quantum computer, and

constrained convex subproblems, solvable on a classical computer. Similarly, the Quantum

Surrogate Lagrangian Relaxation (QSLR) method [15] decomposes the UC problem within the

Surrogate Lagrangian Relaxation (SLR) framework. These two hybrid algorithms rely on

quantum circuits and encounter limitations due to the restricted number of available qubits and

the shallow depth of quantum circuits in the NISQ era. Contemporary quantum annealers

demonstrate the capability to handle larger-scale QUBO problems compared to the currently

available quantum circuit-based hardware. Quantum annealing has been employed to solve

simplified formulations of the UC problem [16]. Additionally, annealing-based hybrid Benders

decomposition has been utilized for multi-energy system optimization [17], as well as for

selecting cutting planes of the linearized UC problem [18]. In three other instances [19-21], a

hybrid quantum Benders decomposition approach was used to address the mixed-integer linear

programming problem. However, this conventional approach to reconstructing the QUBO

Hamiltonians of the subproblems in the hybrid algorithms requires the discretization of

continuous variables in the subproblems, introducing a substantial number of auxiliary qubits

and leading to a considerable increase in the dimension of the Hilbert space, thereby affecting

the accuracy of solving QUBO problems and the convergence of the algorithm.

Hen and Sarandy [22] introduced a technique for solving optimization problems by encoding

constraints directly and proposed general criteria for constructing driver Hamiltonians

corresponding to optimization problem constraints. They demonstrated a notable reduction in

the dimensionality of the Hilbert space achieved through constrained quantum annealing and

improved the precision of quantum annealing by enlarging the minimum eigenenergy gap

between the ground state and the first excited state of the Hamiltonian. Nevertheless, the

construction of driver Hamiltonians with multiple commuting constraints heavily depends on

specific problem intuitions, and as of now, there is no universally applicable method for

generating the corresponding driver Hamiltonian based on arbitrary constraints. Recognizing

the essential metric for the adiabatic evolution algorithm is the minimum eigenenergy gap

between the ground state and the first excited state of the system Hamiltonian, this research

employs consensus-inspired objective functions of relaxed subproblems within the

decomposition framework to achieve more concise and rational construction of cutting planes.

These improved objective functions and cutting planes increase the minimum eigenenergy gap

of the system Hamiltonian, thereby enhancing the accuracy of quantum annealing in solving

the QUBO master problem (QUBO-MP). This advancement enables the centralized solution

framework to handle larger-scale UC problems effectively.

With the continuous development of smart grids, centralized algorithms struggle to meet the

partitioned processing requirements. When applied to the UC problem, a centralized framework

consumes substantial computational resources, exhibits low efficiency, and lacks the flexibility

to schedule based on local bus load demands. Prior research [23,24] has explored distributed

strategies to promote energy transactions among microgrids (MGs). In this research, we employ

an average consensus strategy to enable distributed computation by introducing consensus

variables in the subproblems, decoupling power balance constraints at the bus level. This

approach leads to a fully distributed framework that not only reduces the qubit required for

solving the QUBO-MP but also improves computational efficiency.

In summary, this work proposes the quantum generalized Benders decomposition (QGBD)

algorithm to address UC problems with minimum on/off constraints, achieving improved

computational speed compared to the classical generalized Benders decomposition (GBD)

algorithm. To reduce the number of required qubits, a distributed consensus quantum GBD (D-

CQGBD) algorithm is proposed, establishing a fully distributed solution framework. To

enhance the accuracy of quantum annealing in solving the QUBO-MP, the consensus-inspired

quantum GBD (CIQGBD) and its partially distributed variant (D-CIQGBD) are introduced,

enabling more rational construction of cutting planes. The main contributions of this work

include:

1) This research integrates quantum computing into the GBD framework, proposing a series

of hybrid quantum-classical decomposition algorithms. These algorithms transform the NP-

hard MP into a QUBO formulation (i.e., QUBO-MP) suitable for quantum computing, enabling

efficient solutions using QAOA or quantum annealing. By leveraging the speed advantage of

quantum computing in solving QUBO problems, these algorithms accelerate the solution of UC

problems. In large-scale UC problems, the hybrid algorithms demonstrate significant speed

advantages compared to their classical counterparts.

2) Within the distributed framework, this research proposes the classical D-CGBD algorithm

and its hybrid counterpart, D-CQGBD. Both algorithms introduce consensus variables between

neighboring MGs to reformulate subproblems into local subproblems within each MG. Using

dual information from the local subproblems, local cutting planes are constructed, decomposing

the MP into multiple local master problems (LMPs), thus reducing the number of required

qubits. The D-CGBD and D-CQGBD methods not only achieve decoupling and acceleration of

distributed computation but also ensure the privacy of MG information, meeting the

requirements for cross-regional independent decision-making and partitioned management in

power grids.

3) This research improves the relaxation variable allocation strategy based on a consensus-

inspired approach (CIQGBD), enabling more rational construction of cutting planes. This

method enables the MP to be decomposed into multiple LMPs, facilitating distributed parallel

processing (D-CIQGBD). The QUBO-form Hamiltonian of the MP, constructed with more

rational cutting planes, increases the minimum eigenenergy gap between the ground state and

the first excited state of the system Hamiltonian during the annealing process. This

enhancement improves the accuracy of quantum annealing in solving the QUBO-MP. In the

security-constrained UC (SCUC) problem of the IEEE-RTS-24 bus system, D-CIQGBD

demonstrates a speed advantage over the commercial solver Gurobi.

The remaining part of this paper is organized as follows. Section 2 establishes the necessary

theoretical background. Section 3 presents the mathematical model for the UC and SCUC

problems. Section 4 introduces centralized (QGBD), fully distributed (D-CQGBD), and

partially distributed quantum decomposition (D-CIQGBD) algorithms. Section 5 presents the

results and corresponding discussions. Section 6 concludes the work.

2. Preliminaries

This section introduces the QAOA [3] and quantum annealing algorithms [25], both of

which are applicable to combinatorial optimization.

2.1. QAOA

QAOA is a gate-based quantum optimization algorithm, which has a potential advantage in

combinatorial optimization problems. By optimizing the parameters of the quantum gates (i.e.,



R

), QAOA aims to minimize the expectation value of the problem Hamiltonian

：

( ) ( ) ( )

, , ,

       

. (1)

When

( )



is minimized, we perform measurement on

( )

  

to obtain the solution of

the QUBO problem.

As shown in Figure 1, in the QAOA algorithm, the initial state before entering Layer 1 is an

equal probability superposition of all states, which is realized by a series of Hadmard gates. The

initial state can be expressed as:

 

0,1

2nn





=

, (2)

where n is the number of binary variables of the QUBO problem. In each layer, the state is first

rotated along

with the angle



, and then rotated along the transverse Hamiltonian

with

the angle



. Here

is taken to be the Pauli-X operator:

=ˆ0





=



, (3)

which leads to the evolution operator in each layer as follows:

( ) ( )

( )

ˆcos sin

, cos s ˆ

22 sin cos

b i x x i

U H e I i R

 











−



   

−



   



       





= = − = =



   

 

   

   



 −



   

   



.(4)

The evolution operator corresponding to

in each layer is

( )

,pi

U H e



−

After m layers, the quantum state evolves to:

( )

, , ,

b i p i

U H U H

     

=  



. (5)

Theoretically, the minimum of

can be approached when the number of layers is infinitely

large:

( ) ( ) ( )

* * * * * * min

lim , , ,

mE H E

       

→ ==

. (6)

Given a finite number of layers in practice,

is minimized by iteratively optimizing the values

of the parameters



and



with one classical optimizer. Labelling

as the minimum of

for k iterations, the optimization converges at the k-th iteration when the following condition is

satisfied:

1kk



−

−

. (7)

Here



is the tolerance error.

Figure 1. The framework of QAOA algorithm.

2.2. Quantum Annealing

Quantum annealing belongs to quantum adiabatic evolution. During this evolution, the

system stays at its lowest energy state. At the end of quantum annealing, the quantum state is

just the ground state of the problem Hamiltonian.

The quantum annealing algorithm can be implemented with D-WAVE. The Hamiltonian of

the D-WAVE quantum annealing machine can be expressed with the Ising model:

( ) ( ) ( ) ( )

( , )

( ) ( ) ( ) ( )

ˆ ˆ ˆ ˆ

2 2 2 2

i i i j

Ising b p x i z i j z z

i i i j

HBA s B s A s s

H H h k

   



= − + = − + +







  

, (8)

where

 

0,1s

is the normalized anneal fraction.

is the driver Hamiltonian, while

is the

problem Hamiltonian, whose ground state is just the solution of the QUBO model.

With almost no interaction with the external environment, the quantum system can evolve

slowly enough from the initial Hamiltonian

to the problem Hamiltonian

( )

1 , [0,1]

H H H

  





= − + 





, (9)

where



is the timing point, and is the whole annealing time.

The principle of the quantum annealing algorithm can be described as follows: (1) At



the quantum system is in the ground state of the initial Hamiltonian

, that is, all qubits are in

the superposition of

and

(i.e.,

( )

10 + 1

); (2) When the quantum annealing algorithm

starts (





), the quantum system is slowly perturbed, and couplings

,ij

and biases

the problem Hamiltonian

are introduced, making the qubits become entangled. Assuming

the perturbation is long enough and changes slowly enough (i.e., the ideal quantum annealing

process), the quantum system will remain in the ground state without transitioning to the excited

states; (3) When



, the quantum annealing process ends. Because the quantum system does

not have an energy level crossover during the whole quantum annealing process, the system is

now in the ground state of the problem Hamiltonian, which can be measured to give the solution

of the QUBO model.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

1FullyandpartiallydistributedQuantumGeneralizedBendersDecompositionforUnitCommitmentProblemsFangGao1,DejianHuang1,ZiweiZhao1,WeiDai1,*,MingyuYang1,QingGao2andYuPan31SchoolofElectricalEngineering,GuangxiUniversity,Nanning,530004,China2HangzhouInnovationInstituteofBeihangUniversity,Hangzhou,310051,Chi...

展开>> 收起<<

1 Fully and partially distributed Quantum Generalized Benders Decomposition for Unit Commitment Problems.pdf

共30页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

1 Fully and partially distributed Quantum Generalized Benders Decomposition for Unit Commitment Problems

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: