algorithm - simplex - programacion lineal metodo grafico ejercicios resueltos

¿Cómo resolver este problema de programación lineal? (3)

¿Es el cache en espiral una analogía con la solución? http://strumpen.net/ibm-rc24767.pdf

No soy tan bueno en programación lineal, así que estoy publicando este problema aquí. Espero que alguien pueda indicarme la dirección correcta. No es un problema de tarea, así que no malinterprete.

Tengo una matriz 5x5 (25 nodos) . La distancia entre cada nodo y sus nodos adyacentes (o nodos vecinos) es 1 unidad . Un nodo puede estar en 1 de 2 condiciones: caché o acceso . Si un nodo ''i'' es un nodo de caché, un nodo de acceso ''j'' puede acceder a él con un costo de Dij x Aij (costo de acceso) . Dij es la distancia de Manhattan entre los nodos i y j. Aij es la frecuencia de acceso del nodo i al j.

Para convertirse en un nodo i de caché, debe almacenarse en caché desde un nodo k de caché existente con un costo de Dik x C, donde C es una constante Integer. (Costo de caché) . C se llama frecuencia de almacenamiento en caché.

A se proporciona como una matriz de 25x25 que contiene todos los enteros que muestran la frecuencia de acceso entre cualquier par de nodos i y j. D se proporciona como una matriz de 25x25 que contiene todas las distancias de Manhattan entre cualquier par de nodos i y j.

Suponga que hay 1 nodo de caché en la matriz, averigüe el conjunto de otros nodos de caché y los nodos de acceso, de modo que el costo total se minimice. Costo total = Costo total de caché + Costo total de acceso .

He abordado algunos problemas que son algo como esto.

Primero, si no necesita una respuesta exacta, generalmente sugeriría buscar algo como un algoritmo genético o hacer un algoritmo codicioso. No estará bien, pero tampoco será malo en general. Y será mucho más rápido que un algoritmo exacto. Por ejemplo, puede comenzar con todos los puntos como puntos de caché, luego busque el punto que reduzca más su costo al convertirlo en un punto que no sea de caché. Continúe hasta que eliminar el siguiente haga que el costo aumente, y use eso como su solución. Esto no será lo mejor. Generalmente será razonablemente bueno.

Si necesita una respuesta exacta, deberá realizar una búsqueda brusca de una gran cantidad de datos. Suponiendo que se especifique el punto de caché inicial, tendrá 2 ²⁴ = 16,777,216 posibles conjuntos de puntos de caché para buscar. Eso es costoso.

El truco para hacerlo de forma más económica (tenga en cuenta, no de manera barata, sino de forma más económica) es encontrar formas de eliminar su búsqueda. Tome en serio el hecho de que si realiza 100 veces más trabajo en cada conjunto que mire, le permite eliminar un promedio de 10 puntos de consideración como puntos de caché, entonces su algoritmo general obtendrá un 0.1% de la cantidad de conjuntos y su código se ejecutará 10 veces más rápido. Por lo tanto, vale la pena poner una cantidad sorprendente de energía en la poda temprano y con frecuencia, incluso si el paso de la poda es bastante caro.

A menudo se quieren múltiples estrategias de poda. Uno de ellos suele ser "lo mejor que podemos hacer desde aquí es peor que lo mejor que hemos encontrado anteriormente". Esto funciona mejor si ya has encontrado una mejor solución bastante buena. Por lo tanto, a menudo vale la pena hacer un poco de esfuerzo para hacer una optimización local en su búsqueda de soluciones.

Por lo general, estas optimizaciones no cambiarán el hecho de que estás haciendo una gran cantidad de trabajo. Pero sí te dejan hacer órdenes de magnitud menos trabajo.

Mi primer intento de esto aprovecharía las siguientes observaciones.

Supongamos que x es un punto de caché, y y es su vecino de almacenamiento en caché más cercano. Entonces, siempre puede hacer una ruta desde la memoria caché de x a y "de forma gratuita" si simplemente enruta el tráfico de actualización de la memoria caché de x a y largo de esa ruta. Por lo tanto, sin pérdida de generalidad, el conjunto de puntos de caché está conectado a la cuadrícula.
Si el costo mínimo podría terminar y excede el mejor costo actual que hemos encontrado, no estamos en el camino hacia una solución global.
Tan pronto como la suma de la tasa de acceso desde todos los puntos a una distancia mayor que 1 desde los puntos de caché más la frecuencia de acceso más alta de un vecino al punto de caché que aún puede usar es menor que la frecuencia de caché, agregar más puntos de caché es Siempre va a ser una pérdida. (Esto sería una "condición costosa que nos permite detenernos 10 minutos antes").
El vecino de acceso más alto del conjunto actual de puntos de caché es un candidato razonable para el próximo punto de caché a probar. (Hay varias otras heurísticas que puedes probar, pero esta es razonable).
Cualquier punto cuya frecuencia de acceso total supere la frecuencia de caché debe ser un punto de almacenamiento en caché.

Este podría no ser el mejor conjunto de observaciones para usar. Pero es probable que sea bastante razonable. Para aprovechar esto, necesitará al menos una estructura de datos con la que no esté familiarizado. Si no sabe qué es una cola de prioridad , busque una eficiente en el idioma que elija. Si no puede encontrar uno, un heap es bastante fácil de implementar y funciona bastante bien como una cola de prioridad.

Con esto en mente, asumiendo que se le ha dado la información que ha descrito y un nodo P caché inicial, aquí hay un pseudocódigo para que un algoritmo encuentre el mejor.

# Data structures to be dynamically maintained: # AT[x, n] - how many accesses x needs that currently need to go distance n. # D[x] - The distance from x to the nearest cache node. # CA[x] - Boolean yes/no for whether x is a cache node. # B[x] - Boolean yes/no for whether x is blocked from being a cache node. # cost - Current cost # distant_accesses - The sum of the total number of accesses made from more than # distance 1 from the cache nodes. # best_possible_cost - C * nodes_in_cache + sum(min(total accesses, C) for non-cache nodes) # *** Sufficient data structures to be able to unwind changes to all of the above before # returning from recursive calls (I won''t specify accesses to them, but they need to # be there) # best_cost - The best cost found. # best_solution - The best solution found. initialize all of those data structures (including best) create neighbors priority queue of neighbors of root cache node (ordered by accesses) call extend_current_solution(neighbors) do what we want with the best solution function extend_current_solution (available_neighbors): if cost < best_cost: best_cost = cost best_solution = CA # current set of cache nodes. if best_cost < best_possible_cost return # pruning time neighbors = clone(available_neighbors) while neighbors: node = remove best from neighbors if distant_accesses + accesses(node) < C: return # this is condition 3 above make node in cache set - add it to CA - update costs - add its immediate neighbors to neighbors call extend_current_solution unwind changes just made make node in blocked set call extend_current_solution unwind changes to blocked set return

Tomará mucho trabajo escribir esto, y deberá tener cuidado de mantener todas las estructuras de datos. Pero mi apuesta es que, a pesar de lo pesado que sea, encontrará que poda su espacio de búsqueda lo suficiente como para ejecutarse más rápidamente que su solución existente. (Todavía no será rápido.)

¡Buena suerte!

Actualizar

Cuando pensé más en esto, me di cuenta de que una mejor observación es tener en cuenta que si puedes cortar el conjunto de "no un nodo de caché, ni un nodo bloqueado" en dos partes, entonces puedes resolver esas piezas de forma independiente. Cada uno de esos problemas secundarios es un orden de magnitud más rápido de resolver que todo el problema, así que procure hacerlo lo más rápido posible.

Una buena heurística para hacer eso es seguir las siguientes reglas:

Si bien no se ha alcanzado ningún borde:
1. Conduzca hacia el borde más cercano. La distancia se mide por lo corta que es la ruta más corta a lo largo del conjunto no bloqueado, sin caché.
2. Si dos bordes son equidistantes, rompa los lazos de acuerdo con el siguiente orden de preferencia: (1, x), (x, 1), (5, x), (x, 5) .
3. Rompa los lazos restantes según prefiera conducir hacia el centro de un borde.
4. Romper cualquier lazo restante al azar.
Si bien se ha alcanzado un borde y su componente aún tiene bordes que podrían convertirse en piezas de caché:
1. Si puede moverse de inmediato hacia un borde y dividir las piezas de borde en dos componentes, hágalo. Tanto para "edge in cache set" como para "edge not in cache set" obtendrás 2 subproblemas independientes que son más manejables.
2. De lo contrario, muévase en un camino más corto hacia la pieza en el centro de la sección de piezas de borde.
3. Si hay un empate, divídalo a favor de lo que hace que la línea de la pieza agregada al elemento de caché agregado esté lo más cerca posible de la diagonal.
4. Romper cualquier lazo restante al azar.
Si caes por aquí, elige al azar. (Debería tener un subproblema bastante pequeño en este momento. No es necesario ser inteligente).

Si intenta esto comenzando con (3, 3) como punto de caché, encontrará que en las primeras decisiones encontrará que 7/16 de las veces que logra cortar en dos problemas, 1/16 del tiempo que bloquea en el punto de caché y finalice, 1/4 del tiempo que logra cortar un bloque 2x2 en un problema separado (haciendo que la solución general se ejecute 16 veces más rápido para esa pieza) y 1/4 del tiempo terminas bien en tu camino hacia una solución que está en camino hacia ser encajonada (y rápidamente agotada), o bien ser candidata para una solución con una gran cantidad de puntos de caché que son eliminados por estar en camino de ser un mala solución

No daré pseudocódigo para esta variación. Tendrá muchas similitudes con lo que tenía arriba, con una serie de detalles importantes que manejar. Pero estaría dispuesto a apostar dinero que, en la práctica, se ejecutará en órdenes de magnitud más rápido que su solución original.

La solución es un conjunto, por lo que este no es un problema de programación lineal. Lo que es es un caso especial de ubicación de instalaciones conectadas. Bardossy y Raghavan tienen una heurística que parece prometedora: http://terpconnect.umd.edu/~raghavan/preprints/confl.pdf