Problema de asignación que maximiza la norma de la suma de vectores

Question

Tengo el siguiente problema de asignación

\begin{align} \text{Maximize: }\quad &\left|\left|\sum_{i=1}^{n}\sum_{j=1}^{n} \boldsymbol{v}_{ij} x_{ij}\right|\right|_2^2\\ \text{such that: }\quad &\sum_{j=1}^n x_{ij} = 1, \quad \forall i = 1, \ldots,n\\ \quad &\sum_{i=1}^n x_{ij} = 1, \quad \forall j = 1, \ldots,n\\ &x_{ij}\in \{0,1\} \end{align}

Ici $\boldsymbol{v}_{ij}$ son vectores correspondientes a la asignación de $i$ a $j$ con coordenadas $(\boldsymbol a_i \cdot \boldsymbol b_j, ||\boldsymbol a_i \times \boldsymbol b_j||_2)$ , donde $\boldsymbol a_i$ y $\boldsymbol b_j$ son vectores arbitrarios en $\mathbb R^2$ . ¿Cómo podemos resolver el problema de forma eficiente? Si es NP-difícil, ¿cómo podemos acercarnos a un algoritmo de aproximación?

Notas:

1. Si la función objetivo fuera lineal, entonces el problema habría sido un Problema de Asignación de Sumas Lineales (LSAP) estándar con una complejidad de $\mathcal O(n^3)$ .

2. La función objetivo es cuadrática en las variables $x_{ij}$ por lo que se trata de un Problema de Asignación Cuadrática (QAP). El QAP es NP-duro en general. Sin embargo, puede haber alguna estructura en este problema que lo haga resoluble en tiempo polinómico o un algoritmo de aproximación eficiente.

3. Maximización de la magnitud del vector resultante es para el problema de encontrar el subconjunto de los vectores que maximizan la norma. La solución se basa en ordenar los vectores en función del ángulo y demostrar que los vectores del subconjunto tienen que ser contiguos. Me pregunto si este análisis podría ser útil en este caso.

4. A $\sqrt{n}$ El algoritmo de aproximación para el QAP general se da en 1 .

5. 2 ofrece una descripción general del QAP. Sin embargo, se ocupa del problema de minimización.

6. Una forma diferente de describir la función objetivo para QAP se da en 3 . $$ \text{Maximize} \sum_{i, j \in [n], i\neq j} w_{ij} d_{\pi(i)\pi(j)} $$ Ici $\pi: [n]\mapsto [n]$ es la permutación para la asignación. $W=(w_{ij})$ y $D=(d_{\pi(i)\pi(j)})$ son matrices simétricas no negativas. No estoy seguro de que nuestro problema pueda convertirse a esta forma. También afirman que se puede obtener una aproximación de casi 3,16 cuando la desigualdad del triángulo se cumple para cualquiera de las matrices. No estoy seguro de que sea así, ya que no soy capaz de convertir correctamente el problema en la forma dada.

7. Se puede obtener un límite superior para el problema utilizando la siguiente función objetivo: Maximizar $\sum_{i=1}^{n}\sum_{j=1}^n ||\boldsymbol v_{ij}||_2 x_{ij}$ y luego tomar el cuadrado del valor. Este límite superior se puede encontrar en tiempo polinómico, ya que es un problema de asignación de suma lineal estándar. Sin embargo, no parece plantear ninguna garantía sobre la función objetivo original si se utiliza la solución óptima para la función objetivo modificada. Tal vez la solución pueda mejorarse utilizando la nota 3.

Answer 1

El objetivo es una norma de un vector bidimensional. Mi enfoque sería considerar el problema como un problema multiobjetivo con dos objetivos, que son los elementos individuales del vector. Así, el primer objetivo es $\sum_{i=1}^{n}\sum_{j=1}^{n} (\boldsymbol{v}_{ij})_1 x_{ij}$ y el segundo objetivo es $\sum_{i=1}^{n}\sum_{j=1}^{n} (\boldsymbol{v}_{ij})_2 x_{ij}$ .

Si se maximiza una suma ponderada de los dos objetivos, se puede recuperar el Frontera de Pareto . Sea $\boldsymbol{w} \in \mathbb{R}^2$ sea un vector de pesos (sólo dos números que suman 1). El siguiente problema de optimización genera un punto en la frontera de Pareto (a menos que uno de los pesos sea $0$ ): \begin{align} \text{Maximize: }\quad &\sum_{i=1}^{n}\sum_{j=1}^{n} \boldsymbol{w}^T \boldsymbol{v}_{ij} x_{ij}\\ \text{such that: }\quad &\sum_{j=1}^n x_{ij} = 1, \quad \forall i = 1, \ldots,n\\ \quad &\sum_{i=1}^n x_{ij} = 1, \quad \forall j = 1, \ldots,n\\ &x_{ij}\in \{0,1\} \end{align}

La resolución de este problema de asignación lineal para una $\boldsymbol{w}$ le da una solución Pareto Óptima con valor objetivo $\sum_{i=1}^{n}\sum_{j=1}^{n} \boldsymbol{v}_{ij} x_{ij} \in \mathbb{R}^2$ . Resolviendo repetidamente este problema para variar $\boldsymbol{w}$ y trazando los valores objetivos en el plano, se obtiene la frontera de Pareto. Si introduces "método de la suma ponderada" y "pareto" en tu buscador favorito, encontrarás algunas lecturas de fondo. La razón por la que elegí el método de la suma ponderada para este problema es porque los subproblemas son problemas de asignación lineal.

Una vez que se han generado suficientes puntos, se elige el que tiene la norma más alta. Como sabes de antemano que vas a hacer esto, puedes utilizarlo para variar $\boldsymbol{w}$ de forma inteligente, centrándose en la parte de la superficie de Pareto donde estará la solución óptima.