4
$\begingroup$

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).

$\endgroup$
2
  • 1
    $\begingroup$ 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? $\endgroup$ – prubin Apr 26 at 16:20
  • $\begingroup$ 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 $\endgroup$ – PeterBe Apr 28 at 6:52
9
$\begingroup$

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}

$\endgroup$
34
  • 1
    $\begingroup$ +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$. $\endgroup$ – RobPratt Apr 26 at 12:56
  • 1
    $\begingroup$ 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$ $\endgroup$ – Kuifje Apr 28 at 8:05
  • 1
    $\begingroup$ Regarding the intuition of $P \implies Q$, see math.stackexchange.com/questions/2011842/…. 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. $\endgroup$ – RobPratt Apr 28 at 13:51
  • 1
    $\begingroup$ 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$. $\endgroup$ – Kuifje Apr 29 at 9:30
  • 1
    $\begingroup$ 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)$. $\endgroup$ – Kuifje Apr 30 at 8:53

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.