Binary variables in time series: integer linear programming

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.

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.

• 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. – Riley Dec 10 '18 at 9:52
• 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) – Erwin Kalvelagen Dec 10 '18 at 10:10
• that indeed seemed to be the case. Smart observation regarding the patterns! – Riley Dec 10 '18 at 14:52
• Not so smart. This is a fairly standard and often used approach. Most modelers are well aware of this. – Erwin Kalvelagen Dec 10 '18 at 19:53
• 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?) – Riley Dec 11 '18 at 13:38

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$$

• 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. – Riley Dec 7 '18 at 13:28
• @Riley you are right, I have corrected the errors. – LinAlg Dec 7 '18 at 14:28
• 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)$ – Riley Dec 10 '18 at 13:07
• @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 – LinAlg Dec 10 '18 at 15:40

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.

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.

• 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. – LinAlg Nov 26 '18 at 17:26