mixed integer programming with if then statement for two binary sequences

Question

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 = [1000000111], then P2 can be like [0001100000]. 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.

Answer 1

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}