Right now, I have some binary variables for a linear programming problem:
$x_1\;x_2\;x_3\;x_4\;x_5\;x_6\;x_7\;x_8$
Say these are groups of 4 bits each in this example. So:
Group 1 ={$x_1\;x_2\;x_3\;x_4$}
Group 2={$x_5\;x_6\;x_7\;x_8$}
I want to ascertain that any $(a>=)2$ or more bits of the leftmost $(b=)3$ bits (i.e., $x_1,x_2,x_3$) of group 1 must be $0$, and these corresponding bits of group 2 must be $1$.
So the solution set should be:
Group 1 ={$0\;0\;1\;d$} or {$0\;1\;0\;d$} or {$1\;0\;0\;d$} or {$0\;0\;0\;d$}
Group 2={$1\;1\;d\;d$} or {$1\;d\;1\;d$} or {$d\;1\;1\;d$} or {$1\;1\;1\;d$}, where $d$ represents don't care bits, i.e., 0 or 1.
By this, I mean that if $001d$ is a solution for group 1 then $11dd$ is the correct solution for group 2...and three other possibilities as above.
$a$ and $b$ can vary.
Is there any linear constraint for this? Thank you for the help.
This is a total rewrite of my solution, based on changes to the original question.
Let $n$ be the number of bits in a group (4 in the original question), $b\le n$ the number of initial bits that are constrained (3 in the original question), and $a \le b$ the minimum number of 0 values among the initial $b$ bits (2 in the original question). I am assuming that, within any one problem instance, $a$, $b$ and $n$ are fixed (but could change from one problem instance to the next).
The following constraints do the job: \begin{align*} \sum_{i=1}^b x_i & \le b - a\\ x_{i + n} & \ge 1 - x_{i} \quad \forall i=1,\dots,b. \end{align*}
The first constraint ensures that at least $a$ out of the first $b$ bits in the first group are set to 0. The second set of constraints specifies that among the first $b$ bits in each group, if the bit in the first group is 0 then the corresponding bit in the second group must be 1. If the bit in the first group is 1, the corresponding bit in the second group could be either 0 or 1.
No new variables are required.