3
$\begingroup$

In this article A new modeling and solution approach for the number partitioning problem1, it transforms the number partition problem into a QUBO form like equation (2.1) on page 2. $$\text{diff}=\sum_{j=1}^ms_j-2\sum_{j=1}^ms_jx_j=c-2\sum_{j=1}^ms_jx_j\tag{2.1}$$ My question is how to turn (2.1) into (2.2) and (2.3)?

\begin{align} \text{diff}^2&=\left\{c-2\sum_{j=1}^ms_jx_j\right\}^2 \\ &=c^2+4xQx\tag{2.2} \end{align}

where $$q_{ii}=s_i(s_i-c),\quad q_{ij}=s_is_j\tag{2.3}$$


Reference

[1] Alidaee, B., Glover, F., Kochenberger, G. A., Rego, C. (2005). A new modeling and solution approach for the number partitioning problem. Journal of Applied Mathematics and Decision Sciences. 2005(2):113–21.

$\endgroup$
3
$\begingroup$

\begin{align}\text{diff}^2&=c^2+4\left(\left(\sum s_jx_j\right)^2-c\sum s_jx_j\right)\\&=c^2+4\left(\sum s_j^2x_j^2+\sum_{\rm cyc}s_ks_\ell x_kx_\ell-c\sum s_jx_j\right)\\&=c^2+4\left(\sum x_j\boldsymbol{s_j(s_j-c)}x_j+\sum_{\rm cyc}x_k\boldsymbol{s_ks_\ell}x_\ell\right)\\ &=c^2+4x^\top Qx\end{align}

$\endgroup$
1
  • $\begingroup$ My edit was just minor, only because I couldn't figure out immediately how this was the same as Eq. 2.2. $\endgroup$ Jul 26 at 22:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.