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


[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.


1 Answer 1


\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}


$(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.

  • $\begingroup$ 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? $\endgroup$
    – Colin Hong
    Jun 9, 2022 at 1:48
  • 1
    $\begingroup$ @ColinHong Please see my edits. $\endgroup$
    – TheSimpliFire
    Jun 9, 2022 at 7:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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