# Encoding a binary sequence with shift in MILP

I would like to know if it's actually possible to encode a (binary) sequence with rotations in MILP/MIP.

Given a binary sequence $$(0,1,1,0,0,0,0,1)$$ and variables $$x_0,x_1,x_2,x_3,x_4,x_5,x_6,x_7$$ I want to restrict my MILP program such that it takes up one of the following:
\begin{align} (x_0,x_1,x_2,x_3,x_4,x_5,x_6,x_7) & = (0,1,1,0,0,0,0,1)\text{ or} \\ (x_7,x_0,x_1,x_2,x_3,x_4,x_5,x_6) & = (0,1,1,0,0,0,0,1)\text{ or} \\ (x_6,x_7,x_0,x_1,x_2,x_3,x_4,x_5) & = (0,1,1,0,0,0,0,1)\text{ or} \\ \vdots \\ (x_1,x_2,x_3,x_4,x_5,x_6,x_7,x_0) & = (0,1,1,0,0,0,0,1) \end{align}

I understand that the rotation can be easily solved by just extending the sequence. But I find myself creating multiple MILP instances, each instance corresponding to exactly one of the cases. If this is infeasible, why?

• Why do you need linear programming for this? Oct 9 '21 at 12:00
• It is part of a bigger problem I am currently working on and I require the sequence to be enforced in it. I have worked out a CP model as well. However, due to the large search space, MILP is faster in converging to an optimal solution. Thus, I was interested in the feasibility of such formulation. Oct 9 '21 at 12:13
• cs.stackexchange.com/q/12102/755
– D.W.
Oct 10 '21 at 6:42

To encode a table constraint in MILP, the generally idea is to create a new zero one variable $$s$$ for every row in the table that signifies whether the row is selected. There are then two kinds of constraints. $$\sum_{i \in rows} s_i = 1$$
$$\sum_{j \in col} table_{ij}*s_i = x_i ,\forall_{i \in rows}$$