How to model a constraint of consecutiveness in 0-1 programming?

161 Views Asked by At

I need to model a constraint of consecutiveness in 0-1 programming problem.

Let $S=\{1,\ldots,n\}$. Let $x_{i}$ be a Boolean variable for all $i\in S$. I need to model this situation. If $x_i=1$ and $x_k=1$ then we must have $x_\ell=1$ for all $\ell$ between $i$ and $k$.

I tried to do it this way:

$$x_i + x_k\leqslant 2 x_\ell + M_1(1-x_i) + M_2(1-x_k), \forall\,\ell\in [\![\min(i, k), \max(i, k)]\!],$$

where $M_1$ and $M_2$ are any big numbers.

1

There are 1 best solutions below

0
On BEST ANSWER

Your equation describes it well. However, you can write simply

$$\forall (i,\ell,k)\in S^3 \text{ such that } i \leq \ell \leq k, x_i + x_k \leq 1 + x_\ell,$$

which is what you get with your equation with $M_1=M_2=1$, and is probably tighter.