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 , de la categoría de problemas de ubicación de instalaciones introducidos por primera vez por Koopmans y Beckmann. ^[1]

El problema modela el siguiente problema de la vida real:

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

Intuitivamente, la función de costo incentiva a que las instalaciones con altos flujos entre sí se ubiquen cerca unas de otras.

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

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

Dados dos conjuntos, P ("instalaciones") y L ("ubicaciones"), 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 . Halla la biyección f  : P → L ("asignación") tal que la función de costo:

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

se minimiza.

Generalmente, las funciones de peso y distancia se consideran matrices cuadradas de valores reales , 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} (WXD^{T}X^{T})}$

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

El problema es NP-hard , por lo que no se conoce ningún algoritmo para resolver este problema en tiempo polinomial, 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 polinomial para ningún factor (constante), a menos que P = NP. ^[2] El problema del viajante de comercio (TSP) puede verse como un caso especial de QAP si se supone que los flujos conectan todas las instalaciones solo a lo largo de un solo anillo, todos los flujos tienen el mismo valor distinto de cero (constante) y todas las distancias son iguales a las distancias respectivas de la instancia TSP. Muchos otros problemas de optimización combinatoria estándar pueden escribirse en esta forma.

Además de la formulación original de ubicación de 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.

El QAP también se ha utilizado para modelar el coste de la colocación de caracteres en un teclado. En este caso, las ubicaciones son teclas del teclado y sus distancias por pares corresponden al tiempo necesario para pulsar un par de teclas determinado. Las instalaciones son caracteres y sus pesos son proporcionales a la frecuencia con la que aparece el par de caracteres determinado en un corpus de texto. Este tipo de modelo QAP se utilizó en el diseño del estándar de teclado francés (NF Z71-300). ^[3]

• Problema de asignación de cuello de botella cuadrático

• Michael R. Garey y David S. Johnson (1979). Computadoras e intratabilidad: una guía para la teoría de la NP-completitud . WH Freeman. ISBN 0-7167-1045-5.A2.5: ND43, pág.218.

• https://doi.org/10.7488/ds/3428 QAPLIB - Una biblioteca de problemas de asignación cuadrática
• http://www.wiomax.com/team/xie/maos-qap-quadratic-assignment-problem-project-portal/ MAOS-QAP: solucionador de problemas de asignación cuadrática basado en Java
• https://CRAN.R-project.org/package=qap - Paquete R qap: Heurísticas para el problema de asignación cuadrática
• https://apps.microsoft.com/store/detail/qapsolver/9N7WMCFB6NZZ - Solucionador QAP metaheurístico para Windows 10/11