problema de asignación multidimensional

El problema de asignación multidimensional (MAP) es un problema fundamental de optimización combinatoria introducido por William Pierskalla . ^{[ 1 ]} Este problema puede considerarse una generalización del problema de asignación lineal . ^{[ 2 ]} En otras palabras, el problema puede describirse de la siguiente manera:

Una instancia del problema tiene un número de agentes (es decir, parámetro de cardinalidad ) y un número de características de trabajo (es decir, parámetro de dimensionalidad ) tales como tarea, máquina, intervalo de tiempo, etc. Por ejemplo, se puede asignar a un agente para realizar la tarea X, en la máquina Y, durante el intervalo de tiempo Z. Cualquier agente puede ser asignado para realizar un trabajo con cualquier combinación de características de trabajo únicas a un cierto costo . Estos costos pueden variar según la asignación del agente a una combinación de características de trabajo: tarea específica, máquina, intervalo de tiempo, etc. El problema es minimizar el costo total de asignar los agentes de manera que la asignación de agentes a cada característica de trabajo sea una función inyectiva , o una función uno a uno de los agentes a una característica de trabajo dada.

Alternativamente, se puede describir el problema utilizando la teoría de grafos:

El problema de asignación multidimensional consiste en encontrar, en un grafo multipartito ponderado , un emparejamiento de un tamaño dado, en el que la suma de los pesos de las aristas sea mínima. ^{[ 3 ]}

En la literatura se pueden encontrar diversas formulaciones de este problema. Utilizando funciones de costo, el${\displaystyle D}$– problema de asignación dimensional (o${\displaystyle D}$– MAP ) se puede expresar de la siguiente manera:

Dado${\displaystyle D}$conjuntos,${\displaystyle A}$y${\displaystyle J_{1},\ldots J_{D-1}}$, de igual tamaño, junto con una matriz de costos o una función de ponderación multidimensional${\displaystyle C}$ :${\displaystyle A\times J_{1}\times \ldots \times J_{D-1}\rightarrow \mathbb {R} _{+}}$, encontrar${\displaystyle D-1}$permutaciones${\displaystyle \pi _{d}}$ : A →${\displaystyle J_{d}}$de tal manera que la función de costo total :

${\displaystyle \sum _{a\in A}C(a,\pi _{1}(a),\ldots ,\pi _{D-1}(a))}$

se minimiza. ^{[ 4 ]}

El problema es generalmente NP-difícil . En otras palabras, no se conoce ningún algoritmo para resolver este problema en tiempo polinomial, por lo que puede requerirse un tiempo de cálculo prolongado incluso para resolver instancias del problema de tamaño moderado (según los parámetros de dimensionalidad y cardinalidad). ^{[ 5 ]}

El problema encontró aplicación en muchos ámbitos:

• Programación (procesos de producción) ^{[ 1 ]}
• Fusión de datos multisensor ^{[ 6 ]}
• Vinculación de registros o resolución de entidades multipartitas ^{[ 2 ]}
• Física de partículas elementales ^{[ 7 ]}
• Detección de caídas en ancianos con pequeños dispositivos portátiles ^{[ 8 ]}