Skip to main content
edit the tags
Link
Source Link

Removing linear term in Quadratic assignment problem

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.