Banco de instancias utilizado correspondiente al problema de la selección de la solución deseada:

Este banco de instancias corresponde a diferentes tamaños del problema de la selección de la solución deseada. Para cada tamaño del problema se dispone de un conjunto de instancias. Cada instancia está asociada a un problema geométrico diferente y proviene de la definición de un croquis de un objeto 2D constituido por elementos geométricos simples tales como puntos, líneas, círculos y arcos.

En el croquis se define, así mismo, un conjunto de restricciones entre los elementos geométricos tales como distancia entre dos puntos, distancia de un punto a una línea, ángulo entre dos líneas, tangencia círculo-línea, etc., para especificar la distribución seleccionada para los elementos geométricos. Tales restricciones son necesarias para resolver el problema geométrico correspondiente a la instancia.

Adicionalmente, el usuario especifica un conjunto de predicados sobre los elementos geométricos que identifican la solución deseada del conjunto de soluciones del problema geométrico.

Véase (Hoffmann and Joan-Arinyo, 2005) y las referencias que en ellos se presentan para conocer un análisis exhaustivo del trabajo desarrollado en resolución de restricciones geométricas. El problema de la selección de la solución deseada (Root Identification Problem) se define en (Bouma et al, 1995). La formulación del problema de la selección de la solución deseada como un problema de optimización y la aplicación de las metaheurísticas, entre ellas los algoritmos evolutivos, a la resolución de tal problema se presenta en (Luzón, 2001; Luzón et al, 2003).

El banco de instancias que se presenta a continuación está constituido por dos tipos de instancias diferentes: instancias conocidas correspondientes a tamaños reducidos del problema e instancias aleatorias correspondientes a tamaños considerables del problema.

INSTANCIAS CONOCIDAS DE TAMAÑOS DEL PROBLEMA REDUCIDOS

El primer conjunto de instancias corresponde a problemas geométricos en los que la longitud de índice toma los valores 18, 19 y 20. Los espacios de búsqueda están limitados por tanto por 2¹⁸, 2¹⁹ o 2²⁰ soluciones. Se trata de problemas geométricos constituidos por 18, 19 y 20 elementos geométricos respectivamente. Los predicados que se definen sobre los elementos geométricos son de orientación de un punto a la izquierda o derecha de una línea. Estos problemas fueron generados a partir del solver solBCN, un editor geométrico 2D basado en restricciones, y estudiados exhaustivamente para conocer la calidad y características de las diferentes soluciones que constituyen el espacio de búsqueda.

Las instancias correspondientes a los tamaños del problema 18, 19 y 20 se presentan en las Tablas 1, 2 y 3 respectivamente. Para tamaño 18 se han definido 10 Figuras (problemas geométricos) y 12 Figuras para cada uno de los tamaños 19 y 20. Cada Figura está constituida por elementos geométricos simples y un conjunto de restricciones. Para tamaño 18 se han definido tres conjuntos diferentes de predicados adicionales para 9 de las Figuras y dos para la restante. Para los tamaños 19 y 20 se ha definido un solo conjunto de predicados adicionales para cada Figura. Disponemos, por tanto, de 29 instancias para tamaño 18 y de 12 instancias para cada uno de los tamaños 19 y 20. Para tamaño 18, la notación utilizada para nombrar cada instancia es X_Y, siendo X la Figura e Y el conjunto de predicados asociado. Para los tamaños restantes la notación utilizada para cada instancia es solamente X, puesto que cada Figura tiene un solo conjunto de predicados adicionales.

Para cada instancia se dispone de la siguiente información:

• Nombre de la instancia : X_Y (tamaño 18) o X (tamaños 19 y 20) mostrado en la primera columna.
• Problema geométrico o Figura que representa: imagen en formato postcript (fichero .ps) y elementos geométricos y conjunto de restricciones que definen el problema en formato texto (fichero .bcn). Ello se muestra en la segunda columna.
• Conjunto de predicados adicionales definidos por el usuario que identifican la solución deseada: número de predicados adicionales definidos y fichero en formato texto (.prdY, donde Y corresponde a la instancia X_Y, o .prd para la instancia X) que contiene los predicados. Para cada predicado, -1 se utiliza para indicar punto (primer argumento) a la izquierda de la línea definida por los otros dos puntos (segundo y tercer argumentos) y 1 se utiliza para indicar a la derecha. Esta información se presenta en la tercera columna.
• Espacio de búsqueda completo correspondiente a la instancia en formato texto (.ordY, donde Y corresponde a la instancia X_Y, o .ord para la instancia X). La primera línea del fichero presenta el número de elementos geométricos (18, 19 o 20), la segunda línea muestra el número de predicados adicionales y las restantes cada solución posible (número decimal) junto al número de predicados adicionales que cumple (-1 si la solución no es factible). Este fichero está disponible para su descarga en la cuarta columna de cada Tabla.
• Número de soluciones que cumplen todos los predicados definidos para la instancia (quinta columna).

Tabla 1: Benchmark de instancias de tamaño 18 para el problema de la selección de la solución deseada.

Tabla 2: Benchmark de instancias de tamaño 19 para el problema de la selección de la solución deseada.

Tabla 3: Benchmark de instancias de tamaño 20 para el problema de la selección de la solución deseada.

INSTANCIAS ALEATORIAS DE TAMAÑOS DEL PROBLEMA CONSIDERABLES

El segundo conjunto de instancias está constituido por instancias generadas aleatoriamente para tamaños del problema de mayores requerimientos computacionales para su resolución. El rango de tamaños del problema considerados es más amplio: longitudes de índice de 25, 30, 35, 50, 60, 70, 80 y 100, que suponen espacios de búsqueda limitados respectivamente por 2²⁵, 2³⁰, 2³⁵, 2⁵⁰, 2⁶⁰, 2⁷⁰, 2⁸⁰ y 2¹⁰⁰ soluciones.

Para cada tamaño del problema se generarán aleatoriamente 10 instancias o Figuras. La generación de Figuras (elementos geométricos y restricciones sobre los elementos geométricos) estará basada en la obtención de grafos bien restringidos y descomponibles, (Vila, 2003), a partir de secuencias de Henneberg, (Borcea and Streinu, 2002). Recordemos que cada operación multivaluada (intersección del plan de construcción) está asociada a un signo del índice, (Vila, 2003). Para simplificar, los elementos geométricos considerados han sido solamente puntos y líneas.

Los predicados adicionales que definen la solución requerida por el usuario serán incorporados a cada Figura mediante la elección aleatoria de elementos geométricos y la asociación a los mismos de predicados de orientación: punto a la izquierda de una línea y orientación de tres puntos en el sentido de las agujas del reloj. Para cada instancia se ha generado un número diferente de predicados adicionales.

El software que permite la generación aleatoria de estas instancias forma parte del proyecto solBCN y está disponible en la web

http://floss.lsi.upc.edu (Additional predicates branch)

Más información acerca de su desarrollo puede encontrarse en la web

https://lafarga.cpl.upc.edu/projects/solbcn

A continuación presentaremos las diferentes instancias para cada tamaño del problema. En primer lugar indicaremos las características comunes a las diferentes instancias de cada tamaño: tamaño del problema, número de restricciones geométricas y número de predicados adicionales. Véase la Tabla 4.

*Límite máximo de restricciones adicionales generado para todas las instancias del tamaño.

Tabla 4: Características de las instancias generadas aleatoriamente para cada tamaño del problema.

Presentamos ahora las diferentes instancias individuales. Las Tablas 5, 6, 7, 8, 9, 10, 11 y 12 albergan tales instancias correspondientes respectivamente a los tamaños del problema 25, 30, 35, 50, 60, 70, 80 y 100. Para cada instancia se dispone de la siguiente información:

• Nombre de la instancia : 1-10, presentado en la primera columna de cada Tabla.
• Imagen del problema geométrico (elementos geométricos y restricciones) : imagen en formato postcript (fichero .eps). Ello se muestra en la segunda columna.
• Datos del problema geométrico: fichero con formato XML (fichero .txt) donde aparecen los elementos geométricos que constituyen el problema (<geometry></geometry>), las restricciones geométricas (<constraints></constraints>) junto con los parámetros asociados a las mismas (<parameters></parameters>) y los predicados adicionales definidos (<additionalPredicates></additionalPredicates>). Los elementos geométricos son de dos tipos: puntos (pxy) y líneas (lxy). Las restricciones geométricas son de cuatro tipos diferentes: distancia entre dos puntos (dpp), distancia de un punto a una línea (dpl), ángulo entre dos líneas (all) y punto sobre una línea (opl). Los predicados adicionales definidos son de dos tipos: orientación de tres puntos en el sentido de las agujas del reloj (clockwise) y punto a la izquierda de una línea (pointlineorientation).

Tabla 5: Benchmark aleatorio de instancias de tamaño 25 para el problema de la selección de la solución deseada.

Tabla 6: Benchmark aleatorio de instancias de tamaño 30 para el problema de la selección de la solución deseada.

Tabla 7: Benchmark aleatorio de instancias de tamaño 35 para el problema de la selección de la solución deseada.

Tabla 8: Benchmark aleatorio de instancias de tamaño 50 para el problema de la selección de la solución deseada.

Tabla 9: Benchmark aleatorio de instancias de tamaño 60 para el problema de la selección de la solución deseada.

Tabla 10: Benchmark aleatorio de instancias de tamaño 70 para el problema de la selección de la solución deseada.

Tabla 11: Benchmark aleatorio de instancias de tamaño 80 para el problema de la selección de la solución deseada.

Tabla 12: Benchmark aleatorio de instancias de tamaño 100 para el problema de la selección de la solución deseada.

AGRADECIMIENTOS

Este trabajo ha sido realizado en el marco del proyecto
TIN2007-67474-C03-01 financiado por FEDER y CICYT.

BIBLIOGRAFÍA

Borcea C, Streinu I (2002) On the number of embeddings of minimally rigid
graphs. SoCG’02.

Bouma W, Fudos I, Hoffmann C, Cai J, Paige R (1995) Geometric constraint solver. Computer Aided Design 27(6):487–501

Hoffmann C, Joan-Arinyo R (2005) A brief on constraint solving. Computer-Aided Design and Applications 2(5):655–663

Luzón M (2001) Resolución de restricciones geométricas. Selección de la solución deseada. PhD thesis, Dept. Informática, Universidad de Vigo, written in Spanish

Luzón MV, Joan-Arinyo R, Soto A (2003) Genetic algorithms for root multiselection in constructive geometric constraint solving. Computer & Graphics 27:51–60

Vila S (2003) Contribution to Geometric Constraint Solving in Cooperative Engineering.
PhD thesis, Departament de Llenguatges i Sistemes Informàtics,
Universitat Politècnica de Catalunya, Barcelona, Spain.