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

En matemáticas, el problema de asignación de cuellos de botella cuadráticos ( QBAP ) es uno de los problemas fundamentales de optimización combinatoria en la rama de optimización o investigación de operaciones , de la categoría de problemas de localización de instalaciones . ^{[ 1 ]}

Está relacionado con el problema de asignación cuadrática de la misma manera que el problema de asignación de cuello de botella lineal está relacionado con el problema de asignación lineal , la "suma" se reemplaza por "máximo" en la función objetivo .

El problema modela el siguiente problema de la vida real:

Se dispone de 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, un peso o flujo (por ejemplo, la cantidad de suministros transportados entre las dos instalaciones). El problema consiste en asignar todas las instalaciones a ubicaciones diferentes con el objetivo de minimizar el máximo de las distancias multiplicadas por los flujos correspondientes.

El problema es NP-difícil , ya que puede utilizarse para formular el problema del ciclo hamiltoniano mediante el uso de flujos con el patrón de un ciclo y distancias que son cortas para las aristas del grafo y largas para las no aristas. ^{[ 2 ]}

• Problema del viajante con cuello de botella
• Problema de ancho de banda de grafos