2
$\begingroup$

I'm working on a problem and I can't seem to find an easy solution to it. It's about an optimization problem, concerning a time series.

I have a binary variable $\alpha_t$ for $t \in [0, 24[$. I also have an extra constraint, which states that $$\sum_{t=0}^{23} \alpha_t \geq 14.$$ The problem is that I want to add an extra constraint that if a certain $\alpha_t = 1$, then either $$\alpha_{t-1} = \alpha_{t+1} = 1$$ or $$\alpha_{t-1} = \alpha_{t-2} = 1$$ or $$\alpha_{t+1} = \alpha_{t+2} = 1, $$ i.e. at least 3 consecutive times $\alpha$ needs to be 1. It can be 4 times, it can be 5, but it has to be at least 3 times.

The most intuitive idea is probably this: $$\alpha_t = 1 \Rightarrow \alpha_t + \alpha_{t+1} + \alpha_{t + 2} = 3,$$ but from a certain $t$, this will result that all $\alpha_t = 1$.

I also tried big M constraints, but for larger consecutive times ( $\geq 3)$, this becomes almost impossible to write down/implement.

$\endgroup$
4
$\begingroup$

One simple way to enforce a run length of at least three, is to forbid patterns 010 and 0110. This can be modeled as:

$$ -x_t + x_{t+1} - x_{t+2} \le 0 $$

and

$$ -x_t + x_{t+1} + x_{t+2} - x_{t+3} \le 1 $$

A little bit of thought is needed to decide what to do at the borders, especially the first time period.

A different approach is detailed here.

$\endgroup$
  • 1
    $\begingroup$ I thought about that too, but what about patterns like 110, 101, 011, etc? I want to generalize the method and I feel like this would get way out of hand way too soon for larger consecutive times. $\endgroup$ – Riley Dec 10 '18 at 9:52
  • $\begingroup$ I don't think you fully understand what I suggested. You really only need to worry about 010 and 0110. (With some more thought needed near the boundaries of the planning period) $\endgroup$ – Erwin Kalvelagen Dec 10 '18 at 10:10
  • $\begingroup$ that indeed seemed to be the case. Smart observation regarding the patterns! $\endgroup$ – Riley Dec 10 '18 at 14:52
  • $\begingroup$ Not so smart. This is a fairly standard and often used approach. Most modelers are well aware of this. $\endgroup$ – Erwin Kalvelagen Dec 10 '18 at 19:53
  • $\begingroup$ Apologies, novice modeler here. Small follow-up question: is there then also a way to formulate the constraint, that if one $x_t=1$ in an interval $[a, b]$, then all $x_t$ in $[a, b] $ have to be equal to 1? (Without using Big-$M$ constraints?) $\endgroup$ – Riley Dec 11 '18 at 13:38
1
$\begingroup$

One method is to let $x_t$ denote the starting indices and $y_t$ denote the ending indices of the sequences of ones. For example, if $x=(0,1,0,0,0,1,0)$ and $y=(0,0,0,1,0,0,1)$, the sequence is $\alpha=(0,1,1,1,0,1,1)$. You get the following constraints:

  1. number of starting indices equals number of ending indices: $$\sum_t x_t = \sum_t y_t$$

  2. cannot end a sequence unless it was started at least 3 periods prior: $$y_i \leq \sum_{t=1}^{i-2}x_t-y_t \quad \forall i$$

  3. cannot start a new sequence before the previous one is closed: $$x_i \leq 1- \sum_{t=1}^{i-1}(x_t-y_t) \quad \forall i$$

  4. relating $\alpha$ to $x,y$: $$\alpha_i = \sum_{t=1}^{i}x_t - \sum_{t=1}^{i-1}y_t \quad \forall i$$

$\endgroup$
  • $\begingroup$ I think there's an error in your reasoning: when I implement this, I get only one $x_t = 1$, which results in some $\alpha = (0, 0, \ldots, 0, 1, 1, \ldots , 1)$. In every case I tried (also by forcing some values of variables), it's as if there's a value of 1 in $\alpha$, so must be everything else after that. $\endgroup$ – Riley Dec 7 '18 at 13:28
  • $\begingroup$ @Riley you are right, I have corrected the errors. $\endgroup$ – LinAlg Dec 7 '18 at 14:28
  • $\begingroup$ Unless I'm mistaken, this doesn't necessarily guarantee consecutiveness. Formulation nr 2 doesn't rule out the possibility of a 'zero gap'. Example: $\alpha = (1,1,1,0,1), x=(1,0,0,0,1), y=(0,0,1,0,1)$ $\endgroup$ – Riley Dec 10 '18 at 13:07
  • $\begingroup$ @Riley the second constraint includes $y_5 \leq x_1+x_2+x_3 - y_1 - y_2 - y_3$, which in your example is $y_5 \leq 0$, so $y_5=1$ is infeasible $\endgroup$ – LinAlg Dec 10 '18 at 15:40
1
$\begingroup$

Reading your question I think that you want

$$\alpha_t = 1 \implies \alpha_{t+1} + \alpha_{t+2} = 2 \vee \alpha_{t-1} + \alpha_{t+1} = 2 \vee \alpha_{t-2} + \alpha_{t-1} = 2$$

not

$$\alpha_t = 1 \implies \alpha_t + \alpha_{t+1} + \alpha_{t + 2} = 3, ~ \forall t\in [0, n-2]$$

or, equivalently,

$$\alpha_t = 1 \implies \alpha_{t+1} + \alpha_{t + 2} = 2, ~ \forall t\in [0, n-2]$$

In this case, the answer should be

$$ \alpha_t \implies \alpha_{t+1} \wedge \alpha_{t + 2}, ~ \forall t\in [0, n-2]$$

$$ \neg\alpha_t \vee (\alpha_{t+1} \wedge \alpha_{t + 2}), ~ \forall t\in [0, n-2]$$

$$ (\neg\alpha_t \vee \alpha_{t+1}) \wedge (\neg\alpha_t \vee \alpha_{t + 2}), ~ \forall t\in [0, n-2]$$

rewriting this sentence in binary variables, the constraints are

$$ \begin{align} (1-\alpha_t) + \alpha_{t+1} \geq 1, ~ \forall t\in [0, n-2]\\ (1-\alpha_t) + \alpha_{t+2} \geq 1, ~ \forall t\in [0, n-2] \end{align} $$

Another case

OK, consider this logical sentence

$$\alpha_t \implies (\alpha_{t+1} \wedge \alpha_{t+2}) \vee (\alpha_{t-1} \wedge \alpha_{t+1}) \vee (\alpha_{t-2} \wedge \alpha_{t-1})$$

$$\neg\alpha_t \vee (\alpha_{t+1} \wedge \alpha_{t+2}) \vee (\alpha_{t-1} \wedge \alpha_{t+1}) \vee (\alpha_{t-2} \wedge \alpha_{t-1})$$

After some operations ...

$$(\neg\alpha_t \vee \alpha_{t-2} \vee \alpha_{t+1}) \wedge (\neg\alpha_t \vee \alpha_{t-1} \vee \alpha_{t+1}) \wedge (\neg\alpha_t \vee \alpha_{t-1} \vee \alpha_{t+2})$$

the constraints for $t\in [2, n-2]$ are

$$ \begin{align} (1-\alpha_t) + \alpha_{t-2} + \alpha_{t+1} \geq 1 \\ (1-\alpha_t) + \alpha_{t-1} + \alpha_{t+1} \geq 1 \\ (1-\alpha_t) + \alpha_{t-1} + \alpha_{t+2} \geq 1 \end{align} $$

You need to fix the cases $t=0, t=1, t=n-1, t=n$ using the same idea. For $t\in\{0,n\}$ you can use the first set of equations presented in this text.

$$ \begin{align} (1-\alpha_0) + \alpha_{1} \geq 1 \\ (1-\alpha_0) + \alpha_{2} \geq 1 \\ (1-\alpha_n) + \alpha_{n-1} \geq 1 \\ (1-\alpha_n) + \alpha_{n-2} \geq 1 \end{align} $$

For $t\in\{1,n-1\}$

$$\alpha_1 \implies (\alpha_{2} \wedge \alpha_{3}) \vee (\alpha_{0} \wedge \alpha_{2})$$

$$\neg\alpha_1 \vee (\alpha_{2} \wedge \alpha_{3}) \vee (\alpha_{0} \wedge \alpha_{2}) $$

$$(\neg\alpha_1 \vee \alpha_{0} \vee \alpha_{3}) \wedge (\neg\alpha_{1} \wedge \alpha_{2}) $$

and

$$\alpha_{n-1} \implies (\alpha_{n-2} \wedge \alpha_{n-3}) \vee (\alpha_{n} \wedge \alpha_{n-2})$$

$$\neg\alpha_{n-1} \vee (\alpha_{n-2} \wedge \alpha_{n-3}) \vee (\alpha_{n} \wedge \alpha_{n-2}) $$

$$(\neg\alpha_{n-1} \vee \alpha_{n} \vee \alpha_{n-3}) \wedge (\neg\alpha_{n-1} \wedge \alpha_{n-2}) $$

resulting in these constraints

$$ \begin{align} (1-\alpha_1) + \alpha_{0} + \alpha_{3}\geq 1 \\ (1-\alpha_1) + \alpha_{2} \geq 1 \\ (1-\alpha_{n-1}) + \alpha_{n} +\alpha_{n-3} \geq 1 \\ (1-\alpha_{n-1}) + \alpha_{n-2} \geq 1 \end{align} $$

finally

$$ \left\{\begin{align} & (1-\alpha_0) + \alpha_{1} \geq 1 & \\ & (1-\alpha_0) + \alpha_{2} \geq 1 & \\ & (1-\alpha_1) + \alpha_{0} + \alpha_{3}\geq 1 & \\ & (1-\alpha_1) + \alpha_{2} \geq 1 & \\ & (1-\alpha_t) + \alpha_{t-2} + \alpha_{t+1} \geq 1, & \forall t\in [2,n-2] \\ & (1-\alpha_t) + \alpha_{t-1} + \alpha_{t+1} \geq 1, & \forall t\in [2,n-2] \\ & (1-\alpha_t) + \alpha_{t-1} + \alpha_{t+2} \geq 1, & \forall t\in [2,n-2] \\ & (1-\alpha_{n-1}) + \alpha_{n} +\alpha_{n-3} \geq 1 & \\ & (1-\alpha_{n-1}) + \alpha_{n-2} \geq 1 & \\ & (1-\alpha_n) + \alpha_{n-1} \geq 1 & \\ & (1-\alpha_n) + \alpha_{n-2} \geq 1 & \end{align}\right. $$

These constraints cover all cases correctly. There is no counterexample.

$\endgroup$
0
$\begingroup$

I think I've got it:

use the reasoning in this post Integer linear programming constraint for maximum number of consecutive ones in a binary sequence. Here, we have to look at the $\alpha_t$ as zero's instead of ones. At this point, you can impose a maximum of consecutive zero's.

If the variable however has a value of one, then you can use big M constraints to set the sum of the next 3, equal to 3.

$\endgroup$
  • $\begingroup$ You want to impose a minimum number of consecutive ones, so that reasoning does not apply. Using big-M is not necessary, see my other answer. $\endgroup$ – LinAlg Nov 26 '18 at 17:26

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.