Abstract
Aiming at multi-agent coordinated scheduling problems in power systems under uncertainty, a generic projection and decomposition (P&D) approach is proposed in this letter. The canonical min-max-min two-stage robust optimization (TSRO) model with coupling constraints is equivalent to a concise robust optimization (RO) model in the version of mixed-integer linear programming (MILP) via feasible region projection. The decentralized decoupling of the non-convex MILP problem is realized through a dual decomposition algorithm, which ensures the fast convergence to a high-quality solution in the distributed optimization. Numerical tests verify the superior performance of the proposed P&D approach over the existing distributed TSRO method.
WITH the growing penetration of renewables, its strong uncertainty brings considerable challenges to power system scheduling. In addition, due to the coexistence of multiple agents in power systems, the efficient coordination of independent stakeholders considering privacy-preserving has become the focus of the current research [
At present, the traditional distributed TSRO method deals with uncertainty by constructing a centralized min-max-min RO model. The augmented Lagrangian method, e.g., the alternating direction method of multipliers (ADMM) [
1) TSRO is generally solved by an iterative algorithm, such as the column and constraint generation (C&CG) algorithm or the Benders decomposition. The iterative calculations could hardly satisfy the computational requirements in practical cases due to their large calculation expense. Such a burden grows particularly heavy if the conventional iterative solution algorithm is embedded in distributed decomposition [
2) The representative augmented Lagrangian-based distributed methods can equivalently decouple convex centralized models, and such methods could derive the identical results as the centralized optimization [
In view of the above research gaps, this letter proposes a novel projection and decomposition (P&D) approach for multi-agent coordinated scheduling problems under uncertainty. Compared to the traditional distributed TSRO method, the proposed P&D approach identifies a high-quality solution with low computational cost and strong scalability.
The centralized TSRO model for multi-agent scheduling with uncertainty in power systems is written in matrices as (1). The compact model M1 minimizes the total operation objective for system scheduling in the predicted nominal scenario, and enforces the power balance under uncertainty. The feasibility of these basic scheduling plans in the nominal scenario is ensured for all uncertainty scenarios, thus keeping the safe operation of the system [
(1) |
where xi denotes the first-stage variables of agent i before uncertainty, that is, the basic scheduling plans, including the binary commitments and the continuous unit outputs; denotes the local operation objective of agent i in the nominal scenario, and the total operation objective of all agents is minimized in the first-stage optimization. The second line of M1 represents the local constraints of agent i in the nominal scenario, mainly containing the unit operation and network security within its jurisdiction, and the third line denotes the coupling constraints among agents, such as the consistency for shared line power. In the fourth line, denotes the second-stage optimization model; and yi denotes the continuous recourse variables of agent i after uncertainty. The second-stage recourse plans modify xi to hedge the uncertainty. denotes the non-negative slack variables introduced to characterize power imbalance with two parts . Note that when there is an inflow power imbalance, and ; otherwise, when an outflow power imbalance emerges, and . denotes the uncertainty decision variables of agent i, e.g., the uncertainty in source-load power; and denotes the uncertainty set, such as the boxed or polyhedral set. The fifth and sixth lines represents the local constraints of agent i and the coupling constraints between multiple agents under uncertainty, respectively. Bi, ei, Ci, f, Gi, hi, Li, Mi, Ki, and g are the constant matrices for the first- and second-stage constraints.
Considering that a centralized TSRO model with coupling constraints in both stages cannot be decoupled with guaranteed optimality in distributed optimization, this section proposes a P&D approach to tackle this problem.
For M1, the decision-making of the second stage intrinsically checks the scheduling feasibility under uncertainty, indicating that with the first-stage solution , there exists for any uncertainty scenario that ensures . Hence, M1 is recast as:
(2) |
Compared to M1, the slack variables are omitted in M2. The max-min bi-level model in the second stage is described as a multi-dimensional feasible region of the recourses, which is defined by the inner-layer linear programming constraints with respect to uncertainty. According to the Fourier-Motzkin elimination [
(3) |
where , , and are the parameter matrices produced in the elimination; and i identifies the constraint set generated by the corresponding agent. The general procedures are given in [
It is worth mentioning that the last term in (2) essentially represents the coupling constraints among agents only on their coupling variables in yi under uncertainty, and it does not involve any internal variables of other agents. Such types of constraints are shared among the neighboring agents, e.g., the consistency constraints on tie-line variables between different areas in power systems. Therefore, as agent i knows these coupling variables and constraints with its neighbors, the projection for the second-stage optimization could be conducted independently by agent i without the privacy of its neighboring agents, and each agent can obtain the linear constraints in (3). A simple multi-agent optimization model with coupling constraints is provided in [
According to the property of the Fourier-Motzkin elimination, we can get all feasible solutions of a linear programming model from the solution results fitting these linear constraints generated by the Fourier-Motzkin elimination with two presuppositions [
(4) |
M3 is still intractable because contains infinite uncertainty scenarios. As ui is exogenous, to ensure (3) valid for , the only need is to meet:
(5) |
In the above formulation, the
(6) |
where and denote the coefficient matrices related to of agent i; and denotes dual variables for the
After substituting the dual formulation of the max optimization for each dimension in (6), M3 is transformed as:
(7) |
where collects by columns for all dimensions. As the Fourier-Motzkin elimination is an exact equivalent procedure, the original min-max-min TSRO model, i.e., M1, is equivalent to a mixed-integer linear programming (MILP) problem M4 after feasible region projection. The solution of M4 does not need any iteration compared with M1, which is convenient for the engineering implementation.
The MILP problem M4 after projection is refined into a compact formulation P1.
(8) |
where in M4 is integrated as the decision variables of agent i to form the new variable vector xi for each agent in P1; Ai, b, Di, and di are the constant matrices or vectors for the coupling and local constraints in the refined formulation; Xi is the compact set of all local constraints for agent i in M4, i.e., the first, third, and fourth constraints in (7). The second line of (8) represents the corresponding coupling constraints, that is, the second constraint in (7), where the dimension of b is q.
The traditional ADMM and ATC method are less effective for an MILP because such a non-convex problem no longer meets the optimality and convergence conditions of the traditional decomposition approaches [
(9) |
Its Lagrangian dual expression is formulated as:
(10) |
where denotes the q-dimensional dual variables; and the definition of is as follows: finding the maximal difference in the contributions of feasible solution to the coupling constraints.
(11) |
where j is the index of the matrix line in the coupling constraints.
For traditional distributed scheduling, a coordination center is set up to collect the optimal results of all shared variables among agents. Their contributions to the coupling constraints help update and , which are broadcast to all agents for the next iteration. In fact, it is a burden to set a coordination center for the whole network in the real-world cases. A max consensus algorithm is further devised to assign and to avert a coordination center. The detailed steps of the decentralized algorithm are listed as below.
Algorithm: decentralized dual decomposition algorithm for P1 | |
---|---|
Step 1: | Initialize , set , , , , for all |
Step 2: | Repeat |
Step 3: | For do |
Step 4: | |
Step 5: | |
Step 6: | |
Step 7: | |
Step 8: | |
Step 9: | |
Step 10: | |
Step 11: | |
Step 12: | Until satisfy the coupling constraints |
In Step 4, agent i gathers of its connected agent j, and the average for is constructed by using the weighted factor ; and denotes the group of the neighboring agents for agent i. The dual variables of agent i are fixed as , and the min optimization is performed in Step 5 to reap a tentative primary solution . In Steps 6-9, each agent refines the coefficient via the max and min optimizations and of components , respectively. Specifically, Steps 7 and 8 obtain the worst contributions of to the coupling constraints by the tentative solution , and a tightening coefficient is derived as the maximum one of and in Steps 6 and 9. In Step 10, the dual variables are updated along the gradients via ; denotes the step size whose selection rules can be found in [
Note that the decentralized solution converges to the dual optimal solution in finite iterations with the dual subgradient algorithm. Going into detail, the dual variable sequence created by Step 10 guarantees the convergence to the dual optimal solution. Such a dual finite-time convergence proposition for MILP models is presented in [
In this study, we consider the source-load power uncertainty shown in (1) for multi-agent coordinated scheduling of power systems. Note that there would be uncertainty in the availability of power generation or consumption resources in practice, while the proposed P&D approach is not limited considering certain kinds of uncertainty. In other words, the scheduling model in (1) is general for multiple uncertainty. For instance, when we further consider the output uncertainty of power units [
It is noteworthy that this paper focuses on how to achieve an effective decentralized solution to a centralized RO problem and ensure that the derived decentralized results are as close as possible to the optimal results of the centralized method. From the perspective of game theory, the relationship of the multi-agent objectives in this paper belongs to the cooperative game. There also exists the condition of multiple agents with conflicting objectives in scheduling. Currently, some effective models or methods have been investigated to address this problem, such as the Stackelberg game model [
Three cases of multi-area scheduling are evaluated to verify the superiority and scalability of the proposed P&D approach. Case 1 is a small-scale 2-area 12-bus system with one wind farm integrated into each area and an interconnected tie-line. Case 2 and Case 3 both adopt a 1441-bus system with practical size, which are divided into 4 areas and 8 areas, respectively. The real 1441-bus system contains 130 wind farms, 320 conventional generators, 2057 internal lines, and 23 tie-lines connecting multiple areas with a voltage level of 500 kV. Detailed data of the two test systems are available in [
Case | Method | Cost ($) | Iteration | Time (s) | Number of scenarios | Problem scale | |
---|---|---|---|---|---|---|---|
Number of constraints | Number of variables | ||||||
Case 1 (2-area 12-bus system) | A1 | 150243 | N/A | 4.9 | 1000 | 22646 | 10638 |
A0 | 150280 | 23 | 37.6 | 1000 | 28126 | 7352† | |
A2 | 152326 | 78 | 1146.5 | 1000 | 22694 | 10710‡ | |
Case 2 (4-area 1441-bus system) | A1 | 29376412 | N/A | 100.4 | 20000 | 1248106 | 465184 |
A0 | 29382876 | 27 | 95.2 | 20000 | 1512704 | 303374† | |
A2 | 29768991 | 132 | 3880.6 | 20000 | 1248298 | 465568‡ | |
Case 3 (8-area 1441-bus system) | A1 | 29376412 | N/A | 100.4 | 20000 | 1248106 | 465184 |
A0 | 29381995 | 30 | 63.3 | 20000 | 1512822 | 303402† | |
A2 | 29617300 | 146 | 3433.7 | 20000 | 1248490 | 465952‡ |
Note: † represents the total constraints and variables of the models after elimination for all agents; and ‡ represents the total constraints and variables of the decoupled models after ADMM for all agents.
In Case 1, it is noteworthy that the total operation cost of A0 is approximately equal to the referring centralized solution in A1, and the relative optimality gap is 0.025%, whereas the gap for A2 is 1.39%. The dual decomposition algorithm realizes the effective decoupling of the non-convex MILP problem, and the constraint tightening contracts the duality gap that ensures the solution quality. The number of distributed iterations and the total solution time of A2 are 3.4 and 30.5 times of those in A0, respectively. The reason is that the dual decomposition algorithm updates the dual variables in the direction of gradients, which accelerates the convergence of the problem solution. The update of the multipliers and the penalty factors in ADMM depends on the empirical values, resulting in a low convergence speed. In addition, each agent directly solves the MILP-type robust scheduling model after projection, which greatly reduces the computational time for each distributed iteration.
For larger-scale testing systems in Case 2 and Case 3, the optimality gap between A0 and A1 is further reduced. In particular, the optimality gaps for Case 2 and Case 3 are 0.022% and 0.019%, respectively, indicating that the optimal cost is closer to the centralized objective with more agents. Besides, the iteration of A0 increases slowly, hence its computational performance is relatively stable. The solution within minutes in A0 fully meets the scheduling requirements, while the iteration number of A2 is 4.8 times of that by A0, and the total run time even reaches 40-54 times. It can also be observed that the increase of the modeling scale leads to a significant rise in the iterations and the run time of A2, and the hour-level computational time hinders its practical application. Although the total number of constraints after elimination in A0 increases compared with A1 and A2, the dual decomposition further divides the entire problem into smaller local scheduling problems for each agent, hence it will not further pose huge computational challenges to the decentralized implementation by agents. Therefore, A0 enjoys stable computational performance and high scalability in terms of agent number and system size, and these strengths are more prominent compared with A2. Besides, for all cases, the three methods (A0, A1, and A2) derive the optimal power plans that guarantee 100% feasibility to all stochastic scenarios, indicating the robustness of their solution results.
This letter proposes a novel P&D approach for the robust coordinated scheduling of multiple agents under uncertainty. Numerical tests denote that the proposed P&D approach overcomes the defects of low computational efficiency, slow convergence, and suboptimality in the traditional distributed TSRO method. The merits of the proposed P&D approach in optimality and computational performance are more notable with the enlargement of the system scale and agent quantity. Note that the proposed P&D approach is a universal distributed TSRO method that can be easily extended to numerous coordinated scheduling problems such as multi-area unit commitment, transmission-distribution coordination, energy management of networked microgrids, peer-to-peer trading in prosumers, and integrated energy system dispatch. Future research will consider extending the P&D approach for distributed TSRO methods with binary recourses and endogenous uncertainty. Besides, further research is needed on distributed scheduling of multiple agents with conflicting objectives under uncertainty.
References
J. Wei, Y. Zhang, J. Wang et al., “Decentralized demand management based on alternating direction method of multipliers algorithm for industrial park with CHP units and thermal storage,” Journal of Modern Power Systems and Clean Energy, vol. 10, no. 1, pp. 120-130, Jan. 2022. [Baidu Scholar]
Z. Li, W. Wu, M. Shahidehpour et al., “Adaptive robust tie-line scheduling considering wind power uncertainty for interconnected power systems,” IEEE Transactions on Power Systems, vol. 31, no. 4, pp. 2701-2713, Jul. 2016. [Baidu Scholar]
H. Gao, J. Liu, L. Wang et al., “Decentralized energy management for networked microgrids in future distribution systems,” IEEE Transactions on Power Systems, vol. 33, no. 4, pp. 3599-3610, Jul. 2018. [Baidu Scholar]
H. Qiu and F. You, “Decentralized-distributed robust electric power scheduling for multi-microgrid systems,” Applied Energy, vol. 269, p. 115146, Jul. 2020. [Baidu Scholar]
Z. Chen, Z. Li, C. Guo et al., “Fully distributed robust reserve scheduling for coupled transmission and distribution systems,” IEEE Transactions on Power Systems, vol. 36, no. 1, pp. 169-182, Jan. 2021. [Baidu Scholar]
Y. Ji, Q. Xu, and Y. Xia, “Distributed robust energy and reserve dispatch for coordinated transmission and active distribution systems,” Journal of Modern Power Systems and Clean Energy, vol. 11, no. 5, pp. 1494-1506, Sept. 2023. [Baidu Scholar]
X. Liang, Z. Li, W. Huang et al., “Relaxed alternating direction method of multipliers for hedging communication packet loss in integrated electrical and heating system,” Journal of Modern Power Systems and Clean Energy, vol. 8, no. 5, pp. 874-883, Sept. 2020. [Baidu Scholar]
N. Michelena, H. Park, and P. Papalambros, “Convergence properties of analytical target cascading,” AIAA Journal, vol. 41, no. 5, pp. 897-905, May 2003. [Baidu Scholar]
Z. Li, M. Shahidehpour, W. Wu et al., “Decentralized multiarea robust generation unit and tie-line scheduling under wind power uncertainty,” IEEE Transactions on Sustainable Energy, vol. 6, no. 4, pp. 1377-1388, Oct. 2015. [Baidu Scholar]
N. G. Cobos, J. M. Arroyo, N. Alguacil et al., “Robust energy and reserve scheduling considering bulk energy storage units and wind uncertainty,” IEEE Transactions on Power Systems, vol. 33, no. 5, pp. 5206-5216, Sept. 2018. [Baidu Scholar]
J. Imbert, “Fourier’s elimination: which to choose?” in Proceedings of Principles and Practice of Constraint Programming, Newport, USA, Jun. 1993, pp. 117-129. [Baidu Scholar]
J. Zhen, D. Hertog, and M. Sim, “Adjustable robust optimization via Fourier-Motzkin elimination,” Operations Research, vol. 66, no. 4, pp. 1086-1100, Jul. 2018. [Baidu Scholar]
H. Qiu. (2023, Oct.). Supplementary. [Online]. Available: https://entuedu-my.sharepoint.com/:b:/g/personal/haifeng_qiu_staff_main_ntu_edu_sg/ETahe6g9sy9Eoy005oaY7CEBZyF4B65aDjrfRYD_jGIv4w?e=tdkKI8 [Baidu Scholar]
Y. Liu, L. Wu, and J. Li, “A fast LP-based approach for robust dynamic economic dispatch problem: a feasible region projection method,” IEEE Transactions on Power Systems, vol. 35, no. 5, pp. 4116-4119, Sept. 2020. [Baidu Scholar]
G. B. Dantzig and B. C. Eaves, “Fourier-Motzkin elimination and its dual,” Journal of Combinatorial Theory (A), vol. 14, no. 3, pp. 288-297, May 1973. [Baidu Scholar]
H. Qiu, A. Vinod, S. Lu et al., “Decentralized mixed-integer optimization for robust integrated electricity and heat scheduling,” Applied Energy, vol. 350, p. 121693, Nov. 2023. [Baidu Scholar]
A. Falsone and M. Prandini, “A distributed dual proximal minimization algorithm for constraint-coupled optimization problems,” IEEE Control Systems Letters, vol. 5, no. 1, pp. 259-264, Jan. 2021. [Baidu Scholar]
A. Falsone, K. Margellos, and M. Prandini, “A distributed iterative algorithm for multi-agent MILPs: finite-time feasibility and performance characterization,” IEEE Control Systems Letters, vol. 2, no. 4, pp. 563-568, Oct. 2018. [Baidu Scholar]
H. Qiu, W. Gu, W. Sheng et al., “Resilience-oriented multistage scheduling for power grids considering nonanticipativity under tropical cyclones,” IEEE Transactions on Power Systems, vol. 38, no. 4, pp. 3254-3267, Jul. 2023. [Baidu Scholar]
H. Gao, H. Pan, R. An et al., “Bi-level multi-leader multi-follower stackelberg game model for multi-energy retail package optimization,” Journal of Modern Power Systems and Clean Energy, vol. 12, no. 1, pp. 225-237, Jan. 2024. [Baidu Scholar]