Problema de asignación cuadrática

El problema de asignación cuadrática (QAP) es uno de los problemas de optimización combinatoria fundamentales en la rama de la optimización o investigación de operaciones en matemáticas, desde la categoría de localización de instalaciones. Problemas introducidos por primera vez por Koopmans y Beckmann.

El problema modela el siguiente problema de la vida real:

Hay un conjunto de n instalaciones y un conjunto de n localizaciones. Para cada par de ubicaciones, un distancia se especifica y para cada par de instalaciones a peso o flujo se especifica (por ejemplo, la cantidad de suministros transportados entre las dos instalaciones). El problema es asignar todas las instalaciones a diferentes lugares con el objetivo de minimizar la suma de las distancias multiplicadas por los flujos correspondientes.

Intuitivamente, la función de costos fomenta que las instalaciones con altos flujos entre sí se coloquen cerca unas de otras.

El planteamiento del problema se parece al del problema de asignación, excepto que la función de costos se expresa en términos de desigualdades cuadráticas, de ahí el nombre.

Definición matemática formal

La definición formal del problema de asignación cuadrática es la siguiente:

Dados dos sets, P ("facilidades") y L ("localizaciones"), de igual tamaño, junto con una función de peso w: P × P → R y una función de distancia d: L × L → R. Encuentra la bijeción f: P → L ("asignación") tal que la función de coste:

${\displaystyle \sum _{a,b\in P}w(a,b)\cdot d(f(a),f(b)}$

se minimiza.

Por lo general, las funciones de peso y distancia se consideran matrices cuadradas de valor real, de modo que la función de costo se escribe como:

${\displaystyle \sum _{a,b\in P}w_{a,b}d_{f(a),f(b)}}$

En notación matricial:

${\displaystyle \min _{X\in \Pi _{n}\operatorname {trace} (WXDX^{T})}$

Donde ${\displaystyle \Pi _{n}$ es el conjunto de ${\displaystyle n\times n}$ matrices de permutación, ${\displaystyle W.$ es la matriz de peso y ${\displaystyle D}$ es la matriz de distancia.

Complejidad computacional

El problema es NP-difícil, por lo que no existe ningún algoritmo conocido para resolver este problema en tiempo polinómico, e incluso las instancias pequeñas pueden requerir un tiempo de cálculo prolongado. También se demostró que el problema no tiene un algoritmo de aproximación que se ejecute en tiempo polinómico para ningún factor (constante), a menos que P = NP. El problema del viajante (TSP) puede verse como un caso especial de QAP si se supone que los flujos conectan todas las instalaciones sólo a lo largo de un único anillo, todos los flujos tienen el mismo valor distinto de cero (constante) y todas las distancias son iguales al distancias respectivas de la instancia de TSP. Muchos otros problemas de optimización combinatoria estándar se pueden escribir de esta forma.

Aplicaciones

Además de la formulación original de ubicación de la planta, QAP es un modelo matemático para el problema de colocación de componentes electrónicos interconectados en una placa de circuito impreso o en un microchip, que es parte de la etapa de ubicación y ruta del diseño asistido por computadora en la industria electrónica.