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?

  • $\begingroup$ Why do you need linear programming for this? $\endgroup$
    – nir shahar
    Oct 9 '21 at 12:00
  • $\begingroup$ 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. $\endgroup$
    – DuckyQ
    Oct 9 '21 at 12:13
  • $\begingroup$ cs.stackexchange.com/q/12102/755 $\endgroup$
    – D.W.
    Oct 10 '21 at 6:42

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.