PaperlayerView exact revision on arXiv

Source-linked AI summary

A concise, approximate representation of a collection of loads described by polytopes

Suhail Barot, Josh A. Taylor

arXiv:1412.0939v3math.OC

TL;DR

Representing every flexible load in system operations can add prohibitive numbers of variables and constraints, while storage models may not represent every load type. The paper develops a tractable outer approximation for aggregations of polytopic loads; it is exact for some classes and reported accurate in practical scenarios.

  • Problem

    Detailed load models can add millions of variables and constraints to power-system optimization, and generalized-storage representations may not fit some load types.

    Source: B. Role within power system operations · p. 3

  • Method

    The paper forms a polynomial-time outer approximation of the loads’ Minkowski sum by collecting unique constraint rows across their H-representations.

    Source: §I · p. 1, C. Load aggregation algorithm · p. 5

  • Results

    The approximation is exact for loads with only power constraints and is reported theoretically and empirically accurate in scenarios of practical interest.

    Source: 1) Loads with only power constraints · p. 7, §V · p. 8

  • Takeaways & Limitations

    The approach captures a wide range of polytopic load types while remaining computationally tractable for power-system operations.

    Source: §I · p. 1, §V · p. 8

    Non-convex loads such as a fixed-energy task scheduled at one of several discrete times cannot be aggregated directly by this approach, though convex relaxations may be constructed.

    Source: 5) Non-polytopic loads · p. 4

Abstract

from arXiv · show

Aggregations of flexible loads can provide several power system services through demand response programs, for example load shifting and curtailment. The capabilities of demand response should therefore be represented in system operators' planning and operational routines. However, incorporating models of every load in an aggregation into these routines could compromise their tractability by adding exorbitant numbers of new variables and constraints. In this paper, we propose a novel approximation for concisely representing the capabilities of a heterogeneous aggregation of flexible loads. We assume that each load is mathematically described by a convex polytope, i.e., a set of linear constraints, a class which includes deferrable loads, thermostatically controlled loads, and generic energy storage. The set-wise sum of the loads is the Minkowski sum, which is in general computationally intractable. Our representation is an outer approximation of the Minkowski sum. The new approximation is easily computable and only uses one variable per time period corresponding to the aggregation's net power usage. Theoretical and numerical results indicate that the approximation is accurate for broad classes of loads.

I. INTRODUCTION

Demand response offers power-system flexibility, but representing every load in a large, diverse aggregation can overwhelm operational models. The paper proposes a concise outer approximation for polytopic load aggregations and uses linear-constraint representations to describe loads.

I. INTRODUCTION

  • DR can support power-system flexibility, but aggregations with many small, diverse loads may add millions of variables and constraints to operational models.Individual load models may also be known to the aggregator but not the system operator.Source: §I · p. 1
  • Concise aggregate models let aggregators share capabilities with system operators, who can incorporate them like conventional resources without increasing task difficulty.Source: §I · p. 1
  • The proposed polynomial-time outer approximation represents polytopic load aggregations as a polytope in the number of time periods, for integration into power-system optimization.The paper identifies the Minkowski sum as the aggregation’s flexibility representation and notes that computing it is generally intractable.Source: §I · p. 1
  • Related work models thermostatic loads with temperature-distribution or control approaches and represents some aggregated loads using generalized storage models.The cited approaches include deferrable-load aggregation, clustered generalized batteries, and thermal or generalized battery models.Source: §I · pp. 1–2

A. Notation

  • The paper uses both vertex representations, which specify a polytope by its extreme points, and H-representations, which specify it through linear inequalities.The H-representation is generally preferred for demand response because it matches the form of most load models; converting between the two forms is generally NP-hard.Source: A. Notation · p. 2
  • In H-representation, an A-matrix collects the inequality coefficients, paired with a vector of bounds to describe the polytope.Source: A. Notation · p. 2

B. Role within power system operations

Multi-period optimal power flow can represent demand response alongside other resources, but detailed models for many loads are unwieldy. The paper motivates a compact polytope model for aggregate power across time.

B. Role within power system operations

  • Demand response has dynamic constraints, such as temperature bounds and vehicle arrival and departure times, making it relevant to multi-period power-system dispatch.Multi-period optimal power flow also accommodates system dynamics such as ramping and storage limits.Source: B. Role within power system operations · p. 2
  • Adding individual demand-response models to optimal power flow can introduce millions of variables and constraints, while generalized-storage representations may not fit some load types.Source: B. Role within power system operations · p. 3
  • The paper seeks an aggregate set P = {x | Ax ≤ b}, where x records power injections over D periods, so a small polytope can enter multi-period optimal power flow without a large model expansion.Source: B. Role within power system operations · p. 3

C. Modeling Loads as Polytopes

  • Load models use bounded polytopes over time; shared parameters include power limits, usable or storable energy, initial stored energy, dissipation, and input/output efficiencies.The exposition assumes one time period per unit of duration.Source: C. Modeling Loads as Polytopes · p. 3

1) Storage-like Loads:

The load models express storage-like and thermostatic behavior as polytopes over time. Their constraints capture energy, power, losses, conversion efficiency, and temperature limits.

1) Storage-like Loads:

  • Storage-like loads, such as charging electric vehicles, divide power into inflows and outflows and impose an energy constraint alongside power, leakage, and conversion-efficiency limits.Source: 1) Storage-like Loads · p. 3

2) Thermostatic loads:

  • Thermostatic-load models specify thermal parameters including resistance, capacitance, ambient and set-point temperatures, rated power, and deadband.The model is presented by reference to.Source: 2) Thermostatic loads · p. 3
  • A thermostatic load’s temperature dynamics and deadband are expressed as constraints, with the resulting inequality similar to a generalized-storage energy constraint.Source: 2) Thermostatic loads · pp. 3–4

3) Deferrable loads:

The deferrable-load example represents required energy and power limits with linear constraints, while encoding availability through arrival and departure times.

3) Deferrable loads:

  • The example models a perfectly efficient deferrable load with power limits and a single equality constraint for its total energy requirement E.The paper describes such loads as storage-like loads with arrival and departure times.Source: 3) Deferrable loads · p. 4
  • The deferrable-load constraints are also given in matrix form for a polytope representation.Source: 3) Deferrable loads · p. 4
  • Arrival and departure times are encoded by setting the maximum-power vector Pmax according to the load’s availability window.The passage identifies ta as arrival time and td as departure time.Source: 3) Deferrable loads · p. 4

4) Differential power constraints:

Flexible-load aggregation is represented through the Minkowski sum of load polytopes, but computing that sum can be intractable. The proposed approximation targets polytopic loads, while non-polytopic loads require a convex relaxation to use this approach.

4) Differential power constraints:

  • Differential power constraints bound the bidirectional change in a load’s power between consecutive periods and can be added to the described load models.They are commonly encountered with industrial equipment.Source: 4) Differential power constraints · p. 4

5) Non-polytopic loads:

  • A non-polytopic load cannot be simply aggregated with polytopes using this approach, though a convex relaxation can sometimes be constructed.The example of a 100 kW one-hour load within a three-hour window is represented as a union of three points, then relaxed to a polytope.Source: 5) Non-polytopic loads · p. 4

D. Load Aggregation as Minkowski Sums

  • For loads specified as polytopes, the Minkowski sum exactly describes an aggregation’s capability, but computing it from H-representations is intractable for non-trivial polytopes.The described V-representation method requires vertex enumeration for both polytopes.Source: D. Load Aggregation as Minkowski Sums · p. 4

III. APPROXIMATE LOAD AGGREGATION

  • The paper develops a generic outer approximation of the Minkowski sum of two polytopes.Source: §III · p. 4

A. Polytopes with the same shape

For two polytopes with the same constraint matrix, summing their right-hand-side vectors gives an outer approximation of their Minkowski sum. In the triangle example, this approximation is exact.

A. Polytopes with the same shape

B. Extension to general polytopes

The shared-matrix approximation is extended to arbitrary polytopes by adding redundant constraints so their constraint matrices match. This broadens the method to aggregations containing different load types.

B. Extension to general polytopes

  • The extension broadens applicability from polytopes with the same A-matrix to arbitrary polytopes, including aggregations with different load types.Source: B. Extension to general polytopes · p. 5
  • Missing constraints are added as redundant constraints, with their tightest valid bounds found by linear programming, to create equivalent representations with matching A-matrices.The added constraints are tangent to the polytope; the resulting representations enable use of the shared-matrix approximation.Source: B. Extension to general polytopes · p. 5
  • With m1 and m2 constraints and c constraints in common, the resulting outer approximation has m1 + m2 − c constraints.Source: B. Extension to general polytopes · p. 5

C. Load aggregation algorithm

The algorithm builds a common constraint matrix from the unique rows across load polytopes, then uses linear programs to find bounds and outputs an outer approximation. Its complexity grows polynomially with the number of loads and dimensions.

C. Load aggregation algorithm

  • The algorithm searches the load polytopes’ A-matrices for unique rows, then runs linear programs to find tangent facets and construct the bounds for an outer approximation.The number of linear programs is at most cN, where c is the number of unique constraints and N the number of loads.Source: C. Load aggregation algorithm · pp. 5–6
  • The algorithm’s complexity grows polynomially with the number of loads and dimensions because it invokes a polynomial number of linear programs.Source: C. Load aggregation algorithm · p. 6

IV. EXAMPLES

The numerical examples assess the outer Minkowski approximation by comparing polytope volumes for thermostatic-load and storage aggregations. The reported errors are low in the tested settings, with exact-volume comparisons for storage limited to dimensions through R6.

A. Numerical Examples:

  • The study estimates accuracy from volume ratios, using Monte Carlo for high-dimensional polytopes and exact-volume calculations for storage sums through R6.Thermostatic tests use 1,000 randomized loads under two heterogeneity ranges; storage tests use 1,000 pairwise cases of non-dissipative, fully present loads with unit efficiencies.Source: A. Numerical Examples · p. 6, 1) Thermostatic Loads · p. 6, 2) Storage Loads · p. 7

1) Thermostatic Loads:

  • For thermostatic aggregations, OM is about 1.5–2 times more accurate than GB-N, and its relative performance improves with higher load heterogeneity.The comparison uses volume ratios across discretizations of a one-hour period in low- and high-heterogeneity scenarios.Source: 1) Thermostatic Loads · pp. 6–7

2) Storage Loads:

  • The mean volume of the storage approximation scales exponentially with dimension, appearing linear on a semilogarithmic plot.Monte Carlo estimates extended the approximation-volume analysis to R20.Source: 2) Storage Loads · p. 7, Figure 3 · p. 7
  • For storage aggregations, the OM approximation’s volume error remains below 0.7% through R6 and grows sub-linearly with dimension.Exact-volume computation was intractable beyond R6, so the higher-dimensional volume trend was estimated by Monte Carlo.Source: 2) Storage Loads · p. 7

B. Analytical Results

The analytical results identify load classes for which the outer Minkowski approximation is exact. These include loads with only power constraints and deferrable loads sharing the same time periods.

B. Analytical Results

  • The section establishes exactness results for specific load classes rather than asserting exactness for general polytopes.It presents two analytical results on when the outer approximation is exact.Source: B. Analytical Results · p. 7

1) Loads with only power constraints:

  • For loads with only power constraints, the outer approximation is exact and is the hypercube formed by summing the corresponding power bounds.The result applies to two hypercube loads defined by their per-period power-limit vectors.Source: 1) Loads with only power constraints · p. 7

2) Deferrable loads:

  • For two deferrable loads present over the same time periods, the outer approximation is exact and retains the simplex structure with combined energy requirement E1 + E2.The summed vertices have the same form as those of the original loads, with total energy E1 + E2.Source: 2) Deferrable loads · pp. 7–8

V. CONCLUSIONS

The technique aggregates heterogeneous loads described by polytopes and is reported to be tractable and accurate in scenarios of practical interest. Uncertainty handling remains under development, and allocating aggregate power among individual loads is outside this work's scope.

V. CONCLUSIONS

  • The technique aggregates heterogeneous polytopic loads and is reported to be computationally tractable and theoretically and empirically accurate in practical scenarios.It also captures a wide range of load types.Source: §V · p. 8
  • Extensions to handle uncertainty are still in development, with the aim of representing probabilistically defined loads whose constraints may not be exactly specified.Electric-vehicle arrival and departure times are given as an example of uncertain constraints.Source: §V · p. 8
  • The work does not specify how to allocate bulk power among individual loads, a task that involves equity, cost, and preserving flexibility for future periods.Source: §V · p. 8

Related papers

Loading 1412.0939v3…