3
$\begingroup$

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.

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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

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

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.