# Can I apply decomposition methods for this scheduling problem

I have a centralized optimization problem for a residential area in the context of a smart grid and load flexibility. So let's say I have 10 buildings and each of them has an electric heating device. Further each building has a photovoltaic PV system that generates renewable energy. Now the goal of the centralized optimization problem is to schedule the heating activities of all buildings such that the overall usage of the total reneable energy (sum of all the PV generation of all buildings) is maximized.

Basically every building has 24 decision variables (one for each hour): x_1, ..., x_24 The quantiy the (continious) power consumption of the electric heating device in each hour. Of course we also have some thermal constraints for the room temperature such that it is not possible to heat with full power during all hours. Moreover, each building has a PV generation that is given exogeneously meaning that this is a parameter: PV_1, ..., PV_24

So the goal of the centralized optimizer is to choose x_1, ..., x_24 for all 10 buildings such that the PV self consumption rate, is maximized. The total electrical power P_total for the residential area for one timeslot is just the sum of the x_1s, ..., x_24s for all buildings. The same is valid for the total PV generation PV_total of the residential area. Now we want to minimize the sum of PV_total - P_total over all 24 hours of the day (this maximizes the self-consumption rate of PV).

I hope you have understood the basics of this problem (if not I can give you more information). My fundamental question now is, whether I can use one of the following decomposition methods to transform this centralized large optimization problem into distributed smaller problems that could be solved by the buildings themselves. Basically I would like to know if I can use one of these methods:

Dual decomposition

Dantzig-Wolfe decomposition

Benders decomposition

I'd appreciate every comment.

Update: Here is the complete optimization problem x_t_b and y_t_b are the decision variables for all timeslots t and all buildings b. The objective is to minimize the surplus power in the residential area. The surplus power is calculated by subtracting the total electrical deamand of the area from the total PV geneartion. But only the positive surplus power should be minimized. I use the Big-M approach to incorporate this into the model with the two big M parameters and an auxillary binary variable h^positive. I have two thermal storage systems (modelled by T^UFH and V^DHWuse) which have upper and lower limits. x_t_b is the decision variable for heating up the T^UFH_b and y_t_b the decision variables for heating up the V^DHWuse_b. Only on of them can be heated up at one time slot. To model this I use a binary auxilliary variable h^Aux for each building and each time slot. The total demand P^total comprises the electrical demand of the heat pumps and the inflexible demand P^Demand that is a parameter.

• Must the values of $x_1,\dots,x_{24}$ agree across buildings? – RobPratt Jun 17 at 20:38
• Thanks RobPratt for your comment. No, each building can have different x_1, ..., x_24 values and each building has different PV_1, ..., PV_24 values. – PeterBe Jun 17 at 20:44
• Then what prevents solving each building separately? – RobPratt Jun 17 at 20:45
• Your description sounds like the objective function is a sum across buildings and there are no linking constraints across buildings. So solving each building separately is equivalent to solving them together. – RobPratt Jun 17 at 20:52
• Those sums sound more like definitions for the purpose of describing the objective rather than true constraints. I think you are more likely to get useful responses if you write out a complete formulation. – RobPratt Jun 17 at 21:08

Thank you for adding the formulation. Assuming $$\Delta t$$ is a nonnegative coefficient, you can simplify the formulation by omitting $$h_t^\text{positive}$$, $$P_t^{\text{Surplus}^-}$$, and the associated constraints. Instead, you need only impose $$P_t^{\text{Surplus}^+} \ge P_t^\text{PVtotal} - P_t^\text{total} \quad \text{for all t} \tag 1$$ to get the desired behavior of minimizing the positive surplus.

It looks like you still need some constraints to enforce the relationships between $$T$$ and $$V$$ and the rest of the model. Currently, $$T$$ and $$V$$ appear by themselves.

If you substitute the expressions for $$P_t^\text{PVtotal}$$ and $$P_t^\text{total}$$ (or use implicit/defined variables) and treat $$(1)$$ as the linking/complicating constraints, the rest of the problem decomposes by building, so you might benefit from applying Dantzig-Wolfe decomposition with one block per building.

By substitution, I meant replacing $$(1)$$ with $$P_t^{\text{Surplus}^+} \ge \sum_{b=1}^B P_{t,b}^\text{PV} - \sum_{b=1}^B \left((x_{t,b}+y_{t,b})P_b^\text{HPmax}+P_{t,b}^\text{Demand}\right) \quad \text{for all t} \tag{1'}$$
To treat $$(1)$$ or $$(1')$$ as linking constraints, some automated Dantzig-Wolfe implementations allow you to specify the block-angular structure by using constraint attributes. For example, see this Getting Started example from the SAS documentation.