Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

EDIT:

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|improve this question
add comment

1 Answer

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|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
add comment

Your Answer

 
discard

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.