# MILP optimization constraint formulation

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?

## 1 Answer

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.

• Wouldn't it be easier to say $-z_i\leq x_i- x_{i-1}\le z_i$, and $\sum z_i\le2$ ? That is, $z_i$ represents a jump between $1$ and $0$ and you limit the amount of jumps. I think your formulation does not forbid the case $(1,1,1,0,\dots,0,1,1,1)$ – dafinguzman Dec 28 '15 at 20:21
• Yeah. Essentially I wouldn't want to allow any number of $0$'s between the $1$'s. so situations like $\{0,0,0,\ldots,1,1,1,0,1,1,1\}$ or $\{1,1,1,0,\ldots,0,1,1,1\}$ should be constrained. – ELEC Dec 28 '15 at 20:31
• I believe my formulation is correct (a lot of my models would fail to work if this did not work). – Erwin Kalvelagen Dec 28 '15 at 20:57
• @ErwinKalvelagen your formulation works like a charm on my model! Thanks! – ELEC Dec 29 '15 at 18:08
• @ELEC Excellent! – Erwin Kalvelagen Dec 29 '15 at 18:22