1
$\begingroup$

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.

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$
21
  • 1
    $\begingroup$ Are you saying that every 0 in the first three bits of the first group must be matched by a 1 in the same bit of the second group, even if all three of the firs three bits of the first group are 0? $\endgroup$ Commented Nov 25, 2021 at 21:21
  • 1
    $\begingroup$ You just said [0 0 d d d] => [1 1 d d d] and [0 0 0 d d] => [1 1 1 d d]. Suppose the first group is [0 0 0 1 0]. The first of those rules allows group 2 to be [1 1 0 0 0] (third bit 0) but the second rule does not. This is inconsistent. $\endgroup$ Commented Nov 26, 2021 at 4:06
  • 1
    $\begingroup$ So your statement that (two comments back) that "if group 1 = {$0\;0\;d\;d\;d$} then group 2 = {$1\;1\;d\;d\;d$}" is incorrect, because the first $d$ in group 1 is not a "don't care" bit, in that if it is 0 then $a$ becomes 3 and the corresponding bit of group 2 must be a 1? Is $b$ fixed, or does that vary as well? $\endgroup$ Commented Nov 26, 2021 at 16:59
  • 1
    $\begingroup$ Yes, that is correct. $\endgroup$ Commented Nov 28, 2021 at 19:51
  • 1
    $\begingroup$ Yes, it means at least $a$. $\endgroup$ Commented Nov 30, 2021 at 4:23

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.