MILP optimization constraint formulation

Question

I'm trying to find a sensible way to add constraint for my optimization problem.

Lets assume we have binary decision variables $x_i\in\{0,1\}$ and two constraints \begin{align*} \sum\limits_{i=1}^n x_i&\geq Y_1\\ \sum\limits_{i=1}^n x_i &\leq Y_2\end{align*}

How could I add constraints to my problems in such way that all decision variables that are $1$ have to be "grouped" together and there is no "holes" (zeroes) inside them. So if $n=5,Y_1=2,Y_2=3$ feasible solutions would be

\begin{align*}&\overbrace{\{1,1,0,0,0\}}^{Y_1\,\text{solutions}}\;\text{OR}\\ &\{0,1,1,0,0\}\;\text{OR}\\ &\vdots\\ &\{0,0,0,1,1\} &\\ &\overbrace{\{1,1,1,0,0\}}^{Y_2\, \text{solutions}}\;\text{OR}\\ &\vdots\\ &\{0,0,1,1,1\}\end{align*}

And unfeasible solution would be for example

$$\{1,0,1,0,1\}$$

How could this kind of constraint be implemented?

Answer 1

We see such a condition sometimes in power generation modeling: we want to limit the number of start-ups (switch from 0 to 1) of a generator. There is a smart formulation for this:

$$\begin{array}{l} z_i \ge x_i - x_{i-1} \\ \sum_i z_i \le 1 \\ z_i \in \{0,1\} \end{array} $$

Notes:

• We only model the implication 'if $x_{i-1}=0$ and $x_i=1$ then $z_i=1$'. Otherwise we leave $z_i$ just floating. This actually works in this case: we don't need to add an implication to force $z_i$ to become zero. The bound on $\sum z_i$ takes care of that if needed. This may not be immediately obvious.
• Actually we can even relax $z_i$ to be continuous between zero and one.

• The start period $x_1$ always needs some attention. (Does $x_1=1$ count or not?) It looks like you want to forbid $[1,0,1,1,1]$ so the first 1 needs to be counted as a start-up. I.e. we can assume $x_0=0$. In other words we have: $$ \begin{array}{ll} z_i \ge x_i - x_{i-1} \> \forall i>1 \\ z_1 \ge x_1 \\ \sum_i z_i \le 1 \\ z_i \in \{0,1\} \end{array} $$

• In practical models we often look up the last historic state $x_0$ in the database (this is not a variable but a fixed parameter). This will give us enough information to deal with $x_1$ correctly.