2
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$ Dec 12, 2021 at 15:57
  • $\begingroup$ Yes. I am ruling out such a situation as I intend to make the last two elements to be zero no matter what. $\endgroup$ Dec 12, 2021 at 16:03
  • $\begingroup$ Your question doesn't seem to rule out one zero zero one for the last 4 elements, while your comment rules that out. $\endgroup$ Dec 12, 2021 at 16:10
  • $\begingroup$ Thanks. I edited my question by adding the statement "i is less than 8". Not sure whether this can clear your confusion. $\endgroup$ Dec 12, 2021 at 16:31
  • $\begingroup$ In your example ("Like when ..."), why does the initial 0 in P2 not count as the start of a sequence? $\endgroup$
    – prubin
    Dec 12, 2021 at 16:32

1 Answer 1

4
$\begingroup$

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}

$\endgroup$
4
  • $\begingroup$ Thank you for your proposed solution. It works perfectly. More importantly, I am a new modeler, and I learned a lot from your approach to derive the formulas. $\endgroup$ Dec 12, 2021 at 18:59
  • $\begingroup$ Sorry a follow up question just popped out of my head. What if I want to constrain more than two binary sequences, like four or six binary sequences, will the number of constraints I need to construct increase significantly? $\endgroup$ Dec 12, 2021 at 19:41
  • 1
    $\begingroup$ The number of constraints grows quadratically with the number of sequences: $s(2s-1)(n-2)$ for $s$ sequences each of length $n$. $\endgroup$
    – RobPratt
    Dec 12, 2021 at 20:07
  • $\begingroup$ Thanks for your good response. $\endgroup$ Dec 12, 2021 at 22:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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