Benchmark of instances used corresponding to the Root Identification Problem:

This benchmark corresponds to different sizes of the Root Identification Problem. A set of instances is available for each problem size. Each instance is a different geometric problem and comes from a rough sketch of a two-dimensional object made out of simple geometric elements like points, lines, circles and arcs of circle.

The sketch is annotated with a set of constraints like distance between two points, distance from a point to a line, angle between two lines, line-circle tangency and so on to specify the intended exact shape. These constraints are specifically needed to solve the geometric constraint problem.

Additionally, the user annotates the geometric problem with a set of predicates on the geometric elements which identify the intended solution instance.

See (Hoffmann and Joan-Arinyo, 2005) and references therein for an extensive analysis of work on constraint solving. In (Bouma et al, 1995) the Root Identification Problem is defined. In (Luzón, 2001; Luzón et al, 2003) is shown how the Root Identification Problem can be formulated as an optimization problem and how metaheuristics, among them evolutionary algorithms, can be applied to solve it.

The benchmark presented here is constituted by two different types of instances: well-known instances corresponding to small problem sizes and randomly generated instances corresponding to large problem sizes.

WELL-KNOWN INSTANCES CORRESPONDING TO SMALL PROBLEM SIZES

The first group of instances corresponds to geometric problems with an index length taking value in the set {18, 19, 20}. Search spaces are limited respectively by 2¹⁸, 2¹⁹ or 2²⁰ solutions. Geometric problems made out of 18, 19 and 20 geometric elements have to be solved. The orientation predicates defined are used to indicate if a point should be on the left or on the right of a line defined by other two points. Those problems were generated by the solBCN solver, a constraint based two-dimensional geometric editor, and exhaustively studied in order to know the fitness, quality and features of the solutions belonging to every search space .

The instances corresponding to problem sizes 18, 19 and 20 are presented respectively in Tables 1, 2 and 3. 10 Figures (geometric problems) have been defined for problem size 18 and 12 Figures for each of the problem sizes 19 and 20. Each Figure is made out of simple geometric elements and a constraint set. In problem size 18, we have three different additional predicate sets for 9 Figures and two for the remaining one. In problem sizes 19 and 20, we have only one additional predicate set for every Figure. The number of instances for problem size 18 is 29 and for each of the problem sizes 19 and 20 is 12. In problem size 18, each instance is named X_Y, being X the Figure annotated with the set of predicates Y. In the remaining sizes, each instance is named X because of the one-to-one correspondence between Figures and set of predicates.

For each instance the next information is available:

• The name of the instance: X_Y (problem size 18) or X (problem sizes 19 and 20), shown in the first column.
• The geometric problem or Figure which it represents: image in postscript format (.ps file) and geometric elements and set of constraints which define the problem in text format (.bcn file). It is shown in the second column.
• The set of additional predicates which identify the intended solution instance: number of additional predicates defined and file in text format (.prdY, where Y corresponds to the instance X_Y, or .prd for instance X) containing the predicates. In each predicate, -1 is used to indicate point (first argument) on the left of the line defined by the other two points (second and third arguments) and 1 is used to indicate on the right. This information is presented in the third column.
• The whole search space corresponding to the instance in a text format file (.ordY, where Y corresponds to the instance X_Y, or .ord for instance X). The first line of the file presents the number of geometric elements (18, 19 or 20), the second line of the file presents the number of additional predicates and the remaining lines present each possible solution (decimal number) together with the number of additional predicates which it fulfills (-1 if the solution is not feasible). This file is available for downloading in the fourth column of the Table.
• The number of solutions which fulfill all the predicates defined for the instance (fifth column).

Table 1: Benchmark of Root Identification Problem instances for problem size 18.

Table 2: Benchmark of Root Identification Problem instances for problem size 19.

Table 3: Benchmark of Root Identification Problem instances for problem size 20.

RANDOMLY GENERATED INSTANCES CORRESPONDING TO LARGE PROBLEM SIZES

The second instance set is constituted by randomly generated instances belonging to problem sizes with large computational requirements needed to be solved. Problem sizes considered take value in a wider set {25, 30, 35, 50, 60, 70, 80, 100}. Search spaces are respectively limited by 2²⁵, 2³⁰, 2³⁵, 2⁵⁰, 2⁶⁰, 2⁷⁰, 2⁸⁰ and 2¹⁰⁰ solutions.

We have generated 10 instances or Figures for each problem size. The instance generation (geometric elements and constraints among the geometric elements) is based on well-constrained and descomposable graphs, (Vila, 2003), obtained by Henneberg sequences, (Borcea and Streinu, 2002). The number of geometric elements can be equal or lesser than the index length because of the auxiliar multivaluated functions in the construction plan. Notice that each multivaluated function corresponds to an index sign, (Vila, 2003). The geometric elements considered have only been points and lines in order to simplify.

The extra predicates used to define the intended solution are generated randomly for each instance by randomly selecting geometric elements and a type of orientation predicate: point-line (point on the left of a line) or clockwise (three points). We have different number of additional predicates for each instance.

The software used for randomly generating those instances is a part of the solBCN project and is available at the URL: http://floss.lsi.upc.edu (Additional predicates branch).

Next, the different instances for every problem size are presented. First, we show the common features of the different instances belonging to each size: problem size, number of geometric constraints and number of extra predicates. See Table 4.

*Maximum limit for extra predicates generated.

Table 4: Features for randomly generated instances belonging to each problem size.

Different single instances are shown now. Instances belonging to problem sizes 25, 30, 35, 50, 60, 70, 80 and 100 are respectively presented in Tables 5, 6, 7, 8, 9, 10, 11 and 12. For each instance the next information is available:

• Instance name : 1-10, shown in the first column.
• Geometric problem image (geometric elements and constraints): postcript format image (.eps file). It is shown in the second column.
• Geometric problem data: XML format file (.txt file). It contains geometric elements (<geometry></geometry>), geometric constraints (<constraints></constraints>) together with constraint parameters (<parameters></parameters>) and extra predicates (<additionalPredicates></additionalPredicates>). Geometric elements belong to one of two different types: points (pxy) and lines (lxy). Geometric constraints belong to one of four different types: two-point distance (dpp), point-line distance (dpl), two-line angle (all) and point on line (opl). Extra predicates can be: clockwise three points (clockwise) and point on the left of a line (pointlineorientation). This file is available in the third column.
• Concrete number of extra predicates. Only for problem sizes with a maximum limit for them (see Table 4).

Table 5: Randomly generated benchmark for problem size 25.

Table 6: Randomly generated benchmark for problem size 30.

Table 7: Randomly generated benchmark for problem size 35.

Table 8: Randomly generated benchmark for problem size 50.

Table 9: Randomly generated benchmark for problem size 60 .

Table 10: Randomly generated benchmark for problem size 70.

Table 11: Randomly generated benchmark for problem size 80.

Table 12: Randomly generated benchmark for problem size 100.

REFERENCES

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.

ACKNOWLEDGEMENTS

This research has been supported by FEDER and CICYT under the
project TIN2007-67474-C03-01.