1
$\begingroup$

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:

ADMM: Alternating methods of multipliers

Dual decomposition

Dantzig-Wolfe decomposition

Benders decomposition

I'd appreciate every comment.

Update: Here is the complete optimization problementer image description here

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.

$\endgroup$
  • 1
    $\begingroup$ Must the values of $x_1,\dots,x_{24}$ agree across buildings? $\endgroup$ – RobPratt Jun 17 at 20:38
  • $\begingroup$ 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. $\endgroup$ – PeterBe Jun 17 at 20:44
  • $\begingroup$ Then what prevents solving each building separately? $\endgroup$ – RobPratt Jun 17 at 20:45
  • 2
    $\begingroup$ 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. $\endgroup$ – RobPratt Jun 17 at 20:52
  • 3
    $\begingroup$ 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. $\endgroup$ – RobPratt Jun 17 at 21:08
5
+50
$\begingroup$

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.


Update to answer your additional questions:

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.

Dantzig-Wolfe decomposition applies when you have a set of linking/complicating constraints whose omission makes the resulting problem much easier. In contrast, Benders decomposition applies when you have a set of linking/complicating variables such that fixing the values of these variables makes the problem much easier. In principle, either decomposition algorithm can be used for any subset you choose, but the best performance is obtained when your problem has some structure where only a small percentage of constraints or variables are complicating. The Dantzig-Wolfe decomposition I suggested seems the most natural for your problem, and it matches your intuition of wanting to solve the buildings separately.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks RobPratt for your answer. I really appreciate your help. I have several additional questions: 1) What do you mean by 'If you substitute the expressions for P^PVtotal_t and P^total_t' 2) How can I treat (1) as the linking constraints? 3) Can I also use Benders decomposition? What are the prerequesits for that? I think I need linking variables? What is the difference between linking variables and linking constraints? PS: Yes you are right. I have some constraints that link the decision variables x and y to T and V. $\endgroup$ – PeterBe Jun 19 at 8:08
  • $\begingroup$ Would anyone mind asking my follow up questions (see commen above)? I'd really appreciate it and I'd be quite thankful. $\endgroup$ – PeterBe Jun 21 at 7:33
  • $\begingroup$ @PeterBe, I added some responses to my answer. $\endgroup$ – RobPratt Jun 21 at 15:43
  • $\begingroup$ Thanks for your answer RobPratt and your effort. As I have no experience whatsovever regarding decomposition I still have some questions. 1) What are 'linking variables'? Maybe you can pinpoint them in my example? 2)Did I understand correctly that basically I can use both Benders and Dantzig-Wolfe decomposition for every mixed integer linear program (but the are not beneficial for every problem) ? 3) What about the dual decomposition method or the ADMM method. Can I also apply them in my case? I'd appreciate further comments. $\endgroup$ – PeterBe Jun 22 at 12:06
  • $\begingroup$ Does anyone have an answer for my last comments? I'd be quite thankful for every comment $\endgroup$ – PeterBe Jun 24 at 9:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.