Minimiza el componente máximo de una suma de vectores

Me gustaría aprender algo sobre este problema de optimización: para números enteros no negativos dados , encuentre una función minimice la expresión $a_{i,j,k}$ $f$

max_{k} \sum_{i} a_{i, f (i), k}

$\max_k \sum_i a_{i,f(i),k}$

Un ejemplo que utilice una formulación diferente podría aclararlo: se le da un conjunto de conjuntos de vectores como

{
    {(3, 0, 0, 0, 0), (1, 0, 2, 0, 0)},
    {(0, 1, 0, 0, 0), (0, 0, 0, 1, 0)},
    {(0, 0, 0, 2, 0), (0, 1, 0, 1, 0)}
}

Elija un vector de cada conjunto, de modo que el componente máximo de su suma sea mínimo. Por ejemplo, puedes elegir

(1, 0, 2, 0, 0) + (0, 1, 0, 0, 0) + (0, 1, 0, 1, 0) = (1, 1, 2, 1, 0)

con el componente máximo igual a 2, que es claramente óptimo aquí.

Tengo curiosidad por saber si este es un problema bien conocido y qué métodos de solución aproximada específicos del problema están disponibles. Debe ser rápido y fácil de programar (sin solucionador de ILP , etc.). No se necesita una solución exacta ya que es solo una aproximación del problema real.

Veo que debería haber agregado algunos detalles sobre las instancias del problema que me interesan:

$i \in \{0, 1, \ldots, 63\}$ , es decir, siempre hay 64 filas (cuando se escribe como en el ejemplo anterior).
$j \in \{0, 1\}$ , es decir, solo hay 2 vectores por fila.
$k \in \{0, 1, \ldots, N-1\}$ donde (la longitud del vector) está entre 10 y 1000. $N$

Además, en cada fila la suma de los elementos de todos los vectores es la misma, es decir,

\forall i, j, j^{'} : \sum_{k} a_{i, j, k} = \sum_{k} a_{i, j^{'}, k}

$\forall i, j, j':\quad \sum_k a_{i,j,k} = \sum_k a_{i,j',k}$

y la suma de los elementos del vector suma es menor que su longitud, es decir,

\sum_{k} \sum_{i} a_{i, f (i), k} < N

$\sum_k \sum_i a_{i,f(i),k} < N$

algorithms optimization linear-programming maaartinus
fuente

No es difícil reducir el problema de 3 particiones a su problema. Esto significa que su problema es NP-completo incluso si los números se dan en unario, y esto descarta uno de los enfoques comunes para un algoritmo de aproximación.

Tsuyoshi Ito

Gracias por las correcciones y gracias a @Tsuyoshi Ito por la información. Si lo entiendo correctamente, la restricción a dos vectores por línea (que olvidé indicar) invalida la reducción y puede facilitar el problema.

maaartinus

Tiene razón, la reducción del problema de 3 particiones en el que estaba pensando no funciona si solo hay dos vectores por fila.

Tsuyoshi Ito

¿Entonces hay combinaciones para comparar?

j^{i}

$j^i$

Jason Kleban

@ uosɐſ: Para ser precisos, hay combinaciones posibles, donde es el número de posibilidades para e es el número de posibilidades para .

J^{I} = 2^{64}

$J^I=2^{64}$

J = 2

$J=2$

j

$j$

I = 64

$I=64$

i

$i$

maaartinus

Respuestas:

Reducción de 3SAT a la versión de dos vector: dada una fórmula, deje variables de índice, , y cláusulas de índice. Sea la cantidad de veces que la variable aparece positiva (si ) o negativa (si ) en la cláusula . OPT es menor que si la fórmula es satisfactoria (la biyección es obvia). $i$ $j \in \{0,1\}$ $k$ $a_{i,j,k}$ $i$ $j = 0$ $j = 1$ $k$ $3$

Cómo atacaría este problema: búsqueda de vecindario grande. Comience con cualquier solución. Elija filas al azar. Use la fuerza bruta para encontrar la mejor solución donde pueda cambiar solo en esas filas, muy factible incluso para moderado dado que el tamaño del problema es de filas. Repetir. $r$ $f$ $k$ $64$

hola mods
fuente

Esta es una hermosa reducción. No estoy seguro de por qué no tiene ningún voto positivo. De todos modos, aquí está mi +1.

Tsuyoshi Ito

Creo que deberías elaborar un poco más sobre la reducción. En particular, tiene ocultos bueno, tal vez demasiado bien, ya que hace que la biyección un poco difícil de ver.

f

$f$

Raphael

No podemos discutir la complejidad de un problema cuando el tamaño del problema se fija a una constante, porque (la mayor parte de) la teoría de la complejidad se ocupa del comportamiento asintótico de la complejidad del problema, ya que el tamaño del problema tiende al infinito. Aquí, considero tanto el número de filas como la dimensión de los vectores como variables.

Entonces el problema es NP-completo incluso si los números en la entrada se dan en unario. Esta no es una respuesta a su pregunta porque está preguntando acerca de la aproximación, pero es algo.

Defina el problema rigurosamente:

Instancia : n pares de vectores a _i , b _i ∈ ℕ ^m ( i ∈ {1, ..., n }) y K ∈ ℕ, todos en unario.
Pregunta : ¿Podemos elegir a _i o b _i para cada i para que la suma de estos n vectores tenga como máximo K en cada coordenada?

El siguiente es un problema conocido de NP-complete llamado 3-partición :

Instancia de 3 particiones : B ∈ ℕ, y 3 k enteros c ₁ , ..., c _{3 k} entre B / 4 y B / 2, exclusivo, de modo que ∑ _{i = 1}^{3 k} c _i = kB , todo en unario.
Pregunta : ¿Se puede dividir el multiset { c ₁ , ..., c _{3 k} } en k multisets S ₁ , ..., S _{k de} modo que la suma de cada S _j sea igual aB ?

Dada una instancia ( B ; c ₁ , ..., c _{3 k} ) del problema de 3 particiones, construya una instancia del problema anterior de la siguiente manera. Para cada i = 1, ..., 3 k y j = 1, ..., k , construiremos un par de 4 k -dimensionales vectores, representando la elección de si c _i pertenece a S _j o no:

El vector que representa la opción " c _i ∈ S _j " tiene solo una entrada distinta de cero, que es ( k −1) c _i en la coordenada j .
El vector que representa la opción " c _i ∉ S _j " también tiene solo una entrada distinta de cero, que es B en la coordenada ( k + i ).

No es difícil ver que la instancia ( B ; c ₁ , ..., c _{3 k} ) del problema de 3 particiones tiene una solución si y solo si hay una manera de elegir un vector de cada uno de los 3 k ² construidos parejas, de modo que todas las coordenadas de la suma de estos vectores son a lo sumo ( k -1) B . (De hecho, cuando esto sucede, todas las coordenadas de la suma son iguales a ( k −1) B. ) Entonces, esta es una reducción del problema de 3 particiones al problema anterior.

Hasta ahora, ignoré las dos restricciones adicionales establecidas al final de la pregunta, pero ambas son fáciles de aplicar modificando ligeramente esta reducción. La condición de que la suma de los elementos de cada vector sea igual puede hacerse cumplir agregando coordenadas ficticias que contengan solo 0 o 1. La condición de que esta suma sea menor que la dimensión puede hacerse cumplir agregando coordenadas ficticias que contengan solo 0.

Tsuyoshi Ito
fuente

Buena respuesta, solo algunas notas: 1. No me importa la complejidad teórica aquí. 2. El número de filas es fijo y puede permanecer así, ya que basta con variable . Dicho eso, muchas gracias.

N

$N$

maaartinus