Model the constraints of an integer linear program

Question

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.

Answer 1

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

Answer 2

Writing variables as $y(i,j)$ is not conventional. Following what you've written, define $y_{ij}= \begin{cases} 1 & \text{if configuration $i$ is active at time $j$}; \\[2ex] 0 & \text{otherwise}. \end{cases}$

You also need to define binary variables to indicate if a configuration is chosen or not as $z_i = \begin{cases} 1 & \text{if configuration $i$ is chosen}; \\[2ex] 0 & \text{otherwise}. \end{cases}$

Now the constraint of part b) can be written as $$\sum_{j=1}^{T}y_{ij}\ge \bar{t} \cdot z_i, i=1,\cdots, C$$

If configuration $i$ is chosen, $z_i=1$, at least $\bar t$ time intervals are forced; otherwise, $z_i=0$, which places no constraints on time invervals.

Edit for consecutive time intervals. No need to use $z_i$ any more.

Let's use Configuration 1 with $\bar{t}=3$ as an example. The constraints should be like $$y_{12}\ge y_{11}-\frac{1}{3}y_{11}$$ $$y_{13}\ge y_{12}-\frac{1}{3}(y_{11}+y_{12})$$ $$y_{14}\ge y_{13}-\frac{1}{3}(y_{11}+y_{12}+y_{13})$$ $$y_{15}\ge y_{14}-\frac{1}{3}(y_{12}+y_{13}+y_{14})$$ $$\cdots$$ $$y_{1,T}\ge y_{1,T-1}-\frac{1}{3}(y_{1,T-3}+y_{1,T-2}+y_{1,T-1})$$

Does this work? If $y_{11}=1$, then the first three constraints force $y_{12}=y_{13}=1$, but $y_{14}$ is flexible.

Putting it in a compact form, it becomes $$y_{ij}\ge y_{i,j-1}-\frac{1}{\bar{t}}\sum_{k=1}^{\bar{t}}y_{i,j-k}, j=2, \cdots, T; i=1,\cdots, C.$$ $$y_{i,0}=y_{i,-1}=0, i=1, \cdots, C.$$