Given a set of binary variables $x_{ij} \in X,\ i=0,..,N,\ j=0,..,M$ how do I model an adjacency constraint on $i$'s such that:

  1. $\sum_i^N\sum_j^Mx_{ij} = \alpha, \;\text{with }\ 0 < \alpha < N$ and
  2. $i_0,\ldots,i_\alpha$ are adjacent/consecutive numbers.

For example, assuming $\alpha=3$, $\{x_{32}=\ x_{49}=\ x_{57}=1\}$ would be a feasible solution while $\{x_{22}=\ x_{49}=\ x_{57}=1\}$ is not because $i=2$ in $x_{i=2,j=2}$ is not consecutive to $i=4$ in $x_{i=4,j=9}$.


In simpler words given N binary variables $x_{i},x_{i+1},..,x_{i+N}$ exactly $\alpha$ variables can be equal to 1 and they have to be consecutives. For example $\{x_{i} = x_{i+1} = x_{i+2} = 1\}$ is a valid solution while $\{x_{i} = x_{i+1} = x_{i+3} = 1\}$ is not.


It's not quite clear to me, but I think you mean there is some $k \in [0, \ldots, N+1-\alpha]$ such that $\sum_{j=0}^M x_{ij} = 1$ for $i = k, k+1, \ldots, k+\alpha - 1$ while $\sum_{j=1}^M x_{ij} = 0$ for all other $i$. You can model this with binary variables $t_i$, $i=0 \ldots N+1-\alpha$, and constraints $$ \eqalign{\sum_{i=0}^{N+1-\alpha} t_i & = 1 \cr \sum_{j=0}^M x_{ij} - \sum_{k=\max(0,i+1-\alpha)}^{\min(i,N+1-\alpha)} t_k &= 0 \text{ for each $ i = 0 \ldots N$}\cr}$$

  • $\begingroup$ Hi, what is not clear exactly? I made some changes maybe now it's better. $\endgroup$ – memecs Jan 23 '13 at 9:36

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.