# How do I arrive at the form given in this paper, for the QUBO version of the number partitioning problem?

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

 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.

\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)\tag1\\&=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)\tag2\\ &=c^2+4x^\top Qx\tag3\end{align}

Explanation:

$$(1)$$: This is a standard expansion involving a pairwise cyclic sum.

$$(2)$$: We use the fact that $$x_j=x_j^2$$ as the variable is binary, so that $$\sum s_jx_j=\sum s_jx_j^2$$. In the paper, it is stated directly above (2.1): "Let $$x_j=1$$ if $$s_j$$ is assigned to subset $$1$$, $$0$$ otherwise."

$$(3)$$: The form in $$(2)$$ indicates that diagonal elements of the matrix are $$s_j(s_j-c)$$ and off-diagonal elements $$s_ks_\ell$$ correspond to their row and column coordinates.

• Could you explain how you got from line 2 to 3, because $$\sum x_j s_j(s_j-c)x_j$$ expands to $$\sum x_j^2 s_j^2 - cx_j^2 s_j$$, which seems to be different from line 2? Also, how can you tell that summations in line 3 nicely gives the xTQx in line 4? Jun 9, 2022 at 1:48
• @ColinHong Please see my edits. Jun 9, 2022 at 7:06