A Distributed Operational Method for Convex Hull Pricing Based on the Alternating Direction Method of Multipliers with Dantzig–Wolfe and Benders Decomposition

Yang Liu, Xinhan Lin, S. J. Chen, Zhiding Wu, Haiyan ZhengApplied Sciences 2026 · DOI

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

Abstract

Due to the non-convex characteristic of the power system, it may be difficult for power generators to recover costs by following the system operators. Therefore, independent system operators have introduced discriminatory supplementary payments as incentive measures. In this context, convex hull pricing serves as an integrated solution, capable of markedly reducing such additional payouts. For the convex hull pricing problem, we propose a distributed solution method. This algorithm is based on Dantzig–Wolfe decomposition and Benders decomposition. According to the characteristics of different units, the model is decomposed into a master problem and a group of independent subproblems, and the consensus ADMM method is used to solve the master problem. The convex hull pricing problem can still be solved using this method when the data is stored separately or when the independent agents responsible for each unit wish to protect their information privacy. While ensuring the confidentiality of each unit’s information, high-quality solutions can still be obtained with high efficiency. By comparing the numerical results with those of the other three convex hull pricing algorithms, it is evident that our algorithm can obtain high-quality solutions.
BibTeX
@inproceedings{liu2026distributed,
  author = {Yang Liu and Xinhan Lin and S. J. Chen and Zhiding Wu and Haiyan Zheng},
  title = {{A Distributed Operational Method for Convex Hull Pricing Based on the Alternating Direction Method of Multipliers with Dantzig–Wolfe and Benders Decomposition}},
  booktitle = {Applied Sciences},
  year = {2026},
  doi = {10.3390/app16021097},
}
Figure