5

I have a follow up question to another question of mine How to set a limit for a switch to 0 of a variable about counting the number of switches to 0 of one decision variable. Now I would like to ask the same question for two combined decision variables. So basically I have the decision variable x(t) and another decision variable y(t). The both quantify the heating output of a heating device for two different thermal storage systems for every timeslot t in [1,...,288]. It should be avoided that the heating device is switched on and off frequently thus I want to set a limit for the switching.

The rule in pseudocode looks like this:

if (x(t-1)>0 AND x(t)=0 AND y(t)=0) OR if (y(t-1)>0 AND y(t)=0 AND x(t)=0) 
then increase count by 1
Constraint: count <= limit

Both variables x(t) and y(t) are continious variables with the boundaries [0,1]. It should also be noted that x(t) and y(t) can't be greater 0 simultaneously (this would mean that the heating device would have heated up 2 storages at the same time which is not possible). For this I just use 2 constraints with binary auxilliary variable h(t)

x(t)<= h(t)
y(t)<= (1- h(t))
with h(t) in {0,1}

Any idea how I can derive constraints for something like this? Next to the pure answer I would also appreciate some general advices as how to approach questions like this (if there is a more or less general way of doing this).

PeterBe
  • 1,632
  • 2
  • 15
  • 30
  • 1
    Using your pseudocode, if $x(t-1)=1$ and $y(t)=1$ (so that one unit switches off at the same time the other switches on), the count is not incremented. Is that intentional? – prubin Apr 26 '21 at 16:20
  • Thanks prubin for your comment. Yes this is intentional. Basically - as mentioned in my description - we only have 1 heating unit that servers 2 storage systems. Switching between the 2 systems is not a problem if the device keeps running – PeterBe Apr 28 '21 at 06:52

1 Answers1

10

Again, you need to introduce binaries:

  • $\delta_t$ takes values $1$ if and only if the device is switched off at time $t$
  • $\alpha_t$ is the binary associated with variable $x_t$
  • $\beta_t$ is the binary associated with variable $y_t$

The condition can be written in conjunctive normal form as follows:

$$ (\alpha_{t-1}\wedge \lnot \alpha_{t} \wedge \lnot \beta_{t}) \vee (\beta_{t-1}\wedge \lnot \beta_{t} \wedge \lnot \alpha_{t}) \implies \delta_t\\ \lnot \left( (\alpha_{t-1}\wedge \lnot \alpha_{t} \wedge \lnot \beta_{t}) \vee (\beta_{t-1}\wedge \lnot \beta_{t} \wedge \lnot \alpha_{t})\right) \vee \delta_t\\ (\lnot \alpha_{t-1}\vee \alpha_{t} \vee \beta_{t}) \wedge (\lnot \beta_{t-1}\vee \beta_{t} \vee \alpha_{t}) \vee \delta_t\\ (\lnot \alpha_{t-1}\vee \alpha_{t} \vee \beta_{t} \vee \delta_t)\wedge (\lnot \beta_{t-1}\vee \beta_{t} \vee \alpha_{t} \vee \delta_t)\\ (1-\alpha_{t-1}+\alpha_t + \beta_t+ \delta_t \ge 1) \wedge (1-\beta_{t-1}+\beta_t + \alpha_t+ \delta_t \ge 1) $$

And since $x_t$ and $y_t$ cannot simultaneously be positive, the constraints are \begin{align} \alpha_{t-1} &\le \alpha_t + \beta_t+ \delta_t \quad &\forall t \tag{1}\\ \beta_{t-1} &\le \beta_t + \alpha_t+ \delta_t \quad &\forall t \tag{2}\\ \sum_t \delta_t &\le \ell \tag{3} \\ \alpha_t + \beta_t &\le 1 \quad &\forall t \tag{4} \\ x_t &\le M \alpha_t \quad &\forall t \tag{5} \\ y_t &\le M \beta_t \quad &\forall t \tag{6} \\ \end{align}

Kuifje
  • 13,324
  • 1
  • 23
  • 56
  • 1
    +1 for CNF. Because of the fourth constraint, you can strengthen the formulation by merging the first two constraints as $\alpha_{t-1}+\beta_{t-1}\le\alpha_t+\beta_t+\delta_t$. – RobPratt Apr 26 '21 at 12:56
  • Thanks a lot Kuifje and RobPratt for your answer. @Kuifje: I do not understand the tranission from the 1. line to the 2. line in your conjunctive normal form and I do not understand the transission from the 4. line to the 5. line. – PeterBe Apr 28 '21 at 06:49
  • @RobPratt: I do not understand how and why you strenghten the constraints? It this necessary? Otherwise I would not do it – PeterBe Apr 28 '21 at 06:49
  • @PeterBe you can check that the truth table of the implication $A \Rightarrow B$ is the same as $\lnot A \vee B$. And for the last line, if a logical statement is true then its binary variable is $\ge 1$. – Kuifje Apr 28 '21 at 06:58
  • Thanks Kuifje for your comment and effort. Regarding the Line 1 to 2: I do not understand why "A-->B" is the same as "not A or B"? Let's say A: "The sun is shining" and B: "I go to the sea". So "A-->B" means, if the sun is shining, I go to the sea. How would you read "not A or B"? Either the sun is not shining or I go to the sea? This does not make much sense according to my point of view. Regarding Line 4 to 5: Why and how do you change they AND-symbol to an OR-symbol in the middle. And why do you add two times the 1 in each bracket? Regarding the comment: it's okay. I gave an answer – PeterBe Apr 28 '21 at 07:12
  • Please refer to conditional operators. For the last line it was a typo, thanks for noting. – Kuifje Apr 28 '21 at 07:26
  • Thanks Kuifje. Regarding Line 1 to 2: I read your link and I understand the truth tables. However, I do not comprehend the transission logically. Let's take my example again. A: "The sun is shining" and B: "I go to the sea". How would you read "not A or B" and why is this logically (intuitively) equivalent to "A-->B"? Would you mind elaborating a little bit on that? Regarding the last line: I also had a second question in my last comment "why do you add two times the 1 in each bracket?". The right >=1 is because the logical bracket should be true. But where does the left 1 come from – PeterBe Apr 28 '21 at 07:54
  • 1
    To be honest I am not really sure there is an intuition behind the equivalence of the two truth tables. Maybe @RobPratt can give you more insight on this intuition? The left $1$ comes from the fact that $\lnot \alpha$ is equivalent to $1-\alpha$. And also, I would rather let Rob answer the part about his strengthened constraints but a short answer is 1) it is not necessary, it will only potentially speed up the computation time 2) it is derived from the fact that $\alpha_{t-1}+\beta_{t-1} \le 1$ – Kuifje Apr 28 '21 at 08:05
  • 2
    Regarding the intuition of $P \implies Q$, see https://math.stackexchange.com/questions/2011842/without-truth-tables-how-can-you-intuit-that-p-implies-q-equiv-lnot-p. Regarding the strengthening, it is not necessary but when you can simultaneously shrink and strengthen a formulation, it is almost always a good idea to do so: less memory, faster LP solves, less branching, etc. – RobPratt Apr 28 '21 at 13:51
  • Thanks RobPratt for your answer. I still do not understand how you merge the constraints. Would you mind elaborating a little bit more on that? Your merged constraint is equal ot the first constraint of Kuifje except that you add 'Beta (t-1)' additionally to the left side. Why are you allowed to do that? – PeterBe Apr 28 '21 at 16:06
  • 1
    @PeterBe It is a "clique lifting": if $x_i$ is binary and $x_i + \sum_j a_j y_j \le b$ for all $i$ and $\sum_i x_i \le 1$, then you can strengthen to $\sum_i x_i + \sum_j a_j y_j \le b$. – RobPratt Apr 28 '21 at 16:29
  • As a complement to Rob's answer, convince yourself by checking that the constraint holds for the three possible cases $(\alpha_{t-1},\beta_{t-1}) \in { (0,0),(0,1),(1,0)}$ – Kuifje Apr 28 '21 at 16:31
  • Thanks for your comment @RobPratt and Kuifje. I have to admit that I still not not understand it and I have several questions. 1) x (t) is not a binary but a continuous variable. 2) Why is x (i) + sum (alpha (j), y (j)<= b? 3) What is the index i in the sum (x(i))<=1 and why is it <=1? x can be between 0 and 1 for every timeslot. So the sum over all timeslots t is not <=1. Even if x (i) was a binary, the sum over all i would not be <=1. – PeterBe Apr 28 '21 at 16:46
  • Sorry for the confusion. My $x_i$ is a different variable than your $x(t)$. I'll open a separate question and answer it. – RobPratt Apr 28 '21 at 17:24
  • Thanks for your answer and effort RobPratt. I saw you quesiton (and answer) but I still have problems mapping them to my examples. What are the x(i) in my case and where is the constraint that sum of all x(i) <= 1 in my case? I do not have any constraint with a sum (except the limiation constraint numer (3)). – PeterBe Apr 29 '21 at 09:24
  • 1
    You can map as follows: his $x_1$ is your $\alpha_{t-1}$ and his $x_2$ is your $\beta_{t-1}$. So his $\sum_i x_i = x_1+x_2 \le 1$ is your $\alpha_{t-1} + \beta_{t-1} \le 1$. And his $-\sum_j a_j y_j$ is your $\beta_t + \alpha_t + \delta_t$. – Kuifje Apr 29 '21 at 09:30
  • Thanks for the comment Kuifje. Why is his - sum (a(j)*y(j)) my beta (t) + alpha (t) + delta (t)? – PeterBe Apr 29 '21 at 10:00
  • Any comments to my last comment? I'd highly appreciate every further comment. – PeterBe Apr 30 '21 at 06:28
  • Rewrite the constraint like this $\alpha_{t-1} +(-\alpha_t - \beta_t- \delta_t) \le 0 $, this way you can identify it to $x_1 + (a_1y_1+a_2y_2 +a_3y_3) \le b $. And btw, if you are happy with the answer to the initial question, feel free to accept the answer ;) – Kuifje Apr 30 '21 at 07:24
  • Do I still need the 3 constraints when using the reduction approach from RobPratt (constraint 1,2 and 4) or is just the one equation enough posted by RobPratt "αt−1+βt−1≤αt+βt+δt"? – PeterBe Apr 30 '21 at 08:23
  • I accepted and upvoted your answer Kuifje. Thanks for your effort. – PeterBe Apr 30 '21 at 08:24
  • 1
    No problem. You can use RobPratt's constraint without the initial ones.But you do need to keep constraint $(4)$. Just omit $(1)$ and $(2)$. – Kuifje Apr 30 '21 at 08:53
  • I just found a small mistake. You write that the equations should be valid for all t However when using a difference equation Beta(t-1) then you can't use it for t=1 as Beta(1-1) = Beta(0) is undefined becaue t begins with 1 and not with 0. – PeterBe May 12 '21 at 07:28
  • And I have another question to your suggsted equations 5 and 6. Why do I need the Big-M here and can I not just get rid of it? – PeterBe May 12 '21 at 07:57
  • @Kuifje: Any comments to my last 2 comments and questions? I'd highly appreciate every further comment from you. – PeterBe May 14 '21 at 07:15
  • You can initialize $\beta_0$ with the correct value. You need the big-M constraints, in order to link the continuous and binary variables. – Kuifje May 14 '21 at 08:21
  • Thanks Kuifje for your answer. Here in this quesiton https://or.stackexchange.com/questions/6127/how-to-set-a-limit-for-a-switch-to-0-of-a-variable you do not use the big-M to link the continuous and the binary variable (see your EDIT). Why is this case different? – PeterBe May 14 '21 at 08:32
  • And I still generally do not understand why I need the big-M here. Why do I need it for linking the continuous and binary variables? If alpha has the value 1 then x can have all the values up to 1 and if alpha has the value 0, x will be 0. So why do I need to multiply a big-M here? – PeterBe May 14 '21 at 08:36
  • In this case $M:=1$ – Kuifje May 14 '21 at 08:42
  • Ah okay. Thanks Kuifje. I still have a problem understanding the linking that I wrote in the other question https://or.stackexchange.com/questions/6127/how-to-set-a-limit-for-a-switch-to-0-of-a-variable – PeterBe May 14 '21 at 08:54
  • @Kuifje: Are you sure that the linking of the binary and the continous variable is correct? I somehow doubt it. When x(t) has the value 0 then alpha (t) can still take the value 1 as far as I see it by using your suggested equations. Or is there anything that I miss? What probibits alpha(t) to the the value 1 if x(t) has the value 0? – PeterBe May 18 '21 at 09:15
  • Yes, same as in your other question, you might want to enfore $x_t=0 ; \Rightarrow ; \alpha_t = 0$ to prevent $\alpha_t$ from taking value $1$. – Kuifje May 18 '21 at 09:25
  • @Kuifje: Thanks for your answer. But how can I create equations that ensure that if x (t) =0, alpha (t) =0? Your suggested equations do not do that. – PeterBe May 18 '21 at 17:39
  • Indeed, you will have to refer to the other question you posted, once it gets an answer. – Kuifje May 18 '21 at 17:40