Resumen de Eficiencia y estructuras dinámicas: Puntos Pareto enteros
El problema que planteamos en nuestro trabajo es la búsqueda de los puntos eficientes enteros de un poliedro, aplicando una generalización de los métodos de enumeración implícita y usando estructuras dinámicas. ... -family: 'Times New Roman','serif'; font-size: 12pt">Dichos métodos enumerativos son desarrollados para ser aplicados a problemas lineales aunque no sean del tipo cero-uno, y la enumeración implícita se hace sobre un entorno de la superficie eficiente del poliedro.Las obtención de los puntos eficientes, exige disponer de estructuras dinámicas de datos adecuadas, que filtren dichos puntos de entre los enumerados, para que en cada momento, el espacio requerido sea mínimo.Las dificultades que aparecen en el proceso, aparte del manejo de las estructuras de datos, es que no sabemos si el conjunto de puntos de coordenadas enteras, pertenecientes al poliedro, es no vacío, y si así fuese, tampoco sabemos la frecuencia con que aparecen dichos puntos. En algunos casos, que llamaremos poliedros denso enteros, se demuestra que puede pasarse de un punto a otro por un camino interior al poliedro, pero en los casos que pueda plantearse la duda de que los puntos enteros estén aislados o no existan, habrá que estudiar nuevos procedimientos y demostrar que con ellos, la accesibilidad a cualquier punto eficiente de coordenadas enteras está garantizada.En el Capítulo 1, hacemos una revisión de las estructuras dinámicas de datos que han sido utilizados en otros problemas de búsqueda multidimensional, fundamentalmente, listas lineales, árboles ordenados, q-árboles y kd-árboles.En el Capítulo 2, aplicamos la estructuras anteriores a la localización de puntos eficientes, y se ha ce un estudio del rendimiento de cada una de ellas obteniéndose el kd-árbol como la estructuras más eficiente en nuestro problemas.En el Capítulo3, demostramos que para los poliedros densos enteros, podemos partir de cualquier punto factible y siguiendo un camino uno a uno direccional contenido en el poliedro, podemos llegar a cualquier punto eficiente entero: a lo largo de dicho camino, los puntos visitados serán almacenados en una estructura kd-árbol de forma que al terminar la enumeración la estructura tiene almacenada todos los puntos eficientes enteros.Para poliedros más generales el proceso se complica debido a que puede que no existan puntos enteros factibles, o que estén aislados en el poliedro; en este caso, estudiamos distintas relajaciones que permitirán obtener sus puntos eficientes enteros, o detectar si no existe ninguno, siguiendo un camino uno a uno direccional contenido en el poliedro relajado; los puntos visitados que sean factibles irán a la estructura kd-árbol que almacenará los puntos eficientes.Dada la complejidad, anteriormente citada, de los problemas enteros, si el poliedro tuviese un número muye levado de puntos factibles enteros, el proceso podría hacerse muy largo, pero entonces podemos aplicar los procedimientos estudiados a zonas definidas por unos márgenes de variación para cada una de las coordenadas.
