Optimización de solicitudes cartesianas con costos afines

Question

Tengo una solicitud de optimización de costos sobre la cual no sé si hay literatura al respecto.Es un poco difícil de explicar, así que pido disculpas de antemano por la extensión de la pregunta.

Hay un servidor al que estoy accediendo que funciona de esta manera:

• se realiza una solicitud sobre registros (r1, ...rn) y campos (f1, ...fp)
• sólo puedes solicitar el producto cartesiano (r1,..., rp) x (f1,...fp)
• El costo (tiempo y dinero) asociado con dicha solicitud depende del tamaño de la solicitud:

T((r1, ..., rn)x(f1, ..., fp) = a + b * n * p

Sin pérdida de generalidad (simplemente normalizando), podemos suponer que b=1 entonces el costo es:

T((r1, ...,rn)x(f1,...fp)) = a + n * p

• Sólo necesito solicitar un subconjunto de pares. (r1, f(r1)), ... (rk, f(rk)), una petición que proviene de los usuarios.Mi programa actúa como intermediario entre el usuario y el servidor (que es externo).Tengo muchas solicitudes como esta que llegan (decenas de miles por día).

Gráficamente, podemos pensar en ella como una matriz dispersa de n x p, para la cual quiero cubrir los valores distintos de cero con una submatriz rectangular:

   r1 r2 r3 ... rp
   ------      ___
f1 |x  x|      |x|
f2 |x   |      ---
   ------
f3
..    ______
fn    |x  x|
      ------

Teniendo:

• el número de submatrices se mantiene razonable debido al costo constante
• todas las 'x' deben estar dentro de una submatriz
• El área total cubierta no debe ser demasiado grande debido al costo lineal.

Llamaré g al coeficiente de escasez de mi problema (número de pares necesarios sobre el total de pares posibles, g = k / (n * p).conozco el coeficiente a.

Hay algunas observaciones obvias:

• si a es pequeño, la mejor solución es solicitar cada par (registro, campo) de forma independiente y el costo total es: k * (a + 1) = g * n * p * (a + 1)
• Si a es grande, la mejor solución es solicitar el producto cartesiano completo y el coste total es: a + n * p
• la segunda solución es mejor tan pronto como g > g_min = 1/ (a+1) * (1 + 1 / (n * p))
• Por supuesto, los pedidos en los productos cartesianos no son importantes, por lo que puedo transponer las filas y las columnas de mi matriz para que sea más fácil de cubrir, por ejemplo:

   f1 f2 f3
r1  x    x
r2     x 
r3  x    x

se puede reordenar como

   f1 f3 f2
r1  x  x
r3  x  x
r2       x

Y hay una solución óptima que es solicitar (f1,f3) x (r1,r3) + (f2) x (r2)

• Probar todas las soluciones y buscar el menor coste no es una opción, porque la combinatoria explota:

for each permutation on rows: (n!)
   for each permutation on columns: (p!)
       for each possible covering of the n x p matrix: (time unknown, but large...)
           compute cost of the covering

entonces estoy buscando una solución aproximada.Ya tengo algún tipo de algoritmo codicioso que encuentra una cobertura dada una matriz (comienza con celdas unitarias y luego las combina si la proporción de celdas vacías en la combinación está por debajo de cierto umbral).

Para tener en cuenta algunos números, mi n está entre 1 y 1000, y mi p está entre 1 y 200.El patrón de cobertura es realmente "en bloques", porque los registros vienen en clases cuyos campos solicitados son similares.Lamentablemente no puedo acceder a la clase de un registro...

Pregunta 1:¿Alguien tiene una idea, una simplificación inteligente o una referencia para un artículo que podría resultar útil?Como tengo muchas solicitudes, un algoritmo que funciona bien. de media es lo que estoy buscando (pero no puedo permitirme que funcione muy mal en algún caso extremo, por ejemplo, solicitar la matriz completa cuando n y p son grandes, y la solicitud es bastante escasa).

Pregunta 2:De hecho, el problema es aún más complicado:De hecho, el costo se parece más a la forma: a + n * (p^b) + c * n' * p', donde b es una constante < 1 (una vez que a un registro se le solicita un campo, no es demasiado costoso solicitar otros campos) y n' * p' = n * p * (1 - g) es la cantidad de celdas que no quiero solicitar (porque no son válidas y hay un costo adicional al solicitar cosas no válidas).Ni siquiera puedo soñar con una solución rápida a este problema, pero aún así...alguien tiene una idea?

Answer 1

Seleccionar las submatrices para cubrir los valores solicitados es una forma de establecer problema de cobertura y por tanto NP completo.Su problema se suma a este ya difícil problema de que los costos de los juegos difieren.

Que permitas permutar las filas y columnas no es un problema tan grande, porque simplemente puedes considerar submatrices desconectadas.La fila uno, las columnas cuatro a siete y la fila cinco, las columnas cuatro dos siete son un conjunto válido porque puede simplemente intercambiar las filas dos y cinco y obtener la submatriz conectada fila uno, columna cuatro con la fila dos, columna siete.Por supuesto, esto agregará algunas restricciones (no todos los conjuntos son válidos bajo todas las permutaciones), pero no creo que este sea el mayor problema.

El artículo de Wikipedia da resultados de inaproximabilidad de que el problema no se puede resolver mejor en tiempo polinómico que con un factor. 0.5 * log2(n) dónde n es el número de conjuntos.En tu caso 2^(n * p) es un límite superior (bastante pesimista) para el número de conjuntos y rendimientos en los que solo se puede encontrar una solución hasta un factor de 0.5 * n * p en tiempo polinómico (además de N = NP e ignorando los costos variables).

Un límite inferior optimista para el número de conjuntos que ignoran las permutaciones de filas y columnas es 0.5 * n^2 * p^2 produciendo un factor mucho mejor de log2(n) + log2(p) - 0.5.En consecuencia, sólo puede esperar encontrar una solución en el peor de los casos. n = 1000 y p = 200 hasta un factor de aproximadamente 17 en el caso optimista y hasta un factor de aproximadamente 100.000 en el caso pesimista (todavía ignorando los diferentes costos).

Entonces, lo mejor que puede hacer es usar un algoritmo heurístico (el artículo de Wikipedia menciona un algoritmo codicioso casi óptimo) y aceptar que habrá casos en los que el algoritmo funcione (muy) mal.O vas por el otro lado y usas un algoritmo de optimización e intentas encontrar una buena solución usando más tiempo.En este caso sugeriría intentar usar Una búsqueda.

Answer 2

Estoy seguro de que hay un algoritmo realmente bueno para esto en alguna parte, pero aquí están mis propias ideas intuitivas:

1. Método de tirar algunos rectángulos:

   • Determine un " aproximadamente óptimo " tamaño del rectángulo basado en a .
   • Coloque estos rectángulos (quizás al azar) sobre sus puntos requeridos, hasta que todos los puntos estén cubiertos.
   • Ahora toma cada rectángulo y encogelo tanto como sea posible sin " perdiendo " cualquier punto de datos.
   • Encuentre rectángulos cerca uno del otro y decida si combinarlos sería más barato que mantenerlos separados.

2. Cultivar

   • Comience con cada punto en su propio rectángulo 1x1.
   • Localice todos los rectángulos dentro de n filas / columnas (donde n puede basarse en a ); vea si puede combinarlos en un rectángulo sin costo (o costo negativo: D).
   • Repita.

3. Reducir

   • Comience con un gran rectángulo, que cubra TODOS los puntos.
   • Busque un sub-rectángulo que comparta un par de lados con el grande, pero que contenga muy pocos puntos.
   • Córtalo del grande, produciendo dos rectángulos más pequeños.
   • Repita.

4. Cuádruple

   • Divide el plano en 4 rectángulos. Para cada uno de estos, vea si obtiene un mejor costo recurriendo más, o simplemente incluyendo todo el rectángulo.
   • Ahora tome sus rectángulos y vea si puede combinar alguno de ellos con poco o ningún costo. \

Además: tenga en cuenta que a veces será mejor tener dos rectángulos superpuestos que un rectángulo grande que es un superconjunto de ellos. P.ej. el caso cuando dos rectángulos se superponen en una esquina.

Answer 3

Ok, mi comprensión de la pregunta ha cambiado. Nuevas ideas:

• Almacene cada fila como una cadena de bits larga. Y pares de cadenas de bits juntas, tratando de encontrar pares que maximicen el número de 1 bits. Haga crecer estos pares en grupos más grandes (clasifique e intente unir los realmente grandes entre sí). Luego construya una solicitud que llegue al grupo más grande y luego se olvide de todos esos bits. Repita hasta que todo esté hecho. Tal vez cambie de filas a columnas a veces.

• Busque todas las filas / columnas con cero o pocos puntos en ellas. " Eliminar " ellos temporalmente. Ahora está viendo lo que cubriría una solicitud que los excluye. Ahora quizás aplique una de las otras técnicas, y luego trate con las filas / columnas ignoradas. Otra forma de pensar sobre esto es: primero trata los puntos más densos y luego pasa a los más dispersos.

Answer 4

Dado que sus valores son escasos, ¿podría ser que muchos usuarios soliciten valores similares?¿El almacenamiento en caché dentro de su aplicación es una opción?Las solicitudes podrían indexarse ​​mediante un hash que es función de la posición (x,y), de modo que pueda identificar fácilmente los conjuntos almacenados en caché que se encuentran dentro del área correcta de la cuadrícula.Almacenar los conjuntos en caché en un árbol, por ejemplo, le permitiría encontrar subconjuntos mínimos en caché que cubran el rango de solicitudes muy rápidamente.Luego puede realizar una búsqueda lineal en el subconjunto, que es pequeño.

Answer 5

Consideraría los n registros (filas) y p campos (cols) mencionados en la solicitud del usuario establecidos como n puntos en el espacio p-dimensional ({0,1} ^ p) con la i-ésima coordenada siendo 1 si es así tiene una X, y identifica una jerarquía de grupos , con el grupo más grueso en la raíz, incluidos todos la X. Para cada nodo en la jerarquía de agrupamiento, considere el producto que cubre todas las columnas necesarias (esto es filas (cualquier subnodo) x cols (cualquier subnodo)). Luego, decida de abajo hacia arriba si desea fusionar las cubiertas infantiles (pagando la cobertura completa), o guárdelas como solicitudes separadas. (los revestimientos no son de columnas contiguas, sino exactamente las necesarias; es decir, piense en un vector de bits)

Estoy de acuerdo con Artelius en que la superposición de solicitudes de productos podría ser más barata; mi enfoque jerárquico necesitaría mejoras para incorporar eso.

Answer 6

He trabajado un poco en ello, y aquí hay un algoritmo obvio, O (n ^ 3) codicioso, que rompe la simetría (los registros y los campos se tratan por separado) en un pseudocódigo similar a Python.

La idea es trivial: comenzamos probando una solicitud por registro, y hacemos la fusión más valiosa hasta que no quede nada digno de fusionar. Este algo tiene la desventaja obvia de que no permite solicitudes superpuestas, pero espero que funcione bastante bien en el caso de la vida real (con la función de costo a + n * (p^b) + c * n * p * (1 - g)):

# given are
# a function cost request -> positive real
# a merge function that takes two pairs of sets (f1, r1) and (f2, r2) 
# and returns ((f1 U f2), (r1 U r2))

# initialize with a request per record

requests = [({record},{field if (record, field) is needed}) for all needed records]
costs = [cost(request) for request in requests]

finished = False

while not finished: # there might be something to gain
    maximum_gain = 0
    finished = True
    this_step_merge = empty

    # loop onto all pairs of request
    for all (request1, request2) in (requests x request) such as request1 != request2:
        merged_request = merge(request1, request2)
        gain = cost(request1) + cost(request2) - cost(merged_request)

        if gain > maximum_gain:
            maximum_gain = gain
            this_step_merge = (request1, request2, merged_request)

    # if we found at least something to merge, we should continue
    if maximum_gain > 0:
        # so update the list of requests...
        request1, request2, merged_request = this_step_merge
        delete request1 from requests
        delete request2 from requests
        # ... and we are not done yet
        insert merged_request into requests
        finished = False

output requests

Esto es O (n3 * p) porque:

• después de la inicialización comenzamos con n solicitudes
• el bucle while elimina exactamente una solicitud del grupo en cada iteración.

• el bucle for interno itera en los (ni^2 - ni) / 2 pares distintos de solicitudes, con ni yendo de n a uno en el peor de los casos (cuando fusionamos todo en una gran solicitud).

  1. ¿Puede alguien ayudarme a señalar los casos muy malos del algoritmo? ¿Suena razonable usar este?
  2. Es O (n ^ 3) que es demasiado costoso para entradas grandes. ¿Alguna idea para optimizarlo?

¡Gracias de antemano!