5
$\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
10
$\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
  • 2
    $\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$ @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$. $\endgroup$
    – RobPratt
    Apr 28 at 16:29
  • 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

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.