0

I want to linearize the following absolute value constraint for MILP:

$ \sum_{l=1}^{n} |x_{gl} - x_{hl} | > k $, where $x_{g}$ and $x_{h}$ represent different types of bit strings of length $n$ and $k$ represents Hamming distance (HD) between the bit strings.

All I am saying here is that the HD between $x_{g}$ and $x_{h}$ bit strings should be more than $k$.

How do I linearize this?

1 Answers1

2

Introduce a binary decision variable $z_{g,h,l}$ to represent the absolute value. You want to enforce $z_{g,h,l} = 1 \implies x_{g,l} \not= x_{h,l}$ (equivalently, $x_{g,l} + x_{h,l} = 1$ because $x$ is binary), which you can do with the following linear constraints: $$-(1 - z_{g,h,l}) \le x_{g,l} + x_{h,l} - 1 \le 1 - z_{g,h,l}$$ The absolute value constraint then becomes $$\sum_{l=1}^n z_{g,h,l} \ge k+1$$

RobPratt
  • 45,619
  • Could you please elaborate on how the linear constraints came about? –  Oct 18 '20 at 23:34
  • 1
    To enforce $z=1 \implies f(x) \le 0$, impose big-M constraint $f(x) \le M(1-z)$. To enforce $z=1 \implies f(x) = 0$, impose two big-M constraints $-M(1-z) \le f(x) \le M(1-z)$. – RobPratt Oct 18 '20 at 23:55
  • what is f(x)...? Please understand I am totally new at this big M thing. –  Oct 19 '20 at 00:09
  • 1
    Here, $f(x)=x_{g,l}+x_{h,l}-1$, $z=z_{g,h,l}$, and $M=1$. For many examples of big-M, see https://or.stackexchange.com/questions/tagged/big-m – RobPratt Oct 19 '20 at 00:25
  • What is the purpose of the linear constraints? Can you describe it please? why do you enforce z=1 twice and make sure f(x)<=0 and f(x)=0? –  Oct 19 '20 at 00:48
  • 1
    There are two constraints because $z=1 \implies f(x) = 0$ is equivalent to $(z=1 \implies f(x) \le 0) \land (z=1 \implies -f(x) \le 0)$. – RobPratt Oct 19 '20 at 00:52
  • My apologies. I realized I made a mistake in the constraint- there will be a ">" instead of ">=". Do you think I should edit it in the question? The answer will be same right? –  Oct 19 '20 at 01:27
  • For $>k$, instead impose $\ge k+1$. – RobPratt Oct 19 '20 at 02:13
  • This? $\sum_{l=1}^n z_{g,h,l} \ge k+1$? –  Oct 19 '20 at 02:23
  • 1
    Yes, and please edit the question. – RobPratt Oct 19 '20 at 02:24
  • Your new constraint does not make sense because $x_{g,l}-x_{g,l}=0$ always. – RobPratt Oct 19 '20 at 02:34
  • You referred to $x_g$ as a bit string but then expressed $x_g$ as a set of two bit strings. That is inconsistent. – RobPratt Oct 19 '20 at 03:24
  • What I mean is for example : $x_g$ ={000000,000011,001100,001111,111111} and $x_h$ = {100001,101000,101100 } ..you can see that x_g has all its elements' HD > 1 between each other and HD between elements of x_g and x_h >1, if k = 1 ...comparison at a time will always happen between two strings..that's why I showed an example with two strings... –  Oct 19 '20 at 03:42
  • 1
    Now you are talking about $x_g$ as being an element of a set, so I recommend $x_g \in{\dots}$ instead of $x_g ={\dots}$. – RobPratt Oct 19 '20 at 19:01