Model the constraints of an integer linear program

integer programminglinear programmingoperations researchoptimization

I have to model the costraints of an integer linear program. The objective function is not important here.
Suppose we have $C$ configurations (indexed by $i = 1, \dots, C$) and $T$ time intervals (indexed by $j = 1, \dots, T$). I wish that:

a) only one configuration is active at each time interval;

b) when a configuration has been chosen I must keep it for at least $\bar{t}$ time intervals (with $\bar{t} \leq T$).

So I define the decision variables:

$y(i,j) :=
\begin{cases}
1 & \text{if configuration $i$ is active at time $j$}; \\[2ex]
0 & \text{otherwise}.
\end{cases}$

For request a) I write the constraints:
\begin{equation}
\sum_{i=1}^C y(i,j) = 1 \ \ \ \forall \ j = 1, \dots, T.
\end{equation}

Now, I don't know how to proceed with the request b). Any help or suggestions are appreciated. Thanks in advance.

Best Answer

For part b), you can introduce another binary variable $x_{i,j}$ to indicate the start, together with constraints: \begin{align} x_{i,j} &\le y_{i,k} &&\text{for $k\in\{j,\dots,j+\overline{t}-1\}$} \tag1\\ x_{i,j} &\le 1 - y_{i,j-1} \tag2\\ (1 - y_{i,j-1}) + y_{i,j} - 1 &\le x_{i,j} \tag3 \end{align} Constraint $(1)$ enforces $x_{i,j} = 1 \implies \land_{k=j}^{j+\overline{t}-1} (y_{i,k} = 1)$. Constraint $(2)$ enforces $x_{i,j} = 1 \implies y_{i,j-1} = 0$. Constraint $(3)$ enforces $(y_{i,j-1} = 0 \land y_{i,j} = 1) \implies x_{i,j} = 1$.


Alternatively, you can omit $x$ and just impose $$(1 - y_{i,j-1}) + y_{i,j} - 1 \le y_{i,k} \quad\text{for $k\in\{j+1,\dots,j+\overline{t}-1\}$},$$ equivalently, $$y_{i,j} - y_{i,j-1} \le y_{i,k} \quad\text{for $k\in\{j+1,\dots,j+\overline{t}-1\}$}, \tag4$$ (where $y_{i,j}$ is treated as $0$ if $j<0$ or $j>T$), which enforces $$(y_{i,j-1} = 0 \land y_{i,j} = 1) \implies \bigwedge_{k=j+1}^{j+\overline{t}-1} (y_{i,k} = 1).$$


Yet a third approach is to enforce $$\left(y_{i,j-1} \land \lnot \bigwedge_{k=1}^{\overline{t}} y_{i,j-k}\right) \implies y_{i,j},$$ equivalently, $$\left(\lnot y_{i,j-1} \lor \bigwedge_{k=1}^{\overline{t}} y_{i,j-k}\right) \lor y_{i,j},$$ which has conjunctive normal form $$\bigwedge_{k=1}^{\overline{t}} \left(\lnot y_{i,j-1} \lor y_{i,j-k} \lor y_{i,j}\right),$$ yielding linear constraints $$1 - y_{i,j-1} + y_{i,j-k} + y_{i,j} \ge 1 \quad \text{for $k \in \{1,\dots,\overline{t}\}$}.$$ Rearranging this, we obtain $$y_{i,j} \ge y_{i,j-1} - y_{i,j-k} \quad \text{for $k \in \{1,\dots,\overline{t}\}$}. \tag5$$ Now we can recover @toronto hrb's formulation by aggregation: $$y_{i,j} \ge y_{i,j-1} - \frac{1}{\overline{t}}\sum_{k=1}^{\overline{t}} y_{i,j-k} \tag6$$ So $(6)$ is correct but weaker than $(5)$.