Modeling an On/Off Span

I may be ruining a perfectly good homework problem by posting this. :-)

Occasionally someone needs to incorporate in an integer programming model the notion of something changing state for a predefined span of time. The typical characterization I've seen is as follows:

• we have a sequence of binary variables $x_i\in\{0, 1\}, i\in\{1,\dots,N\}$ that indicate the state of something; and
• if the state changes from 0 to 1, it must remain 1 for exactly $K$ consecutive periods (with a possible exception of we reach the horizon limit $N$ before we see the $K$-th unit value).

For $K=3$, this means the sequence <... 0 1 1 1 0 ...> is valid but <... 0 1 1 0 ...> is invalid (not enough ones), <... 0 1 1 1 1 0 ...> is invalid (too many ones), and <... 0 1 1> (bumping into the end of the horizon) may or may not be considered valid. The question is, how do we model this with binary variables.

The answer is to rethink our choice of variables: rather than focusing on binary variables representing the system state, we focus on binary decision variables indicating whether or not a particular epoch represents the start of a string of ones. So we introduce a new set of binary variables $y_i\in\{0, 1\}, i\in\{1,\dots,N\}$, where $y_i=1$ if and only if a string of $x$ variables starting at epoch $i$ take the value 1. We enforce all this with the following constraints:

1. $x_{i-1}\le 1-y_i, i\in\{2,\dots,N\}$ (the value of $x$ in the epoch immediately prior to the start of a run must be 0);
2. $x_{i+K}\le 1-y_i, i\in\{1,\dots,N-K\}$ (the value of $x$ in the epoch immediately after the end of a run must be 0); and
3. either $$x_i\ge y_j \forall i\in\{1,\dots,N\}, \forall j\in \{i-K+1,\dots,i\}$$ or $$x_i\ge \sum_{j=i-K+1}^i y_j,$$eliminating any terms with indices outside the domain $\{1,\dots,N\}$ (the $K$ values at or immediately after the start of a run must be 1).

The second version of (3) is more compact (good) but makes the constraint  matrix denser (not so good). I'm pretty sure the second version produces the tighter feasible region.

If you do not want the time frame to end on a run of fewer than $K$ ones, constrain $y_j=0$ for $j\in \{N-K+2,\dots,N\}$. If you must have at least one zero after the final run of ones (i.e., <... 0 1 1 1 0> is okay for $K=3$ but <... 0 1 1 1> is not), constrain $y_j=0$ for $j\in \{N-K+1,\dots,N\}$. If you do not want to start a run of ones at the very beginning of the time frame (<0 1 1 1 0 ...> is okay but <1 1 1 0 ...> is not), constrain $y_1=0$.