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.

Improve this question
$\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$ Commented 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$ Commented 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$ Commented 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$ Commented 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$ Commented Dec 12, 2021 at 16:32

1 Answer 1

Reset to default
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}

Improve this answer
$\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$ Commented 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$ Commented 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$ Commented Dec 12, 2021 at 20:07
  • $\begingroup$ Thanks for your good response. $\endgroup$ Commented 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.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.