Cuadrados suma lineal

Question

¿Hay cualquier algoritmo eficaz para un problema de asignación cuadrática suma lineal?

Para el problema de asignación cuadrática suma lineal quiero decir lo siguiente:

$$\min\left(\sum_i \sumj c{ij}x_{ij}\right)^2$$

con las condiciones

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

Answer 1

Aquí es una alternativa formulación como un problema de programación lineal.

Minimizar $x^2$ es equivalente a minimizar $|x|$. Si a continuación se define una nueva variable $u$ tal que $x-u\leq My$ y $-u-x\leq M(1-y)$, $y=\{0,1\}$ y $M$ es un número grande, usted puede solucionar el problema como $\min u$, con estas restricciones. Estas dos restricciones esencialmente asegurarse de que $u\geq|x|$. Se pierde la estructura de un problema de la asignación, pero sí obtener un problema de programación lineal.

Formulación:

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

donde he utilizado $Z$ a representar a su término el interior de la plaza en la función objetivo.

Answer 2

En otras palabras, usted quiere encontrar una permutación $\sigma$ que minimiza $|\sum_i c_{i\sigma(i)}|$?

Que es NP-duro, por la reducción del subconjunto suma el problema, lo que pide, para un número finito (multi)el conjunto de números $a_1,\ldots,a_n$, si existe un subconjunto no vacío que sumas a 0.

Dada una instancia de subconjunto suma, la construcción de una $c_{ij}$ matriz de dimensión $(2n-1)\times(2n-1)$ como sigue: $$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}$$ con $n$ copias de cada $a_i$, $n-1$ columnas de ceros a la derecha, y $n-1$ filas de ceros en la parte inferior.

A continuación, $\min_\sigma |\sum_i c_{i\sigma(i)}|=0$ si y sólo si existe un subconjunto no vacío de la $a_i$s que sumas a $0$. (Claramente $\sum_i c_{i\sigma(i)}$ es siempre la suma de un subconjunto de la $a_i$s, y tiene que ser un vacío subconjunto porque no hay suficientes columnas cero para la permutación para evitar todos los de ellos).