Removing linear term in Quadratic assignment problem

Question

Let us consider the following Quadratic assignment problem:

\begin{equation} \tag{QP1} \max_{\begin{matrix}x_{ij}\in\{0,1\} \\ \forall j \sum_i x_{ij}=1 \\ \forall i \sum_j x_{ij}=1 \end{matrix}} x^TCx +d^{T}x=\max_{\begin{matrix}x_{ij}\in\{0,1\} \\ \forall j \sum_i x_{ij}=1 \\ \forall i \sum_j x_{ij}=1 \end{matrix}} \sum_{i,j,k,l=1}^{n}C_{ijkl}x_{ij}x_{kl}+\sum_{i,j=1}^{n}d_{ij}x_{ij} \end{equation}

It is written in [1] that "since $x_i^2=x_i$ we may assume without toss of generality that there is no linear term in the cost function, or to put it differently, the linear term consists of the main diagonal of the matrix $C$."

So that in their paper they only consider a problem (with additional constraints but they have no impact for the reasoning here): \begin{equation} \tag{QP2} \max_{\begin{matrix}x_{ij}\in\{0,1\} \\ \forall j \sum_i x_{ij}=1 \\ \forall i \sum_j x_{ij}=1 \end{matrix}} x^TCx =\max_{\begin{matrix}x_{ij}\in\{0,1\} \\ \forall j \sum_i x_{ij}=1 \\ \forall i \sum_j x_{ij}=1 \end{matrix}} \sum_{i,j,k,l=1}^{n}C_{ijkl}x_{ij}x_{kl} \end{equation}

My question is: if $d_{ij}=C_{ijij}$ does (QP2) has the same optimal solution $x^{*}$ than (QP1) ? What if $d_{ij}=n.C_{ijij}$ ?

This idea of "removing the diagonal" also appears in [2] at the beginning of the paper: "B [the linear term] can be removed from the formulation as the diagonal of A [the quadratic term] has the same effect." But i have some struggle to understand the meaning of this because it seems for me that the costs are different.

[1] Helmberg, C., Poljak, S., Rendl, F.and Wolkowicz, H. Combining semidefinite and polyhedral relaxations for integer programs. Integer Programming and Combinatorial Optimization. 1995.

[2] Oliver Burghard and Reinhard Klein, Efficient Lifted Relaxations of the Quadratic Assignment Problem. Vision, Modeling, and Visualization. 2017.

Answer 1

The idea is that you can move the costs from the diagonal to the linear part or vice versa because $y_i^2=y_i$ implies that $$\sum_i \sum_j a_{i,j} y_i y_j + \sum_i b_i y_i = \sum_i \sum_j (a_{i,j}+b_i [i=j]) y_i y_j.$$ Sometimes this technique is used to make the quadratic part convex, as described in Theorem 1 of Hammer and Rubin (1970).