Optimización de solicitudes cartesianas con costos afines

Question

Tengo una solicitud de optimización de costos que no sé cómo si hay literatura. Es un poco difícil de explicar, así que me disculpo de antemano por la duración de la pregunta.

Hay un servidor accedo que funciona de esta manera:

• se realiza una solicitud de registros (R1, ... rn) y campos (F1, ... fp)
• se solo puede solicitar el producto cartesiano (r1, ..., rp) x (f1, ... fp)
• El costo (tiempo y dinero) asociado con una solicitud de este tipo es afín en el tamaño de la solicitud:

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

Sin pérdida de generalidad (sólo normalización), podemos suponer que b=1 lo que el costo es:

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

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

Gráficamente, podemos pensar en ella como una matriz dispersa NXP, por lo que quiero para cubrir los valores distintos de cero con una submatriz rectangular:

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

Tener:

• el número de submatrices se mantienen razonables debido al costo constante
• toda la 'x' debe encontrarse dentro de una submatriz
• el área total cubierta no debe ser demasiado grande debido al costo lineal

voy a nombrar g del coeficiente de diseminación de mi problema (número de pares necesarios sobre el total de pares posibles, g = k/(n * p). Sé el coeficiente a.

Hay algunas observaciones obvias:

• si a es pequeña, la mejor solución es solicitar cada uno (registro, campo) par 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 todo el producto cartesiano, y el costo 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, las órdenes en los productos cartesianos son unimporta nt, por lo que puede transponer las filas y las columnas de mi matriz para que sea más fácil que se puede cubrir, por ejemplo:

 
    f1 f2 f3 
r1 x x 
r2  x 
r3 x x 

pueden reordenarse como

 
    f1 f3 f2 
r1 x x 
r3 x x 
r2  x 

y no hay una solución óptima el cual es solicitar (f1,f3) x (r1,r3) + (f2) x (r2)

• Tratar todas las soluciones y buscando el menor coste no es una opción, debido a que los explotan combinatoria:

 
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 

así que 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, luego las combina si la proporción de celdas vacías en la fusión está por debajo de algún umbral).

Para poner algunos números en mi mente, mi n está en algún lugar entre 1 y 1000, y mi p en algún lugar entre 1 y 200. El patrón de cobertura es realmente 'blocky', porque los registros vienen en clases para las cuales los campos son similar. 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 documento que podría ser útil? Como tengo muchas solicitudes, un algoritmo que funciona bien en promedio es lo que estoy buscando (pero no puedo permitirme que funcione muy mal en algunos casos extremos, por ejemplo solicitando la matriz completa cuando nyp son grandes, y la solicitud es de hecho bastante escasa).

Pregunta 2: De hecho, el problema es aún más complicado: el costo es de hecho más como la forma: a + n * (p^b) + c * n' * p', donde b es una constante < 1 (una vez que se le pide un récord para un campo, es no es demasiado costoso para solicitar otros campos) y n' * p' = n * p * (1 - g) es el número de células que no deseo solicitar (porque no son válidas, y existe un costo adicional al solicitar elementos no válidos). Ni siquiera puedo soñar con una solución rápida a este problema, pero aún así ... ¿una idea para alguien?

Answer 1

Selección de las submatrices para cubrir los valores solicitados es una forma de la set covering problem y por lo tanto NP completo. Su problema se suma a este problema ya difícil que los costos de los conjuntos difieren.

Que permita permuta las filas y columnas no es un problema tan grande, ya que puede considerar submatrices desconectadas. Fila uno, columnas cuatro a siete y fila cinco, columnas cuatro dos siete son un conjunto válido porque puede simplemente cambiar la fila dos y fila cinco y obtener la submatriz conectada fila uno, columna cuatro a 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 los resultados de inapproximability que el problema no se puede resolver en tiempo polinomial mejor que con un factor 0.5 * log2(n) donde n es el número de conjuntos. En su caso, 2^(n * p) es un límite superior (bastante pesimista) para el número de conjuntos y rendimientos de que solo puede encontrar una solución hasta un factor de 0.5 * n * p en tiempo polinomial (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 rindiendo un factor mucho mejor de log2(n) + log2(p) - 0.5. En consecuencia, solo puede esperar encontrar una solución en su peor caso de 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 (aún ignorando los costos variables).

Así que 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 que el algoritmo se comporte (muy) mal. O ir por el otro lado y utilizar un algoritmo de optimización e intentar encontrar una buena solución utilizando más tiempo. En este caso, sugeriría intentar usar A* search.

Answer 2

Estoy seguro de que hay un muy buen algoritmo para esta ahí fuera en alguna parte, pero aquí están mis propias ideas intuitivas:

1. enfoque

   Toss-alguna-rectángulos:

   • determinar una " aproximadamente "tamaño de rectángulo óptimo" basado en a.
   • Coloque estos rectángulos (quizás al azar) sobre los puntos requeridos, hasta cubrir todos los puntos.
   • Ahora tome cada rectángulo y encoja tanto como sea posible sin "perder" ningún punto de datos.
   • Encuentra rectángulos cercanos entre sí y decide si combinarlos sería más económico que mantenerlos separados.

2. Grow

   • empezar con cada punto en su propio rectángulo de 1x1.
   • Busque 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. encogen

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

4. Quad

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

también:. tener en cuenta que a veces será mejor tener dos superposición rectángulos que un rectángulo grande que es un superconjunto de ellos. P.ej. el caso cuando dos rectángulos simplemente se superponen en una esquina.

Answer 3

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 iff tiene una X y identify a hierarchy of clusters, con el clúster más grueso en la raíz, incluidas todas las X. Para cada nodo en la jerarquía de clústeres, 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 fusionar las coberturas para niños (pagando la cobertura completa) o mantenerlas como solicitudes separadas. (las cubiertas no son de columnas contiguas, sino exactamente las necesarias, es decir, piense en un vector de bits)

Estoy de acuerdo con Artelius en que las solicitudes de productos superpuestas podrían ser más baratas; mi enfoque jerárquico necesitaría mejorar para incorporar eso.

Answer 4

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

Answer 5

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

• Almacena 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 y trate de unir los realmente grandes). Luego crea una solicitud que golpee al grupo más grande y luego olvídate 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" temporalmente. Ahora está viendo qué cubriría una solicitud que los excluye. Ahora quizás aplique una de las otras técnicas, y luego trate las filas/columnas ignoradas. Otra forma de pensar sobre esto es tratar primero con los puntos más densos y luego pasar a los más escasos.

Answer 6

He trabajado un poco en esto, y aquí hay un obvio, O (n^3) codicioso, algoritmo de ruptura de simetría (los registros y los campos se tratan por separado) en pseudo-código tipo pitón.

La idea es trivial: comenzamos probando una solicitud por registro, y hacemos la fusión más valiosa hasta que no quede nada que valga la pena fusionar.Este algo tiene el inconveniente obvio que no permite que las solicitudes se solapan, pero esperar que funcione muy bien en el caso de la vida real (con la función a + coste 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 

Esta es O (n3 * p) porque:

• después de la inicialización empezamos con n solicitudes
• el bucle while elimina exactamente una petición de la piscina en cada iteración.

• el ciclo interno for repite en (ni^2 - ni)/2 pares distintos de solicitudes, con ni pasando de n a uno en el peor de los casos (cuando fusionamos todo en una solicitud grande).

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

Gracias de antemano!