Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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}$$

share|cite|improve this answer
Hi, what is not clear exactly? I made some changes maybe now it's better. – memecs Jan 23 '13 at 9:36

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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