How can i find the solution of this NP-hard optimization problem?

Question

I have an NP-Hard optimization problem of the form:

\begin{align} & \min {{\sum\limits_{i=1}^{M}{{{a}_{i}}}}_{{}}} \\ & s.t{{.}\:\:\:\:_{{}}}{{_{{}}}_{{}}}\sum\limits_{i=1}^{M}{{{a}_{i}}{{a}_{i+k}}}>0\:\: \: \:{{,}_{{}}}{{_{{}}}_{{}}}\forall k=0,1,\ldots ,M-1 \\ & \:\:\:\:\:\:\:\:\:\:\:{{a}_{i}}\in \left\{ 0,1 \right\}\:\:\:\:\:\:\:\:\:\:{{,}_{{}}}i=1,\ldots ,M. \\ \end{align}

How can I found any optimum or sub-optimum solution?

Answer 1

You can linearize the quadratic constraint by introducing a binary variable $b_{i,k}$ to represent the product $a_i a_{i+k}$. The new constraints are: \begin{align} \sum_i b_{i,k} &\ge 1 &&\text{for all $k$}\\ b_{i,k} &\le a_i &&\text{for all $i$ and $k$}\\ b_{i,k} &\le a_{i+k} &&\text{for all $i$ and $k$} \end{align}