TL;DR
This paper introduces a novel distributed algorithm for convex hull pricing in electricity markets, combining Dantzig-Wolfe and Benders decomposition with the Alternating Direction Method of Multipliers (ADMM). This approach efficiently solves complex pricing problems while preserving the privacy of individual generator data, offering a more scalable and secure solution than existing methods.
What Problem Does This Paper Address?
The electricity market aims for efficient resource allocation through marginal cost pricing. However, the non-convex nature of power systems (e.g., startup/shutdown costs) means that simple marginal cost pricing can lead to generators not recovering their full costs, necessitating "uplift payments" from the system operator. These payments increase costs and reduce market transparency. Convex hull pricing (CHP) is a method to reduce these uplift payments by approximating non-convex cost functions with convex ones. The challenge is that solving the underlying optimization problem for CHP is computationally intensive and complex, especially for large-scale power systems, and often requires centralized data, which raises privacy concerns. This paper addresses the need for an efficient, scalable, and privacy-preserving method for solving the convex hull pricing problem.
Methods
The core of this paper is a distributed algorithm that leverages a combination of established optimization techniques:
- Dantzig-Wolfe (DW) Decomposition: This technique is used to decompose the overall problem into a master problem and several subproblems, particularly for units with specific operational characteristics (grouped as G2). It helps in handling the complexity arising from the "poles" (extreme points) of the feasible region.
- Benders Decomposition: This method is applied to units with different characteristics (grouped as G3) to generate "cutting planes" that progressively refine the feasible region, effectively approximating the convex hull.
- Alternating Direction Method of Multipliers (ADMM): This is the backbone of the distributed computation. ADMM is used to solve the master problem in a decentralized manner. It allows for parallel processing of subproblems and iterative updates of consensus variables, ensuring convergence to the optimal solution while keeping data local to each unit.
The proposed method decomposes the problem into groups of units (G1, G2, G3) based on their characteristics. G2 units are handled via DW decomposition, and G3 units via Benders decomposition. ADMM then coordinates these subproblems by solving a master problem, enabling distributed computation and privacy preservation.
Datasets
The authors used a test dataset from a literature reference [21] comprising 40 instances across 8 categories, with varying numbers of units (N) and time periods (T). The experiments were conducted on a notebook computer with specific hardware and software configurations (Intel i5-13500H CPU, 16 GB RAM, Python 3.11.3, Gurobi 11.0.0). No new benchmark datasets were introduced; existing ones were used for evaluation.
Key Insights and Ideas
- Privacy-Preserving Optimization: The most significant insight is the successful integration of ADMM with decomposition methods (DW and Benders) to achieve distributed convex hull pricing. This allows individual generators to keep their operational data private while still contributing to a globally optimal pricing solution.
- Decomposition for Scalability: The paper demonstrates how breaking down a large, complex problem into smaller, manageable subproblems (via DW and Benders) and then coordinating them with ADMM is crucial for tackling large-scale power system optimization.
- Balancing Accuracy and Efficiency: The proposed method strikes a good balance between achieving high-quality solutions (close to the optimal convex hull price) and computational efficiency, outperforming traditional methods in many aspects, especially for larger problem instances.
- Adaptive Penalty Parameter: The use of adaptive penalty terms in ADMM (Algorithm 2) is highlighted as a technique to accelerate convergence, which is critical for real-time applications.
Key Results
- Solution Quality: The proposed ADMM_DB method consistently achieves high-quality solutions, with objective optimality gaps very close to the precise convex hull pricing (OPT) benchmark (within 0.1% in many cases). It outperforms traditional Column Generation (CG) and is comparable to or better than ADMM with cutting planes (ADMM_CP).
- Computational Efficiency: While not always the fastest for small problems, the ADMM_DB method shows significantly better computational efficiency than OPT and CG for larger-scale problems. It is also more efficient than ADMM_CP, reducing computation time by approximately 54-60% in some cases.
- Uplift Payments: The method effectively minimizes uplift payments, with deviations from the OPT solution being relatively small (e.g., below 11% in cases 1, 2, and 5).
- Scalability: The distributed nature of the algorithm makes it highly scalable for large numbers of generators and time periods, a key advantage over centralized methods.
Limitations and Future Work
- Computational Time for Very Large Systems: While the proposed method is efficient, the authors acknowledge that for extremely large-scale scenarios, further acceleration strategies might be needed to address iteration overhead and coordination.
- Real-time Applications: Direct application in real-time or near-real-time markets might still face challenges due to stringent computational time constraints and high-frequency data updates.
- Future Research Directions:
- Refining row-and-column generation techniques to boost computational efficiency and convergence speed.
- Extending the framework to stochastic and renewable-based convex hull pricing models to incorporate uncertainties.
- Exploring warm-start techniques, rolling-horizon implementation, and parallel/asynchronous decomposition strategies for real-time applications.
Summary updated