Encoding a binary sequence with shift in MILP

Question

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?

• nir shahar: Why do you need linear programming for this?
• DuckyQ: 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.
• D.W.: cs.stackexchange.com/q/12102/755

Answer 1

In constraint programming this particular type of constraint is known as a table constraint. It is generally said to be an existential constraint, since many other constraints can be encoded using a table constraint. As such, it is often better to use the underlying structure when possible (I don't see a way around it in this case), although tables have been proven to be very effective in constraint programming solvers.

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

This is how the MiniZinc constraint modelling language would also encode this constraint for MILP solvers: https://github.com/MiniZinc/libminizinc/blob/master/share/minizinc/linear/fzn_table_int.mzn