# mixed integer programming with if then statement for two binary sequences

I have two random binary sequences of the same size, denoted as P1 and P2 respectively here. Let's say they are both the size of ten, like P1 = [1,0,1,1,0,0,0,1,1,1], P2 = [0,1,1,0,0,1,0,0,1,1]. I want to add a constraint such that when zero starts to appear in either P1 or P2, it must appear for exact consecutive two times in both P1 and P2.

Like when P1 = , then P2 can be like . In this example, P1 changes from 1 to 0 at the first element and the second element, hence the second element and the third element must be zero together, which also applies to P2 simultaneously. Also, P2 changes from 1 to 0 at the fifth element and sixth element. Hence, the sixth element and seventh element must be zero, which applies to P1 again.

Mathematically, it will be something like if P1[i]- P1[i+1] = 1 (this indicates P1[i+1] =0 and P1[i] =1), or P2[i] - P2[i+1] =1; then P1[i+1]=P1[i+2] = 0 and P2[i+1] = P2[i+2] = 0, where i belongs to[1,8]. I wonder how to add such constraint in mixed integer programming.

• Are you ruling out one in the 2nd to last element, followed by zero in last element, which can't be followed by another zero. because there is no next element? Or is that an exception? Dec 12, 2021 at 15:57
• Yes. I am ruling out such a situation as I intend to make the last two elements to be zero no matter what. Dec 12, 2021 at 16:03
• Your question doesn't seem to rule out one zero zero one for the last 4 elements, while your comment rules that out. Dec 12, 2021 at 16:10
• Thanks. I edited my question by adding the statement "i is less than 8". Not sure whether this can clear your confusion. Dec 12, 2021 at 16:31
• In your example ("Like when ..."), why does the initial 0 in P2 not count as the start of a sequence?
– prubin
Dec 12, 2021 at 16:32

You want to enforce $$((P_{1.i} \land \lnot P_{1,i+1}) \lor (P_{2,i} \land \lnot P_{2,i+1})) \implies (\lnot P_{1,i+1} \land \lnot P_{1,i+2} \land \lnot P_{2,i+1} \land \lnot P_{2,i+2})$$ Rewrite in conjunctive normal form: $$(¬P_{1,i} ∨ P_{1,i+1} ∨ ¬P_{1,i+2}) ∧ (¬P_{1,i} ∨ P_{1,i+1} ∨ ¬P_{2,i+1}) ∧ (¬P_{1,i} ∨ P_{1,i+1} ∨ ¬P_{2,i+2}) ∧ (¬P_{1,i+1} ∨ ¬P_{2,i} ∨ P_{2,i+1}) ∧ (¬P_{1,i+2} ∨ ¬P_{2,i} ∨ P_{2,i+1}) ∧ (¬P_{2,i} ∨ P_{2,i+1} ∨ ¬P_{2,i+2})$$ This immediately yields linear constraints $$(1-P_{1,i} + P_{1,i+1} + 1-P_{1,i+2} \ge 1) ∧ (1-P_{1,i} + P_{1,i+1} + 1-P_{2,i+1}\ge 1) ∧ (1-P_{1,i} + P_{1,i+1} + 1-P_{2,i+2}\ge 1) ∧ (1-P_{1,i+1} + 1-P_{2,i} + P_{2,i+1}\ge 1) ∧ (1-P_{1,i+2} + 1-P_{2,i} + P_{2,i+1}\ge 1) ∧ (1-P_{2,i} + P_{2,i+1} + 1-P_{2,i+2}\ge 1)$$ Equivalently, \begin{align} P_{1,i} - P_{1,i+1} + P_{1,i+2} &\le 1 \\ P_{1,i} - P_{1,i+1} + P_{2,i+1} &\le 1 \\ P_{1,i} - P_{1,i+1} + P_{2,i+2} &\le 1 \\ P_{2,i} - P_{2,i+1} + P_{1,i+1} &\le 1 \\ P_{2,i} - P_{2,i+1} + P_{1,i+2} &\le 1 \\ P_{2,i} - P_{2,i+1} + P_{2,i+2} &\le 1 \end{align}
• The number of constraints grows quadratically with the number of sequences: $s(2s-1)(n-2)$ for $s$ sequences each of length $n$. Dec 12, 2021 at 20:07