Syntax CELAR instances

Each instance is distributed in four files in a single directory.

var.txt: gives the list of the variables,
dom.txt: gives the domain's definition,
ctr.txt: gives the list of all constraints,
cst.txt: defines the criteria to be optimized a priori on this instance.

All the files are made of fixed size fields and use space as a seprator.

The var.txt file

This file describes all the variables in the instance. Each line corresponds to one variable using 4 fields from which only the two first fields are always present.

Field 1: the variable number. ATTENTION, the numbers are not necessary in sequence. Some instances actually involve only a subet of the variable of the original problem.

Field 2: the domain number for the variable (cf. dom.txt file).

Field 3: the initial value of the variable (if any). This field is not always present. If present, it means that the link has laready been assigned a frequency.

Field 4: mobility of the variable i.e., the index of the cost of modification of its value (cf. cst.txt). The mobility can be equal to 0, 1 2, 3 et 4. A mobility equal to 0 indicates that the variable value cannot be modified (hard constraint). The values from 1 to 4 corresponds to increasing penalties whose values are defined in the cst.txt file.

The dom.txt file.

This file describes the domains used by the variables of the problem. Each line describes one domain. The first line defines a dummy domain that results from the union of all the domains.

Field 1: the domain number, used in the var.txt file .

Field 2: the domain cardinality.

Field 3 and next: the values of the domains, in increasing order.

The ctr.txt file.

This file describes the constraints of the instance. Each line defines a binary constraint.

Field 1: the number of the first variable.

Field 2: the number of the second variable.

Field 3: the constraint type. It is defined by a single character: (D (difference), C (cosite), F (fixe), P (préfixé) ou L (far fields). This field is useless in practice and is only available here to identify the origin of the constraint.

Field 4: the operator used in the constraint (see next field). It can be "=" or ">".

Field 5: the constraint deviation. It defines the constant k12 already mentionned. Together, Fields 4 and 5 define the constraint. The Field 4 indicates the realtional operator that must be used to compare the absolute value of the difference of the values of the variables to the integer given in the field 5 (deviation). The semnatics of a constraint is therefore:

|Field1 - Field2| Field4 Field5

Field 6: The index of weighting of the constraint. As for the mobility of assigned variables, it is an index that varies from 0 to 4. Value 0 indicates a hard constraint. Values from 1 to 4 indicates increasing weights as given in the cst.txt field. If this field is absent from the file, the constraint must be considered as an hard constraint (index 0).

The cst.txt file

It defines the criteria to be optimized on the instance a priori. This file has no precise syntax. It gives a textual description of the criteria and may also contain the definition of 8 numbers a1,..., a4, b1,..., b4. When the instance is unfeasible, one must minimize:
a1*nc1+...+a4*nc4+b1*nv1+...+b4*nv4

Where nci is the number of constraints whose weighting index is equal to i and which have been violated and where nvi is the number of assigned variables whose mobility index is equal to i and which have been modified. When may note that, according to the instance considered, the criteria to optimize a priori can be:

to simply minimize the number of freqeuncies used (instances 1, 2, and 3).
to minimize the number of frequencies used if the problem is feasible or else to minimize a weighted sum of violated constraints defined by a1,..., a4, b1,..., b4 (instances 6 to 11).
to minimize the largest frequency used if the problem is feasible or else to minimize a weighted sum of violated constraints defined by a1,..., a4, b1,..., b4 (instances 4 and 5).