The growing integration of Distributed Generation (DG) and Demand Response (DR) resources into electrical grids has highlighted the need for innovative solutions to coordinate Price-Responsive Devices (PRDs). These devices operate as autonomous entities seeking to adjust their usage schedules in response to current electricity prices to maximize their individual benefits. Here, we introduce an innovative technique grounded in the Dantzig-Wolfe (DW) Decomposition to coordinate these autonomous PRDs within a decentralized framework. By leveraging the inherent parallel structure of DW, we treat the independent optimization routines of the PRDs as separate subproblems. A central entity—typically the utility or system operator—gathers the consumption proposals (bids) from these devices, resolves the master problem in the DW structure, and generates an appropriate price signal in response. This method achieves rapid convergence because the numerous subproblems—potentially numbering in the millions across many PRDs—can be addressed in parallel. Moreover, drawing on DW principles, if the individual device subproblems remain convex, the process converges to the globally optimal solution (corresponding to a Nash Equilibrium) after a modest number of rounds. The effectiveness of this framework was tested through a case study involving 200 participating homes, each with two load categories: Electric Vehicles (EVs), representing shiftable/interruptible loads, and Electric Water Heaters (EWHs), serving as thermostatically controlled appliances (TCLs). Simulations revealed that convergence to the optimum leads to lower overall generation expenses and reduced consumer bills (calculated via marginal generation costs), alongside a substantial drop in the aggregate demand’s Peak-to-Average Ratio (PAR).
Power networks are seeing daily additions of both renewable and conventional Distributed Generation (DG) resources, along with large-scale energy storage and Demand Response (DR) capabilities. Coupled with advancements in high-speed, reliable communication systems such as 5G, these developments enable bidirectional information exchange between producers and consumers, presenting new challenges and opportunities for grid operations [1, 2]. Addressing these issues and capitalizing on the benefits requires integrated oversight of both load and supply sides. Such combined management offers key benefits for contemporary smart grids, including improved supply-demand alignment, greater integration of intermittent renewables, and support for system services such as frequency regulation and voltage support through DG and DR assets.
A variety of techniques for coordinating flexible loads have appeared in prior research [3, 4]. Among them, group-level management of price-responsive devices (PRDs) is attracting increasing interest. This market-oriented strategy not only delivers the benefits outlined earlier but also motivates producers and consumers alike to advance smart grid objectives. Essentially, coordinating PRDs applies core economic principles of open markets to electricity systems, enabling greater renewable uptake through markets for surplus output, enhanced system reliability through ancillary services such as peak reduction and voltage/frequency support, and overall cost savings [5, 6]. Some existing methods rely on centralized oversight, where a single controller directs appliances toward goals such as load valley filling or cost reduction [7, 8].
A fundamental distinction in PRD management lies between centralized and decentralized paradigms [9]. Centralized methods were practical historically due to limited communication infrastructure and few responsive loads. Yet, as adoption of flexible assets—such as storage units, EVs, and temperature-regulated devices—rises, centralized schemes risk missing truly optimal outcomes and forego the potential for genuine market-driven interactions between supply and demand. To avoid these drawbacks, numerous efforts have advocated decentralized strategies for managing adaptable loads [10, 11].
This study presents a decentralized, market-driven framework for coordinating household appliances. PRDs are depicted as rational, self-interested agents focused on minimizing their personal electricity expenses through independent optimization. Examples include EVs (as shiftable/interruptible loads) and Electric Water Heaters (EWHs, as thermostatically controlled loads or TCAs). These devices interact solely with an aggregator, submitting their planned consumption profiles (bids) and receiving updated price information. No direct device-to-device data exchange occurs, and we presume no single device wields significant market influence or forms groups to distort outcomes.
Key contributions of the present approach include:
(a) incorporating users’ individual trade-offs between service quality and expense savings, (b) effectively managing binary or threshold-responsive assets such as EVs and home batteries (which frequently sit at the system margin and require precise coordination), and (c) demonstrating scalability to handle arbitrarily large numbers of devices exhibiting diverse price sensitivities.
This portion surveys techniques addressing appliance coordination where each participant’s independent choice plays a critical role. Objectives vary—ranging from minimizing production costs to achieving load valley filling or peak reduction—but these goals often produce overlapping outcomes. Optimizing one typically approximates good performance on related metrics. For instance, minimizing generation expenses [12] frequently results in smoother, flatter demand profiles (valley filling or overall reduction) [13-17]. Although system operators may prioritize different aims that tend to align [18, 19], responsive loads fall into two broad categories: those aligned directly with operator goals via direct load control (DLC) [20], or those pursuing personal gain through market participation and price-based bidding [12].
Operator-focused control yields clear system-level gains (e.g., lower production costs) and may also confer indirect benefits to consumers through rebates or credits. Nevertheless, such indirect gains might fall short of what users could achieve independently, potentially discouraging program participation.
Market-oriented methods, therefore, tend to attract greater user engagement by offering maximum personal benefit and decision autonomy. A prominent stream of research on decentralized, market-based PRD coordination—treating devices as competing, self-optimizing entities—relies on game-theoretic models [12, 17, 21-24].
Approaches in Refs. [25] and [26] employ Mean Field Games (MFG), where individual actions matter less than the collective (average) behavior of the population. Devices react to prices, with the large-scale group treated as an infinite group; quadratic cost terms enable convergence to an ε-Nash equilibrium.
Reference [27] applies MFG in a distributed manner to schedule large populations of thermostatically controlled loads (TCLs), enabling rational agents to schedule usage and participate in frequency-support markets.
Gan et al. [17] introduced a decentralized scheme for valley filling leveraging EVs’ flexible charging needs. EVs adjust based on iterative signals until optimality is reached. However, the approach is not truly market-based, as devices align with system-wide valley-filling goals rather than purely minimizing personal costs. While broadly beneficial, individual user savings and cost reductions were not explicitly quantified.
In [23], a distributed procedure achieves a Nash equilibrium among self-interested plug-in EVs (PEVs) via iterative price updates based on average bids. The intent is to synchronize load across EVs, though the precise mechanism for reducing system costs or individual payments remains unclear.
Reference [28] develops a decentralized PEV strategy that balances production expenses with overload and battery wear costs, converging to socially acceptable coordination under reasonable assumptions.
An instant-settlement billing model for peak shifting is presented in Ref. [29], which models appliances as selfish actors and offers scenario-specific paths to the Nash equilibrium (centralized, distributed, or controlled cases).
Rivera et al. [19] present a distributed ADMM-based EV scheduling framework with a composite objective blending aggregator and user priorities. It supports multiple aims (valley filling, cost minimization) but applies weights that may introduce bias favoring one side.
Building on Ref. [19] ’s ADMM, Ref. [30] coordinates EV groups where local optimization handles charging while a higher-level Macro Load Area Aggregator supplies DER profiles, attaining Walrasian equilibrium [31] at convergence.
Depaola et al. [12] describe an iterative, game-theoretic PRD coordination that is theoretically proven to reach the Nash equilibrium, with per-iteration cost declines observed. Its sequential (non-parallel) nature makes it slow for large-scale deployment; a quicker, though slightly suboptimal, variant was suggested.
Mohsenian et al. [18] propose a game-theoretic method for competitive agents that requires full mutual awareness of behaviors (i.e., non-private). It achieves a Nash equilibrium equivalent to global cost minimization under certain conditions. Drawbacks include privacy erosion (all parties can observe others’ actions, enabling potential misuse) and the need for demanding infrastructure for high-bandwidth, low-latency peer-to-peer communication.
Whereas prior methods pursue Nash equilibrium via game theory, an alternative is to formulate a unified optimization that encompasses both electricity production costs and the individual PRDs’ local objectives (their effective electricity usage expenses), as illustrated in Figure 1a. Importantly, this differs from conventional multi-objective setups. The formulation in Figure 1a jointly optimizes unit commitment with the self-interested PRD problems. Its purpose is to identify price signals and consumption bids (key decision variables) that simultaneously reduce consumer payments and total generation expenses.
Figure 1. (a) Integrated formulation of unit commitment incorporating price-responsive devices (solved as a single monolithic problem), and (b) Application of Dantzig-Wolfe decomposition to the integrated model (illustrating two representative iterations of the procedure).
Consider a scenario in which the system operator possesses complete knowledge of every appliance’s individual preferences. (In the context of this study, price-responsive devices [PRDs] are treated as rational, utility-maximizing agents whose preferences emerge from solving their own private optimization routines.) If the operator understands precisely how each device would respond to any given price—i.e., the outcome of its local optimization—then an ideal operating point exists where both total generation expenses and the aggregate of end-users’ local objectives are simultaneously minimized. At this equilibrium point (equivalent to a Nash Equilibrium), neither the grid operator nor the individual consumers would wish to alter their respective production or consumption decisions.
Nevertheless, solving the problem in its full centralized form faces two fundamental obstacles. First, the resulting mathematical program becomes prohibitively large. Second, it demands that the system operator obtain and maintain detailed, up-to-date information on the private preferences of every appliance in every household. The following section introduces a practical alternative that circumvents these difficulties by applying the Dantzig-Wolfe (DW) decomposition framework.
Originally developed to address very large-scale linear programs [32], the Dantzig-Wolfe (DW) procedure decomposes such problems into a coordinating master problem and multiple independent subproblems. These subproblems can be solved concurrently—often on separate machines—with only their solution proposals communicated back to the master-problem processor at each step.
The original model (OM) displays a pronounced block-angular structure with high sparsity: decision variables associated with device j are decoupled from those of device j+1, and the sole coupling among all subproblems arises through a single global balance constraint that equates total scheduled generation to total consumption. This structural property renders the OM especially well-suited to DW decomposition.
Figure 1b outlines the core iterative logic of the DW procedure, which repeats until a predefined convergence criterion is satisfied or further progress becomes negligible. In the proposed scheme, the private, self-interested optimization routines of the PRDs are cast as DW subproblems, while the unit commitment (supply-side) objective serves as the master problem. Solving the master problem produces a candidate aggregate load profile for each participant together with a corresponding price signal derived from the marginal cost of generation. In response, each PRD solves its local subproblem using the received price, yielding a revised consumption schedule (energy bid) that reflects its willingness to consume under the quoted tariff. The exchange continues iteratively until neither side—neither the operator updating the price nor the devices updating their bids—alters its proposal, signaling arrival at the optimal equilibrium.
Although classical linear programming solvers (Simplex, interior-point, dual Simplex, ellipsoid method, etc.) could theoretically address the OM, the DW approach offers distinct practical benefits when the problem is (1) extremely large in dimension, (2) highly sparse, and (3) block-angular in structure. These traits align ideally with DW’s strengths, and—assuming the master and subproblems remain linear—the method guarantees convergence to the global optimum. Moreover, the information exchange is minimal: only price signals flow from the unit commitment master to the devices, and only aggregate energy bids return to the operator. This bidirectional communication is markedly more efficient than sequential single-device updates required by earlier schemes [12, 18]. Privacy is preserved because devices disclose consumption intentions solely to the central coordinator, eliminating peer-to-peer information sharing as in [12, 18] and thereby reducing opportunities for collusive manipulation. Finally, the procedure is inherently market-based: it aligns supply and demand through iterative price discovery, thereby supporting the smooth integration of distributed renewable generation into the electricity system.
Essential components of the unit commitment problem when price-responsive devices participate can be expressed compactly as follows:
(1)
In this formulation, G denotes the set of dispatchable generating units, and D denotes the set of price-responsive devices. The principal decision variables are the hourly power outputs gi from each plant i and the hourly consumption dj by each device j (both vectors spanning the 24-hour operating horizon). For each device j, zj captures all auxiliary internal decisions (e.g., temperature setpoints, battery state-of-charge trajectories, etc.). The pair (dj, zj) fully specifies the operating schedule for device j over the planning period. The function ci(·) gives the production cost per unit for unit i. At the same time, bj(·) quantifies—in monetary terms—the benefit (i.e., maximum willingness to pay) that the owner of device j derives from executing the chosen plan (dj, zj). The only equality constraint displayed enforces daily energy balance: total scheduled output from controllable plants plus fixed uncontrollable generation g0 (e.g., distributed photovoltaic output) equals total consumption by responsive devices plus fixed non-responsive demand d0.
For clarity of exposition, numerous realistic features are omitted here, including start-up/shut-down costs, minimum/maximum output limits, minimum up- and down-time restrictions, transmission constraints under normal and contingency conditions, and related operational limits [33-39]. These elements can be reinstated in subsequent extensions.
If we split Eq. 1 into a power production cost function C(D) and a consumption benefit function B(D) as follows:
(2)
(3)
Then Eq. 1 becomes simple.
(4)
Equivalently, the system operator seeks a feasible demand profile D that minimizes net system cost, defined as production cost C(D) minus the aggregate value B(D) that customers place on their chosen consumption patterns.
In realistic large-scale systems, transmitting the full details of every PRD’s benefit function to a central entity is impractical. Even if such information transfer were feasible, the resulting joint unit commitment model—with potentially millions of responsive devices—would exceed the computational capacity of any single machine. To address these challenges, the present work develops a distributed, iterative coordination protocol derived from Dantzig-Wolfe decomposition of the unit commitment problem, delegating the computation of demand-side subproblems to the devices themselves.
Two key characteristics enable this decomposition. First, the only linkage between individual PRD optimization tasks and the central unit commitment is the global supply-demand balance requirement. Second, the private optimization problems faced by most PRDs are convex (frequently linear or quadratic), as is the aggregate benefit function B(D), which is simply the sum of independent convex subproblems. These properties hold for both the individual device problems and the overall consumption-side objective.
Dantzig-Wolfe decomposition is a classical iterative method for handling convex programs that are too large to fully instantiate in memory [32, 40-43]. It is therefore well-matched to the unit commitment problem with very high numbers of PRDs. The technique also provides strong theoretical guarantees: each iteration yields a strictly improving solution; convergence is finite when subproblems are linear; the gap between the primal and dual objectives at every step quantifies the distance to optimality; and any intermediate solution remains feasible even if the procedure is terminated early.
The method rests on two fundamental properties of convex optimization: (1) every feasible point lies within the convex hull of the problem’s extreme points, and (2) the objective function value over the feasible region is likewise the convex hull of its values at those extreme points.
These properties permit rewriting the aggregate consumption benefit function as a convex combination over extreme points:
(5)
Where K indexes the (typically enormous) set of all feasible demand profiles, dk is the demand vector associated with extreme point k, bk = B(dk) is the corresponding benefit value, and wk ≥ 0 is the weight assigned to that point (with ∑ wk = 1). Substituting this representation into the earlier compact form (Eq. 4) yields the Dantzig-Wolfe master problem:
(6)
The master problem thus constructs an optimal demand profile D as a convex combination of known extreme points that minimizes net cost C(D) – B(D).
Because enumerating the complete set K is intractable, DW iteratively constructs a restricted subset K′ of promising extreme points sufficient to approximate the optimum [32]. This is accomplished by alternating between solving the current master problem (Eq. 6) and the following demand-side pricing subproblem:
(7)
Here, p is the vector of hourly marginal prices obtained from the dual variables of the balance constraint in the preceding master solve. Solving (Eq. 7) with the current price vector p identifies the consumption plan D that maximizes net benefit (or equivalently minimizes expenditure) at those prices. Because the subproblem is convex, its optimum occurs at an extreme point of the feasible consumption set, furnishing a new candidate point dk together with its benefit value bk = B(dk) to enrich the working set K′ for the next master iteration.
This iterative exchange persists until no additional extreme point emerges that can further reduce the net system cost. At this stage, the procedure has converged to the optimal aggregate consumption schedule [32]. When the benefit function B(D) takes the form of a linear program (or can be equivalently reformulated as one), the feasible region possesses only a finite number of extreme points, ensuring finite-step convergence. By contrast, for nonlinear yet convex programs, the feasible region corresponds to a linear program with an infinite set of extreme points; in such cases, the solution quality steadily improves with each round, asymptotically nearing the true optimum.
In practice, therefore, the joint unit commitment problem involving price-responsive devices (PRDs) is resolved through the following iterative sequence. At every cycle, the master problem (Eq. 6) identifies the most advantageous weighted combination of all previously submitted demand profiles and derives candidate price levels for the demand-side subproblem. The demand-side subproblem then returns a consumption profile that can be accommodated at an equal or lower net cost (production cost minus customer benefit). More precisely, the steps are:
1. The central coordinator initializes a starting price vector p(0).
2. The consumption subproblem (Eq. 7) is executed in a decentralized fashion:
a. The central coordinator distributes the current price vector pk to all participating PRDs.
b. Each PRD independently solves its private optimization task and submits its preferred demand schedule d_j,k (the vector of hourly energy consumption planned by device j in iteration k) together with the corresponding benefit value b_j,k (an estimate—expressed in monetary terms—of the value the device owner attaches to executing that schedule, i.e., the maximum amount the owner would pay for it). For privacy or simplicity, the absolute level of the benefit may include an arbitrary constant offset that remains fixed across iterations.
c. The individual dj,k and bj,k are aggregated across all devices to form a system-wide demand profile dk and total benefit bk.
1. The central coordinator incorporates the newly obtained demand profile dk and its benefit value bk into the working set of extreme points K′ and re-solves the master problem (Eq. 6), selecting an improved convex combination of the accumulated extreme points. If a predefined optimality tolerance is satisfied or a maximum iteration count is reached, the algorithm terminates. Otherwise, a modest improvement in the objective has been achieved; the coordinator extracts updated prices p(k+1) from the dual variables associated with the load-balance constraints and returns to step 2.
2. Upon completion, the final nonzero weights wk produced by the master problem (6) are communicated to the PRDs (or to intermediate home- or feeder-level coordinators). Each device’s final consumption schedule is then obtained by weighting its previously submitted bids according to these coefficients. If full convergence has occurred, the resulting load vectors are simultaneously optimal for every individual PRD and for the overall system at the equilibrium prices. Even in the event of early termination, the final price and load assignments remain feasible and represent an improvement over the initial conditions for both the system operator and the participating consumers.
A key strength of this mechanism is its ability to form any convex combination of the demand bids already received from the PRDs, rather than being restricted to exactly replicating a submitted profile. This flexibility proves especially valuable when dealing with highly price-elastic devices (such as EVs or behind-the-meter batteries). In such cases, (1) Devices that are marginal in multiple periods tend to fully arbitrage even tiny price differentials, flattening efficient prices across those intervals and thereby weakening the ability of pure price signals to induce desired load shapes (e.g., valley filling or renewable tracking). The DW approach supplements the price signal with an effective quantity signal by blending profiles. (2) Conventional price-adjustment schemes often struggle with near-infinite elasticity, as minuscule price changes can trigger extreme load swings, leading to persistent oscillation rather than convergence to a stable price vector—and even a correct price vector may fail to produce the intended consumption pattern. By contrast, the proposed DW-based method handles highly elastic devices robustly and rapidly converges by appropriately mixing bids from either side of the equilibrium.
Moreover, the demand-side subproblem lends itself naturally to complete decomposition across individual devices. The coordinator broadcasts the same price vector to every PRD, each solves its local model, and the resulting demand vectors and benefit scalars are simply summed. This structure enables massive parallelism and low-bandwidth communication in a realistic deployment. For instance, a central system-level coordinator could solve the master problem, while distribution-level (feeder) coordinators and household-level coordinators manage aggregation at their respective tiers. At each hierarchical level, only price vectors are sent downward, and summed demand/benefit scalars are returned upward. This successive aggregation reduces the data volume dramatically at each stage, requiring only modest communication capacity (sufficient to exchange information with a few dozen entities at the adjacent level). The framework accommodates arbitrary heterogeneity among PRDs without modification, provided each exhibits a convex (rational) price response.
Existing studies commonly classify loads into non-shiftable (must-run), shiftable (interruptible), and thermostatically controlled appliances (TCAs) [44]. Non-shiftable loads (e.g., televisions, microwaves) require immediate energy delivery and exhibit no flexibility. Shiftable/interruptible loads (e.g., electric vehicles, dishwashers, clothes dryers) do not demand instantaneous service because they incorporate storage or operate on daily/weekly cycles without strict urgency [45]. TCAs (e.g., air conditioners, refrigerators, water heaters) modulate consumption in response to temperature dynamics (ambient conditions or user-setpoints), with energy input/output influencing internal states.
Although many prior works on energy management focus solely on non-shiftable and shiftable loads [18], non-shiftable devices are inherently unresponsive to price or control signals. They can therefore be treated as fixed background demand without loss of generality. Given the impracticality of modeling every load type exhaustively—and noting behavioral similarities across categories—this study selects electric vehicles (EVs) to represent shiftable/interruptible loads and electric water heaters (EWHs) to represent TCAs. The subsections below detail the private, self-interested optimization models these devices use during the market-based bidding process.
The EWH model developed here seeks to minimize the combined economic cost of electricity purchases and the discomfort cost associated with under-heated water. Formulated as a linear program for day-ahead scheduling, it draws on a simplified thermodynamic representation introduced in [5]. The model assumes perfect foreknowledge of daily hot-water demand patterns and optimizes power draw accordingly. Future extensions could incorporate stochastic hot-water forecasts, allowing the EWH to bid power vectors under uncertainty as outlined in [5].
The bi-objective cost Eq. 8 balances electricity expenditure against discomfort:
Here, pk denotes the price vector received from the master problem in iteration k, I indexes the 24 hourly intervals of the planning day, Ein is the energy input (kWh) during hour h, and ps (in $/kWh) is a constant penalty reflecting the customer’s willingness to pay to avoid each kWh of heating shortfall. The term psEshorth provides a linear, volume- and temperature-sensitive proxy for the customer’s demand for satisfactory hot water.
Eq. 9 captures the tank’s thermal dynamics: Ttank is the water temperature at the end of hour h, tamb is the forecasted ambient air temperature, rloss is the normalized heat-loss coefficient per hour, and ctank (°C/kWh) is the temperature rise per unit of input energy.
(9)
Constraint (10) enforces the EWH’s maximum input power limit, emax (kWh/h).
(10)
Constraints (11) and (12) quantify temperature shortfall Tshort (relative to the user’s minimum acceptable temperature Tmin) and the resulting energy shortfall Eshort, respectively. Discomfort depends jointly on the degree of under-heating and the volume (energy equivalent) of water demanded.
(11)
(12)
Once the problem is resolved, PRD number j reports its consumption vector for iteration k as dj,k = [Ein0, Ein1, Ein2, ..., Ein23]. It also computes the benefit bj,k as the product of the shortfall penalty and the total amount of hot water consumed, which is expressed as ps * ∑(h∈I) Einh. This penalty can vary across iterations as the plan adjusts to fluctuating electricity prices. By definition, this represents the amount the customer is willing to pay for the hot water they receive and, by extension, for the energy used to produce it.
Electric vehicles follow a straightforward cost-optimization approach. The user specifies the charging hours for the EV (referred to as parking hours), each associated with a maximum charging rate emaxh for hour h. The energy required by the vehicle at the end of the charging window is referred to as EDES and represents the total energy needed for the day. The objective of cost-minimization programming is to determine the most economical charging hours for the vehicle.
The cost function is given in Eq. 13, where the goal is to minimize the user’s electricity cost. As with the Electric Water Heater (EWH) problem, the price minimized for the EV is determined by the master problem, i.e., pp = Pk.
(13)
In this equation, I denotes the set of all hours in the upcoming day, and php denotes the tentative price of electricity for each of those hours. Einh is the decision variable representing the energy consumed for charging in each hour.
The charging window is modeled by Eq. 14
(14)
Ensuring that the total energy delivered to the battery across the selected hours equals the required energy. Eq. 15 enforces this constraint.
(15)
We employ a straightforward algorithm to address this linear program:
· Identify the hours of the day during which charging can occur (where emaxh > 0).
· Arrange these hours in ascending order of price, using time of day (earliest to latest) as the secondary sorting criterion in case of price ties.
· For each hour in this ordered list, beginning with the lowest-priced one, allocate as much charging as needed to achieve the desired energy level, or charge at the maximum allowable rate, emaxh for that hour—whichever quantity is smaller.
Once the optimal charging schedule is determined, the EV model returns the resulting consumption profile dj,k = [Ein0, Ein1, Ein2, …, Ein23]. Under this algorithm, the EV consistently achieves a full charge, meaning the value derived by the EV remains constant regardless of the selected charging strategy. Consequently, the reported benefit bj,k is zero for every EV in each iteration.
In the Dantzig-Wolfe (DW) iteration process outlined in this study, the consumption subproblem (7) is treated as one unified problem that covers all price-responsive devices (PRDs) across the system. This is accomplished by presenting the identical price vector pp = pk to every water heater and electric vehicle model, computing the individual optimal response for each PRD, and then aggregating their consumption schedules:
(16)
These aggregated profiles are subsequently submitted to the central coordinator. The parameter N denotes the total number of DW iterations performed. There are two possible stopping criteria: 1) execute a fixed, predefined number of iterations, or 2) continue until the optimality gap falls below a specified threshold.
Following the final master problem solution, the weights wk obtained from the master problem (6) are distributed back to the individual PRDs according to their earlier submitted bids:
(17)
This allocation can occur either by directly communicating the weights to the devices or by having a home-level or circuit-level coordinator compute the final consumption vector dj* and inform device j of the precise power quantity it has been allocated.
With this allocation procedure, the aggregate power demand across all PRDs precisely corresponds to the total demand profile determined by the system-level master problem:
(18)
The proposed framework assumes that all PRDs exhibit convex responses to price signals. It does not assign distinct weights to the extreme points (bids) submitted by individual devices. In future extensions, the approach could accommodate devices involving discrete (integer) decisions—for instance, dishwashers or washing machines that must complete full cycles once initiated. One viable strategy would involve refining weights at the feeder (neighborhood) level, enforcing integer weights where required for discrete devices while adjusting weights across all PRDs on that feeder to ensure the total feeder load aligns as closely as possible with the system-requested amount.
For this study, we adopt a basic electricity generation model. We disregard non-dispatchable generation g0 and non-price-responsive loads d0, simplifying the load-balance constraint in Eq. 2 to:
(19)
We further assume a quadratic cost function for power production, such that the minimum cost of supplying a demand level D is given by:
(20)
Where Dh represents the demand in hour h. These simplifications yield a straightforward system in which marginal costs equal 2aDh for each hour. Nevertheless, the method presented here remains broadly applicable to any convex supply-side formulation—for example, a linear program in which marginal costs correspond to the dual variables of the hourly load-balance constraints.
By iteration N of the Dantzig-Wolfe process, the system’s PRDs have disclosed the following extreme points (feasible consumption vectors):
(21)
Where N is the number of completed iterations/bids, and dk is the aggregate consumption bid submitted by all PRDs in iteration k. The customer benefit associated with each extreme point (representing the maximum willingness to pay for that consumption vector, up to a possible constant shift) is:
(22)
With bk denoting the scalar sum of benefits reported by all individual PRDs.
Because the feasible regions of the EV and EWH models are convex, any convex combination of their bids remains feasible. Accordingly, the master problem constructs an overall consumption plan (load vector) as a convex combination of prior bids:
(23)
Where D is the constructed bid (vector, one element for each hour h).
The total benefit of this constructed bid is B(D), where
(24)
The central coordinator lacks direct knowledge of the true benefit function B(D). However, through successive iterations, its approximated version B′(D) gradually converges toward the actual B(D) value [32]. As mentioned earlier, this convergence occurs in a finite number of steps when the PRD subproblems are formulated as linear programs—which is the case in this study—and approaches the true value asymptotically if the PRD subproblems are convex but nonlinear.
Dantzig-Wolfe decomposition produces an optimality gap at every iteration. This gap reflects the difference between two key quantities: Sbest, the best attainable objective function value, and Sknown, the best objective value identified up to that point.
In iteration k, the master problem seeks to minimize the expression C(D) − B′(D). The resulting objective value at the selected solution is given by
(25)
Where Dk denotes the demand vector chosen by the master problem during round k.
A value denoted as Sknown serves as a valid lower bound on the objective, since it corresponds to a realizable solution. Within the master formulation, B′(Dk) is constructed cautiously, representing a convex combination of previously evaluated points on the actual benefit curve B(D); due to the convex nature of B(Dk), this approximation cannot exceed the true value and therefore remains at or below B(Dk) for the demand vector Dk. Likewise, C(Dk) reflects the genuine generation cost and is therefore attainable.
After resolving the master problem at iteration k, the coordinating entity communicates provisional price signals, pk , to end users. In response, consumers determine their hourly demand quantities dk, collectively indicating the total energy they intend to purchase, and report the associated utility value bk. The obtained subproblem solution dk (with corresponding benefit bk) is optimal, implying that any alternative demand vector d would not yield a better objective outcome; formally, all other feasible d result in objective values that are no greater, i.e.,
(26)
For all d, which leads to
(27)
The master problem produces the solution Dk, associated with a production cost C(Dk) and a marginal cost vector pk, where pk is the gradient of the cost function C(d) evaluated at Dk. Given that C(d)is convex, it must lie above its tangent hyperplane at that point, which implies that
(28)
For every admissible demand vector d.
By subtracting Eq. 27 from Eq. 28, we obtain
(29)
Which leads to
(30)
And consequently, the optimality gap can be expressed as
(31)
In the present study, the algorithm was executed for a fixed number of 24 iterations, and the optimality gap was used solely as a diagnostic indicator rather than a stopping criterion. Future extensions could instead adopt a convergence rule that terminates iterations once the gap falls below a predetermined threshold or a specified proportion of the direct generation cost C(Dk).
Figure 2. Grid structure.
The smart grid layout is illustrated in Figure 2. This system provides electricity to eight households, which together operate 16 appliances. All loads are linked to the grid operator via a single shared transmission line. Without loss of generality, it is assumed that power is supplied entirely by one distributed generator (DG) unit serving all connected loads. As the only energy source is this single dispatchable generator and no renewable resources are present to influence costs, the marginal generation cost remains constant across all hours. In addition, technical power quality constraints, such as voltage and frequency stability, are excluded from this unit commitment formulation, with the analysis focusing solely on economic dispatch.
In this study, the generator is considered to be jointly owned by all participating consumers. Consequently, the operator functions purely as a coordinator without pursuing any profit. Each customer is responsible only for paying the actual operating cost of the generator, calculated by multiplying their individual consumption profile by the price signal issued by the coordinator. Each household transmits only its energy bid to the coordinator, and no household has any information about its neighbors’ consumption patterns.
Each household reacts to the day-ahead price signal by submitting the total energy consumption schedule for all controllable devices within its premises (specifically EVs and EWHs). As noted earlier, the loads eligible for bidding include both shiftable and thermally controlled appliances (TCA). To limit the scope of the analysis, electric vehicles (EVs) were chosen to represent the shiftable loads, while electric water heaters (EWHs) were selected to represent the TCA loads. Therefore, in this work, each household adjusts its device schedules in response to price signals to optimize overall performance.
Figure 3. EWH’s response to the broadcast price
In this hypothetical setup, where generation costs remain identical across all time periods due to the absence of renewable energy sources, and only demand-responsive loads are present, the optimal aggregate demand curve and the corresponding price signal would ideally be constant (flat) throughout the entire scheduling horizon. Nevertheless, the existing framework can be readily extended to incorporate non-interruptible generation from renewable energy resources.
As outlined in the preceding section, the simulation considers only two categories of controllable appliances. It was also noted that loads can be broadly classified into three groups: (1) non-shiftable, (2) shiftable, and (3) thermally controlled appliances (TCAs). Non-shiftable loads remain unresponsive to price variations, maintaining a fixed consumption pattern. To streamline the analysis and focus on the paper’s core contributions, non-shiftable loads have been excluded from the modeled load profiles.
This section examines the behavior of a single electric vehicle (EV) and a single electric water heater (EWH). It demonstrates how these devices, acting in their own interest, seek to maximize their individual benefits by reacting to the broadcast price signal.
Figure 4. EV response to broadcasted price.
Figure 3 illustrates how the electric water heater (EWH) reacts to the price signal broadcast by the coordinator during one iteration of the optimization process. Using the received price information together with a forecast of the user’s hot water demand, the EWH determines its optimal (self-interested) operating schedule. The resulting energy consumption decision variable is then submitted to the aggregator as the EWH’s energy bid.
The price signal appears as a solid black line in the bottom panel of the figure. Simultaneously, the EWH maintains an estimate of the user’s expected energy withdrawal. In this study, this forecast is assumed to be perfect (deterministic rather than stochastic) and is derived from historical data analysis, potentially supported by machine learning techniques. This prediction is depicted with dotted black lines in the central panel of the figure.
The primary outcomes from solving the optimization problem are presented as follows: the top panel shows the actual water-temperature trajectory inside the heater, calculated based on the demand forecast. The pink dotted line in the middle panel indicates the planned energy input to the EWH. This quantity constitutes the decision variable that the EWH forwards to the coordinator at the end of each optimization round. A more comprehensive explanation of the underlying EWH optimization model can be found in Ref. [5].
Figure 5. Initial price and demand profile.
Figure 6. Final price and demand profile.
Figure 4 depicts the electric vehicle’s reaction to the price signal issued by the coordinator. The gray bars represent the maximum energy the EV can absorb in each hour. Periods with zero availability indicate that the vehicle is in use and therefore unavailable for charging. The blue bars illustrate the actual energy-absorption schedule determined by the optimization procedure.
As with the EWH, the energy input decision variable for the EV (shown by the blue bars) is communicated to the coordinator as the vehicle’s energy bid. For instance, in this specific case, the EV charged at its maximum rate during hours 1, 4, 21, and 24, while operating at one-third of its full capacity during hour 5.
In the scenario examined here—where the marginal generation cost remains constant across all hours due to the absence of renewable energy sources and where no fixed (non-responsive) loads are present—the theoretically optimal outcome is a perfectly flat aggregate load profile accompanied by a constant price signal. In other words, the Peak-to-Average Ratio (PAR) would equal one.
To assess the effectiveness of the Dantzig-Wolfe (DW) algorithm, it is therefore necessary to examine the extent to which the obtained aggregate load curve and the resulting price profile deviate from these ideal flat lines.
Figures 5 and 6 present the price signal and the corresponding aggregate load profile at the initial (step 0) and final iterations, respectively. At each step, every appliance independently solves its local self-interested optimization problem based on the received price signal and submits its resulting scheduled energy consumption as an energy bid to the coordinator.
As shown, the initial demand is concentrated in a few specific hours (consistent with the fact that only EVs and EWHs are modeled in this study). Consequently, the price calculated from the anticipated marginal generation cost—derived directly from the reported energy consumption—no longer accurately reflects the true marginal cost of production. This discrepancy arises because the price-responsive devices (PRDs) actively adjust their consumption schedules to maximize their individual benefits.
Figure 7. PAR and STD for price and aggregate demand.
This clustering of demand leads to unexpectedly high generation costs during hours that were initially projected to have low usage. As observed, the starting price signal reaches elevated levels between 3 AM and 6 AM. This prompts reduced consumption during those costly intervals. However, a peak demand of 54 kW still occurs, driving up overall expenses.
Such behavior indicates that if the coordinator were to compute prices solely based on the immediate forecasted consumption, the process would fail to converge and would instead exhibit an unstable oscillating (flip-flop) pattern.
This is precisely where the strength of the Dantzig-Wolfe (DW) algorithm becomes evident. The DW method identifies an improved solution by constructing a convex combination of all previously submitted bids at every iteration. For instance, during the third iteration, it interpolates between the first and second bids to produce a master problem solution that is superior to both prior steps. The same principle applies to subsequent iterations: at the nth step, the algorithm has information from the n−1 earlier bids, enabling it to generate a solution that is at least as good as—or better than—the previous one. This iterative procedure continues until further improvements cease.
Figure 6 displays the stabilized price signal and the aggregate demand profile after the iterative process completes. The Peak-to-Average Ratio (PAR) decreases substantially, and the maximum load drops from 54 kW to 26 kW. It is important to emphasize that every load in this simulation is price-responsive. In a more realistic setting that includes a mix of price-responsive and non-responsive loads, the achievable reduction in PAR would be smaller than when all loads are price-responsive. As illustrated in Figure 6, the PAR associated with the price signal improves markedly, falling from 4.7 to 2.6.
As previously noted, at every iteration, the coordinator broadcasts the price signal to all appliances in each household. Each device then independently maximizes its own benefit by solving a local optimization problem using the received price. The process stabilizes when, upon receiving the updated price signal, no appliance modifies its submitted bid. This condition indicates that the system has attained the global optimum, or equivalently, a Nash equilibrium.
Figure 5 illustrates the advancement of the Dantzig-Wolfe (DW) procedure over successive iterations. In the early stages, both the price signal and the aggregate demand exhibit large fluctuations. At this point, the Peak-to-Average Ratio (PAR) for both price and demand is approximately 4.7. As iterations continue, both the PAR and the standard deviation (STD) decline steadily. By iteration 5 and beyond, the PAR drops to roughly 1.1.
Nevertheless, this remaining variation is still sufficient to prompt loads to adjust their consumption patterns. By iteration 15, the appliances stop altering their responses to the price signal. In other words, the algorithm has reached a state in which no device has any incentive to revise its scheduled consumption plan — the very definition of a Nash equilibrium. This outcome fulfills the method’s primary objective: to generate price signals and energy bids for each user so that no participant wishes to deviate from its chosen behavior. The algorithm’s optimality properties are examined in the following section.
Figure 7 displays the generation cost (in red) and the total user payments (in black) throughout the iterative process. User payments are computed as the sum over all intervals of the product of the electricity price and the aggregate consumption in that interval. The generation cost is determined according to Eq. 20.
As shown in Figure 7, both generation cost and user payments start at high values. As the iterative negotiation proceeds, both quantities decrease progressively. When the price signal is issued, and none of the appliances revise their consumption schedules, the system reaches a Nash equilibrium (in game-theoretic terms).
The optimality gap, defined by Eq. 28, is plotted in blue in Figure 7. This gap quantifies the difference between the best possible objective value and the best value discovered so far. As the algorithm advances, it continuously refines these quantities. In the later stages of the process (iteration 15 in this simulation), the gap stabilizes and shows no further reduction, indicating that the optimal point has been reached. This coincides with the earlier observation that the Nash equilibrium is attained at iteration 15.
With the growing penetration of renewable energy sources and distributed generation in modern power systems, the need for effective coordination mechanisms to balance generation and consumption has become more pressing. One promising approach to advancing the objectives of the smart grid is to establish market-based mechanisms for these services. Accordingly, this paper introduces a market-oriented coordination algorithm.
Coordinating price-responsive devices (PRDs) presents significant challenges, primarily because these devices can rapidly adjust their consumption in response to very small price changes, compounded by the lack of detailed information about each device’s individual preferences. Attempting to collect such preference data would compromise user privacy.
To address these difficulties, the paper first formulates a centralized optimization problem that minimizes generation costs and PRD payments simultaneously. Solving this joint problem would guarantee an optimal outcome (or Nash equilibrium). However, tackling such a large-scale problem directly is impractical due to limited knowledge of end-user behavior. Moreover, even if complete information were available, solving the resulting massive optimization problem would be computationally prohibitive.
Therefore, an algorithm is required that can handle this complex problem without requiring access to private user information. The proposed solution achieves this by decomposing the overall problem into a master problem (solved centrally by the operator) and multiple subproblems (solved locally by individual appliances). This decomposition eliminates the need for the operator to know each appliance’s internal preferences; instead, appliances communicate their intended energy usage through bids.
Furthermore, the distributed nature of the optimization enables rapid execution at each iteration. The specific formulation of the algorithm also ensures convergence within a modest number of iterations. Because subproblems are solved in parallel, the method scales efficiently and can coordinate thousands of devices without sacrificing performance.
Given the advantages of a distributed, price-based coordination framework, an algorithm grounded in the Dantzig-Wolfe decomposition was developed. As demonstrated in the results section, the proposed approach converges to the optimal solution in only 15 iterations while simultaneously reducing costs for both the distributed generation unit and the PRDs, reaching a balanced state in which no participant has an incentive to deviate.
In this study, a simplified unit commitment problem involving a single generator was considered. Future work will extend the model to a more comprehensive unit commitment formulation that incorporates generation and transmission constraints. Given the efficiency and computational speed of the proposed algorithm, it has strong potential to effectively and optimally solve large-scale unit commitment problems that include numerous price-responsive devices.
None
None
This research was partly funded by grants from the Ulupono Initiative and Blue Planet Foundation.
None
Open Access The author(s) retain copyright. This article is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. It may be shared and adapted for non-commercial purposes with appropriate attribution, an indication of changes, and distribution of adaptations under the same license. Third-party material may be subject to separate terms identified in its credit line. View the license at https://creativecommons.org/licenses/by-nc-sa/4.0/.
Institute of Smart Energy Systems Press
