4
$\begingroup$

Is there any effective algorithm for a squared linear sum assignment problem?

For squared linear sum assignment problem I mean the following:

$$\min\left(\sum_i \sum_j c_{ij}x_{ij}\right)^2$$

with the conditions

$ \sum_j x_{ij}=1\\ \sum_i x_{ij}=1\\ x_{ij}\in\{0,1\} $

2 Answers 2

2

Here is an alternate formulation as a linear program.

Minimising $x^2$ is equivalent to minimising $|x|$. If you then define a new variable $u$ such that $x-u\leq My$ and $-u-x\leq M(1-y)$, $y=\{0,1\}$ and $M$ is some large number, you can solve the problem as $\min u$, with these extra constraints. These two constraints essentially ensure that $u\geq|x|$. You lose the structure of an assignment problem, but you do obtain a linear program.

Formulation:

$$\min u$$ $$Z\leq M(1-y)$$ $$ Z-u\leq My$$ $$-Z\leq My $$ $$ -u-Z\leq M(1-y)$$ $$\sum_i x_{ij}=1$$ $$\sum_j x_{ij}=1$$ $$y=\{0,1\}$$ $$x_{ij}=\{0,1\}$$ $$u\geq 0$$

where I have used $Z$ to represent your term inside the square in the objective function.

  • 0
    Why isn't the solution to this program $u=0$? If $Z$ takes at least one positive value $Z_+$, then $y=1$, $Z=Z_+$ and $u=0$ is a solution, and if $Z$ takes at least one negative value $Z_-$, then $y=0$, $Z=Z_-$ and $u=0$ is a solution. Or am I missing something?2012-09-21
  • 0
    @joriki I had a sign wrong in my working. I have fixed it now.2012-09-21
  • 0
    If $Z$ takes negative values, $u=0$ is still a solution (now with either $y=0$ or $y=1$).2012-09-21
  • 0
    I was right the first time. Let me think for a moment to describe it. I may also have royally screwed up...2012-09-21
  • 0
    I think that is good now @joriki. There was a few negative signs going astray.2012-09-21
  • 0
    Yes, it makes sense now :-)2012-09-21
1

In other words, you want to find a permutation $\sigma$ that minimizes $|\sum_i c_{i\sigma(i)}|$?

That is NP-hard, by reduction from the subset sum problem, which asks, for a finite (multi)set of numbers $a_1,\ldots,a_n$, whether there is a nonempty subset that sums to 0.

Given an instance of subset sum, construct a $c_{ij}$ matrix of dimension $(2n-1)\times(2n-1)$ as follows: $$C=\begin{bmatrix} a_1 & a_1 & \cdots & a_1 & 0 & \cdots & 0 \\ a_2 & a_2 & \cdots & a_2 & 0 & \cdots & 0 \\ \vdots & \vdots &\ddots& \vdots & \vdots && \vdots \\ a_n & a_n & \cdots & a_n & 0 & \cdots & 0 \\ 0 & 0 & \cdots & 0 & 0 & \cdots & 0 \\ \vdots & \vdots && \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 0 & 0 & \cdots & 0 \end{bmatrix}$$ with $n$ copies of each $a_i$, $n-1$ columns of zeroes to the right, and $n-1$ rows of zeroes at the bottom.

Then $\min_\sigma |\sum_i c_{i\sigma(i)}|=0$ if and only if there's a nonempty subset of the $a_i$s that sums to $0$. (Clearly $\sum_i c_{i\sigma(i)}$ is always the sum of some subset of the $a_i$s, and it has to be a nonempty subset because there are not enough zero columns for the permutation to avoid all of them).