A Novel Quantum-Inspired Approximate Dynamic Programming Algorithm for Unit Commitment Problems

A novel quantum-inspired approximate dynamic programming algorithm (ADP) is proposed for solving unit commitment (UC) problems. The quantum computing theory is applied to tackle some new issues rising from ADP. In details, the unit states in UC problems are expressed by the quantum superposition. Then, the collapsing principle of quantum measurement is applied to solve the Bellman equation of ADP speedily. Based on the quantum rotation gate, the pre-decision states of the ADP are generated by quantum amplitude amplification technology. In the proposal algorithm, the quantum computation balances between state space exploration and exploitation automatically. Test cases of UC are performed to verify the feasibility of the proposal approximate algorithm for the range of 10 to 100 units with 24-hour with ramp rate constraints. The experimental results show that the quantum-inspired ADP algorithm can find the better sub-optimal solutions of large scale UC problems within a reasonable time.

section_content: Unit commitment (UC) is an important task in the power system operation. A good schedule of generating units may save the electric utilities many production costs. The UC problem can be formulated as a large-scale, nonlinear, mixed-integer combinatorial optimization problem, but it is difficult to obtain the global optimal solution. Though a lot of methods have been used to solve the UC problem, such as the priority list (PL) [1], dynamic programming (DP) [2] [3], mixed-integer programming (MIP) methods [4] [5], meta-heuristics [6] - [8], quantum-inspired meta-heuristic methods [8] - [10], etc., they still have some flaws. For example, DP method for solving UC is easy to encounter the curse of dimensionality problem [2] [3]. Fortunately, this problem can be solved by the approximate dynamic programming (ADP) method efficiently. Moreover, ADP can gain the optimal or better sub-optimal solutions of many engineering problems. To implement ADP, generally, the DP algorithm is constructed over a limited set of states. For instance, the priority list is used to generate the limited set of unit commitment problem's states [2], then the ADP is implemented on the limited set to solve the UC problem. ADP is implemented using quantum amplitude amplification in [11]. Recently, the method of quantum amplitude amplification based on Grover iteration was applied to the action selection of the Bellman equation in dynamic programming and solve the curse of dimensionality [12]. In [13], this method is also used to solve the Bellman equation of reinforcement learning and makes a good tradeoff between exploration and exploitation. However, the quantum amplitude amplification based on the quantum rotation gate is much easier to implement and combine with combinatorial optimization problems compared with the one based on Grover iteration [14]. 

The most important work of ADP in recent years is the forward iteration ADP algorithm theory proposed by Prof. Powell of Princeton University in the year 2013 [15]. The forward ADP algorithm can overcome the curse of dimensionality. However, there are still some open issues. The main one is how to make a balance between exploration and exploitation, which affects the quality of solution of ADP significantly. In the case for solving UC problem, the general exploration strategies, such as Boltzmann machine [15], epsilon-greedy [15], knowledge gradient and Bayesian method [15], R-max [15], etc., could not explore the state space of UC problem effectively [3] [15]. Therefore, it is necessary to seek some new exploring strategies for the UC problems specially. 

In this paper, a novel quantum inspired ADP algorithm (QI-ADP) for solving large scale UC problems is proposed by using the quantum computing theory to tack some issues in ADP. The unit states in UC problems are expressed by the quantum superposition. Then, the collapsing principle of quantum measurement is applied to solve the Bellman equation of ADP speedily. The pre-decision states of the ADP are generated by quantum amplitude amplification technology. Test cases of UC problems which range from 10 to 100 units with 24-hour are performed to verify the feasibility of the proposed algorithm. The experimental results show that the quantum-inspired ADP algorithm can find the better sub-optimal solutions of large scale UC problems within a reasonable time. It's feasible that using quantum computing theory tackle some new issues rising from ADP.
section_name: Introduction

section_content: The UC problem is to determents a unit commitment schedule to minimize the total operating cost of all generating units, subject to a number of system and unit constraints. 

The objective function of UC problem is given as the following

where u i,t presents the state of unit i at hour t (0 when the unit is off, and 1 otherwise). The fuel cost function of unit i at hour t is expressed as

where P i,t is the power generation of unit i at hour t. The a i, b i and c i are the cost coefficients of unit i. C i,t is the startup cost and can be described as,,

where C i,hot is the hot startup cost of unit i, and C i,cold is the cold startup cost of unit i. T i,t is the continuous online time (+) or offline time (-) of unit i. T i,off is the minimum down time of unit i. T i,cold is the cold start time of unit i. 

The power balance constraint is given by,,, 1 0

where P D,t is the system demand at hour t. 

The system spinning reserve is expressed by

where P i,max is the maximum power output of unit i. S R,t is the required spinning reserve at hour t. The active power from unit i is limited as

where P i,min and Pi,max are the minimum and maximum power output of unit i. The minimum up/down time constrains are given by, 1,,

where T i,on is the minimum up time of unit i. T i,off is the minimum off time of unit i. The ramp rate constraints are indicated as below,

where P i,up, P i,start, P i,down and P i,shut are the limit of unit i for ramp up, ramp down, startup ramp and shutdown. The UC model in this paper is constituted by the above equations ranged from (1) to (9).
section_name: The Model of UC Problem

section_name: The QI-ADP Algorithm for UC Problem

section_content: The state of UC problem is given by (10). The value of u i,t is 0 or 1. Therefore, (10) has 2 T×N different combination states, which are from 00 0

. In this paper, the quantum state is employed for (10) to express the states of UC problem for the sake of using quantum theory since u i,t can be considered as a bit in the traditional information science. 

1,1

In the quantum information science, an information unit (a quantum bit, qubit) is represented by a superposition state as

) where |0> and |1> correspond to traditional login states 0 and 1. α and β are complex coefficients and satisfy 11 ) is hard to be expressed and stored in a traditional computer. Based on the characteristics of α and β in (11), a vector as ( 12 ) can be expressed and stored as followed:

Then, (10) is expressed by the quantum state as

where Q t,N expresses all the unit commitment states of N units at hour t. ( 13 ) has 2 T×N different base states, which are from | 00 0

. Thus, the states of ( 10 ) can be quantized by (13).
section_name: State of UC problem and quantum state

section_content: According to the ADP algorithm framework in [15], the quantum-inspired ADP algorithm for UC problem is described as follows. Step1: Get the pre-decision state matrix P by quantum observing (13). 

Step2: do for t=0,1,2,….,T (a) Solve the Bellman equation in (14) Step4: Return the best solution B of UC problem. The following will discuss some main issues in the above QI-ADP algorithm. In step1, the form of the pre-decision state matrix P is the same as (10). The quantum observing method to construct P is that for a pair of (α i,t,β i,t ) in ( 13 ), u i,t is 1 if |α i,t | 2 <|β i,t | 2, otherwise u i,t is 0. After observing each pair (α i,t,β i,t ) in ( 13 ), the matrix P is constructed. As P represents a schedule of UC problem, it must satisfy UC constraints. If P violates the UC constraints, a heuristic method [8] - [10] is used to adjust them. 

In step3, the solution of nth iteration is given by 0,

M is a schedule of UC problem. If M violates the UC constraints, the heuristic method [8] - [10] is used to adjust them. Let B is the best solution of n-1 iteration with the same formulation as (10). In matrix B, the meaning of b i,t is same as u i,t in (16). If f(M)< f(B), the current best solution is updated with B=M. 

In step3, the ( 13 ) is updated by the quantum rotation gate. For a pair of (α i,t,β i,t ) in (13), the updating method is shown as

) cos( )

where, i t   is the quantum rotation angle corresponding to (α i,t,β i,t ). 

where 0

 is the given initial rotation angle. τis the constant coefficient.
section_name: The QI-ADP Algorithm for UC Problem

section_content: The proposed algorithm is simulated on a PC with Intel Core2 Quad CPU (2. 5GHz), 2GB RAM. The algorithm is implemented with Matlab on Windows platform. The data of test cases for UC problems are taken from [5]. Six test cases are from 10 up to 100 units with 24 hours with ramp rate constraints. Let P i,up =P i,down =0. 2P i,max, which means the ramp up and ramp down rate of each unit are taken to be 20% of its maximum power output. Let P i,start =P i,shut =2P i,min, which means that the startup and shutdown ramp rate of each unit are its double minimum power output. The Outer-Inner Approximation approach (OIA), outer approximate (OA) and tighter several-step outer approximation (TOA) are very successful deterministic mix-integer mathematical programming methods, and they can obtain high quality solutions for UC problems [5]. The results show in Tab. 1. From Tab. 1, Comparing results of QI-ADP to the ones of OA, TOA and OIA, the average differences are 0. 87%, which are very small. The results indicate that QI-ADP can obtain the high-quality sub-optimal solutions of test cases with ramp rate constraints. [10], which identify that the characteristics of running time of QI-ADP and OIA are nearly linear, while the characteristic of QBPSO is nonlinear. That's to say, QI-ADP can solve the UC problems efficiently and obtain the high-quality solutions. As a result, it's feasible using quantum computing theory to tackle some new issues rising from ADP itself.
section_name: Test results

section_content: A novel quantum-inspired ADP algorithm is proposed in this paper. The quantum computation theory is used to handle the issues of ADP. The quantum amplitude amplification technology is applied to explore the state space of UC problem and automatically makes the balance between exploration and exploitation. The Bellman equation is solved efficiently by the quantum observing method. The pre-decision states of ADP are generated by the quantum computation theory. The results of simulated experiments show that QI-ADP can solve large scale cases of UC problems, and can obtain a better sub-optimal solution within a reasonable time.
section_name: Conclusion

section_name: Acknowledgement

section_content: This work is sponsored by the National Basic Research Program of China ( 973 Program ) (Project No. 2013CB228205 ), the National Science Foundation of China (Project No. 51167001 ), and the Humanities & Social Science Research Project of the Ministry of Education of China (Project No. 11YJAZH080 ).
section_name: Acknowledgement