Source-linked AI summary
Aggregated Feasible Region of Heterogeneous Demand-Side Flexible Resources -- Part I: Theoretical Derivation of the Exact Model
Yilin Wen, Zechun Hu, Shi You, Xiaoyu Duan
TL;DR
Demand-side aggregators need an exact feasible region for heterogeneous resources because existing AFR models can be inaccurate and cause infeasible allocation. The paper formulates AFR calculation as a projection problem and uses FME with redundancy analysis to derive its exact expression and computation method. The resulting model substantially reduces FME complexity, although its constraint count remains exponential in the number of time intervals.
Problem
Existing AFR models for multiple heterogeneous demand-side resources are limited or inaccurate, creating a risk of infeasible lower-level power allocation.
Method
The paper models individual resources with power-and-energy constraints, formulates AFR as a polytope projection, and derives the exact region using FME and redundancy analysis.
Results
The derived exact AFR reduces computational complexity from O((2NT)2NT ) for unsimplified FME to O(N2T ), with 2(2T −1) constraints independent of N.
Takeaways & Limitations
The exact AFR can be extended by adding resource terms to the aggregate sum or by directly combining AFR expressions for separate resource sets.
Takeaways & Limitations
The exact AFR still has an exponential number of constraints with respect to the number of time intervals, limiting computation when T is large.
Abstract
from arXiv · showhide
In the first part of the two-part series, the model to describe the exact aggregated feasible region (AFR) of multiple types of demand-side resources is derived. Based on a discrete-time unified individual model of heterogeneous resources, the calculation of AFR is, in fact, a feasible region projection problem. Therefore, the Fourier-Motzkin Elimination (FME) method is used for derivation. By analyzing the redundancy of all possible constraints in the FME process, the mathematical expression and calculation method for the exact AFR is proposed. The number of constraints is linear with the number of resources and is exponential with the number of time intervals, respectively. The computational complexity has been dramatically simplified compared with the original FME. However, the number of constraints in the model is still exponential and cannot be simplified anymore. Hence, In Part II of this paper, several approximation methods are proposed and analyzed in detail.
I. INTRODUCTION
Heterogeneous demand-side resources must be aggregated to provide grid services, but existing aggregation models often misrepresent their feasible power region. The paper therefore derives an exact AFR using FME while reducing redundant constraints.
- I. INTRODUCTION: Aggregating small demand-side resources helps meet ancillary-service scale requirements, including PJM’s 0.1 MW adjustable-power threshold.Directly dispatched ancillary services and incentive-based demand response can perform better than indirect price-based control.
- I. INTRODUCTION: Centralized scheduling has scalability and privacy problems, whereas distributed optimization requires unit-level computation and communication and is often too slow for real-time use.
- I. INTRODUCTION: Hierarchical dispatch requires an accurate aggregated feasible region so lower-level allocation remains feasible, but practical models often use only aggregate power bounds or experience-based rules.
- I. INTRODUCTION: Existing AFR studies either bound TCL regions with generalized storage models, use inaccurate summed power-and-energy boundaries, or retain all EV energy states instead of an aggregate state.
- I. INTRODUCTION: The paper derives and computes the exact AFR for heterogeneous resources with FME, whose projection formulation starts from individual power-and-energy constraints.
- I. INTRODUCTION: FME can generate N·P new constraints when eliminating one variable and may have double-exponential complexity across multiple eliminations, motivating analysis of redundant constraints.
D. Using Fourier-Motzkin Elimination to Calculate the AFR
The AFR is obtained by projecting the joint polytope of individual resource constraints onto aggregate energy variables. FME eliminates resource-energy variables interval by interval, with several combination methods and redundancy rules determining the retained constraints.
- D. Using Fourier-Motzkin Elimination to Calculate the AFR: The individual feasible regions form an NT-dimensional polytope, and the AFR is its projection onto aggregate energy E(t), avoiding direct high-dimensional Minkowski-sum calculation.The unsimplified projection would eliminate NT variables from 4NT constraints with complexity O((2NT)2NT).
- D. Using Fourier-Motzkin Elimination to Calculate the AFR: FME starts at interval T and eliminates eN(T), eN(T−1), …, eN(1); eliminating every resource energy at one interval constitutes one FME step.
- D. Using Fourier-Motzkin Elimination to Calculate the AFR: At each interval, ei(t) can be eliminated by combining CN(t), CN(t) with Fv,k,X(t), or only Fv,k,X(t).These are the three elimination methods analyzed in the subsequent sections.
- D. Using Fourier-Motzkin Elimination to Calculate the AFR: Constraints produced by combining only CN(t) can be redundant under Hypo 2, because they are implied by Ce_i(t−1) and are omitted from later steps.
- D. Using Fourier-Motzkin Elimination to Calculate the AFR: The second method groups resources by whether they use Cp(t) or Ce(t), so the resulting inequality depends on the selected DSFR set X rather than individual resource identities.
- D. Using Fourier-Motzkin Elimination to Calculate the AFR: When X=∅, the resulting expression gives the aggregated power and energy constraints formed by summing the individual bounds.
IV. THE SECOND METHOD OF ELIMINATION
The second elimination method analyzes how supplement and remove operations generate constraints and proves that many operation sequences are redundant. The resulting reductions identify the nonredundant inequalities needed for subsequent elimination or the final AFR.
- Operation redundancy: Single SA or RA implies every longer elimination chain that alternates SP and RP before ending with SA or RA.Thus, chains such as SP-RA, RP-SA, and loop-SR need not be computed separately.
- Operation properties: SA preserves the sign of the energy term while reversing the sign of selected prior-time terms, whereas RA produces only same-sign prior-time terms.This sign regularity is used later to characterize the coefficient of E(t).
- Operation redundancy: SA and RA generate many constraints because subsets are selected broadly, but redundant constraints can be identified from implication relationships without computation.The operation definitions distinguish SAX,Y from RAX,Y according to how Cp(t) and Ce(t) are assigned across subsets.
- Theorem 2: Theorem 2 shows that only inequalities associated with specific preceding SA or RA operations remain nonredundant among the generated inequalities.For nonempty Z, the relevant preceding operations are SAN−Z,Z(t−1) and RAZ,Z(t−1).
- Corollary 1: Corollary 1 retains SAX,N−X(t), RAX,X(t), and SAX,∅(t) as the only nonredundant operations for the considered inequalities.The first two continue into the next elimination step, while SAX,∅(t) contributes directly to the final AFR constraint set.
C. General Formula
The general formula organizes the surviving constraints through paths and coefficient vectors generated across elimination steps. A binary-tree representation captures how the retained SA and RA operations develop these coefficients and physical power combinations.
- General formula: The general constraint formula is derived from Corollary 1 after retaining only the nonredundant operations in each elimination step.The formula contains a continuing part for constraints participating in later elimination and a direct part corresponding to SAX,∅.
- Coefficient-vector development: The coefficient vector v develops as a complete binary tree whose branches represent retained SA, RA, or boundary-combination operations.Right branches represent SAX,N−X or SAX,∅, while left branches generally represent RAX,X; the leftmost path instead reflects redundant-case combinations.
- Path representation: Each generated path l has an associated coefficient vector v_l, from which Φ_l(q) can be represented as u_lP(q).The vector u_l converts signed coefficients into indicators of the power terms included in the corresponding combination.
- Path representation: The path-based expression interprets Φ_l(q) as the sum of a selected combination of power values over intervals from T to t+1.The indicator function records whether the number of nonzero nodes on a path is even or odd.
- Elimination termination: At q=T, setting every initial energy e_i(0) and E(0) to zero terminates the Fourier-Motzkin elimination.The operator notation and path index definitions specify how the resulting vector expressions are selected and indexed.
V. THE THIRD METHOD OF ELIMINATION
The third elimination method would combine constraints that still contain the eliminated variable, but the paper proves these combinations are redundant. Consequently, the general formula from the second method already contains all effective FME inequalities.
- Third elimination method: The third method combines constraints containing e(t) to eliminate that variable, but this additional elimination creates the source of double-exponential complexity.The paper therefore seeks to establish whether these combinations add any effective inequalities.
- Computational consequence: Because the third-method combinations are redundant, the general formula derived in Section IV-C represents all effective inequalities and the third method is unnecessary for computation.The proof uses Hypotheses 1 and 2.
- Redundancy theorem: Theorem 3 proves that when the relevant resource subsets overlap, all constraints formed by combining their inequalities to eliminate e_j(t) are redundant.The redundancy applies for j in the intersection of the two subsets.
VI. MATHMATICAL EXPRESSION AND COMPUTATIONAL COMPLEXITY
The exact AFR constraints are characterized by a reduced FME formulation whose computation avoids redundant subset enumeration while retaining exponential dependence on time intervals.
- The exact AFR consists of constraints (13), indexed by every q ∈ [0,T] and l ∈ L(q).
- The apparent 2^N−2 subset combinations can be reduced because each φX,l(q) calculation decomposes across individual DSFRs.The maximum and minimum terms can therefore be computed by summing resource-level contributions rather than enumerating every subset explicitly.
- Using sparse computation, the required calculation involves O(N2^T) time complexity across N resources and T intervals.The outer layer requires N comparisons and one N-term summation, while the inner work depends on the nonzero components of u_l.
- The accurate AFR has 2(2^T−1) inequality constraints, independent of the number of resources N.Adding a resource requires only one additional term in the summations, and AFRs from two resource sets can be merged by adding their corresponding φ terms.
- Compared with original FME, the proposed derivation reduces complexity from O((2^{NT})^{2^{NT}}) to O(N2^T), but the constraint count remains exponential in T.The remaining exponential growth becomes impractical for large horizons such as T ≥ 20, motivating approximation methods in Part II.
APPENDIX A PROOF OF THEOREM 1
Appendix A proves Theorem 1 by showing that alternative elimination sequences produce inequalities already implied by direct elimination, using set relations and the model hypotheses.
- Only the right-side inequality and selected propositions are proved explicitly because the left-side and remaining cases are symmetric or analogous.
- The DSFR sets used in SP and RA satisfy disjointness and set-difference identities that organize the resulting constraint terms.These relations include Wp ∪ We = ∅, Vp ∪ Ve = ∅, and identities linking differences with intersections.
- The proof considers direct RA elimination of an inequality and compares it with the SP-RA elimination sequence.
- The proof uses known interval bounds and the stated hypotheses to establish the required inequality implications.One final transformed inequality reduces to the identity 0 ≤ 0, completing the proof of Theorem 1.
- The appendix derives the resulting inequalities by applying the relevant elimination operations to subsets of N−X and X.
APPENDIX C PROOF OF THEOREM 2
Appendix C addresses the proof of Theorem 2 by reducing the target implication to an inequality whose validity follows from Hypothesis 3.
- The appendix states that proving the displayed implication requires establishing an intermediate inequality corresponding to (C.4).
A. Proof of Proposition a)
The proof of Proposition a) applies sequential elimination operations and combines the resulting inequality with the energy constraint term.
- Applying SAX,Y(t) for nonempty Y ⊆ N−X and SAY,Z(t−1) for Z ⊆ N−Y produces the required intermediate inequality.
- The resulting inequality is combined with Ce before the proof reduces to the target implication.
- Hypothesis 3 establishes the final inequality, completing Proposition a).
B. Proof of Proposition b)
The proof establishes Proposition b) by comparing inequalities produced through alternative elimination orders and showing the resulting inequality is redundant under Hypo 2.
- Applying S_A^{X,Y}(t) followed by R_A^{Y,Z}(t−1) yields the comparison needed for the proof.
- Inequality (C.8) implies (C.7) when the stated comparison inequality holds.
- Inequality (C.9) follows from Hypo 2, completing the proof of Proposition b).
APPENDIX D PROOF OF THEOREM 3
Theorem 3 is proved by eliminating variables associated with overlapping elements and showing the resulting inequalities are redundant across all parity cases of the involved paths.
- When both paths have one non-zero node, eliminating e_j(t) combines opposite inequalities and proves redundancy by itemwise comparison.The two elimination cases are symmetric, and the argument compares contributions from X, Y, and W.
- The proof partitions elements into overlapping, exclusive, and outside sets, rewriting inequality (D.2) as (D.3).It defines X = X_a ∩ X_b, Y = X_a − X, Z = X_b − X, and W = N − (X_a ∪ X_b).
- Path-overlap and non-overlap definitions construct vectors u_l0 and corresponding paths that organize the parity-based redundancy proof.u_l0 marks positions where u_la and u_lb both equal 1, while the symmetric construction marks positions where either equals 1.
- For the odd-odd case, both paths contain the shared position q, while the constructed auxiliary path has zero at q.This establishes the parity and overlap conditions used to transform the left-hand side of inequality (D.3).
- The proof concludes after establishing inequality (D.11), completing the odd-odd case and then Theorem 3.
- The cases with parity patterns (1,0), (0,1), and (0,0) prove redundancy by adding or subtracting the corresponding inequalities.The (1,0) and (0,1) cases use addition, whereas the both-even case uses subtraction after eliminating e_j(t).