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 Answers 4

Reset to default
5
$\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$
13
  • 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$ Commented Dec 10, 2018 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$ Commented Dec 10, 2018 at 10:10
  • $\begingroup$ that indeed seemed to be the case. Smart observation regarding the patterns! $\endgroup$ Commented Dec 10, 2018 at 14:52
  • $\begingroup$ Not so smart. This is a fairly standard and often used approach. Most modelers are well aware of this. $\endgroup$ Commented Dec 10, 2018 at 19:53
  • 1
    $\begingroup$ The first decision is at t=0, but there are historic values before that play a role. $\endgroup$ Commented Jan 13 at 11:09
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$
4
  • $\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$ Commented Dec 7, 2018 at 13:28
  • $\begingroup$ @Riley you are right, I have corrected the errors. $\endgroup$ Commented Dec 7, 2018 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$ Commented Dec 10, 2018 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$ Commented Dec 10, 2018 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$
1
  • $\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$ Commented Nov 26, 2018 at 17:26

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.