2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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)$ $\endgroup$ – dafinguzman Dec 28 '15 at 20:21
  • $\begingroup$ 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. $\endgroup$ – ELEC Dec 28 '15 at 20:31
  • $\begingroup$ I believe my formulation is correct (a lot of my models would fail to work if this did not work). $\endgroup$ – Erwin Kalvelagen Dec 28 '15 at 20:57
  • $\begingroup$ @ErwinKalvelagen your formulation works like a charm on my model! Thanks! $\endgroup$ – ELEC Dec 29 '15 at 18:08
  • $\begingroup$ @ELEC Excellent! $\endgroup$ – Erwin Kalvelagen Dec 29 '15 at 18:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.