I'm trying to formulate a linear constraint
$$Ax\leq b$$ $$x\in\{0,1\}^n$$
such that the feasible set is exactly those binary vectors $x$ with a single contiguous string of ones of length $k$.
For example, if $n=4$ and $k=2$, then it would be the vectors:
$$(1,1,0,0)$$ $$(0,1,1,0)$$ $$(0,0,1,1)$$
I've so far been unsuccessful at finding a suitable $A$ and $b$, can anyone help me out with this?
Adding two binary vectors that indicate the start and end locations of your contiguous string, $b_1$ and $b_2$, the problem can be formulated as: $$ \begin{align*} \sum_{j=1}^{i-1} x_j \leq (i-1) - (i-1)(b_1)_i \quad \forall i\\ \sum_{j=i+1}^{n} x_j \leq (n-i) - (n-i)(b_2)_i \quad \forall i \\ x_i \geq \sum_{j=1}^i (b_1)_j - \sum_{j=1}^{i-1} (b_2)_j \quad \forall i\\ \sum_{i=1}^n (b_1)_i = 1 \\ \sum_{i=1}^n (b_2)_i = 1 \\ x, b_1, b_2 \in \{0,1\}^n \end{align*} $$ Let $l$ and $r$ denote the index where $b_1=1$ resp. $b_2=1$. The first two constraints ensure that $x_j=0$ for $j<l$ and for $j>r$. The third constraint sets $x_i=1$ if $l \leq i \leq r$.
You can transform equality constraints into inequalities. You can then rewrite the constraints as $Ax + Gb_1 + Hb_2 \leq b$.
Alternative solution If you do not want to add additional variables, you have to add many logical statements of the form $x_3=0 \wedge x_5=1 \Rightarrow x_1=0$. This particular one can be formulated as $x_1 \leq 1+x_3-x_5$.