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?
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$$