How do you specify a linear constraint to an integer program where, given a binary variable x over a period of t intervals (x1,x2…xt), you want x to be =1 either never or at least n consecutive times?
Asked
Active
Viewed 108 times
0
-
Welcome to MSE. Please use MathJax. – José Carlos Santos Sep 12 '17 at 11:23
-
It depends on the whole model which constraint satisfy the condition. A condition alone is not enough information. – callculus42 Sep 12 '17 at 13:43
1 Answers
0
You should change the topic of your question since your problem is formulated using binary/integer variables (it is not a linear programming problem).
Given that $n \le t$, we can define auxiliary binary variable $y_j \in \{0,1\}$ for each $j \in \{1,\dots,t-n+1\}$ which takes value one if at least $n$ variables $x_j,\dots,x_{n+j-1}$ take value one. If we want either none or exactly $n$ consecutive variables to take value one then we can add the following constraints to our model: \begin{align} &\sum_{i=j}^{n+j-1} x_i \ge ny_j\ \ \ \ \ \ \ \ \ \ \forall j \in \{1,\dots,t-n+1\}\\ &\sum_{i=1}^{t} x_i \le n\\ &\sum_{j=1}^{t-n+1} y_j \le 1 \end{align}
Let $z_k \in \{0,1\}$ be an auxiliary binary variable which takes value one if exactly $k \in \{n,\dots, t\}$ consecutive $x$ variables take value one. If we want none or at least $n$ consecutive variables to take value one, then it is enough to add the following constraint to the model:
\begin{align} &\sum_{i=j}^{k+j-1} x_i \ge k(y_j+z_k-1)\ \ \ \ \ \ \ \ \ \ \forall k \in \{n,\dots, t\}, \ \forall \, j \in \{1,\dots,t-k+1\}\\ &\sum_{i=1}^{t} x_i \le \sum_{k=n}^{t} kz_k\\ &\sum_{k=n}^{t} z_k \le 1 \end{align}
Note that there may be several other ways to formulate your problem.