Orland Diez

Sara Gutiérrez-Enríquez

Carmen Mediano

Miriam Masas

Cristina Saura

Neus Gadea

Judith Balmaña

A novel de novo BRCA2 mutation of paternal origin identified in a Spanish woman with early onset bilateral breast cancer

Keywords: BRCA2, de novo mutation, hereditary breast cancer

Germline mutations in either of the two major breast cancer predisposition genes, BRCA1 and BRCA2, account for a significant proportion of hereditary breast/ ovarian cancer.

Identification of breast cancer patients carrying mutations in any of these genes is primarily based on a positive family history of breast/ovarian cancer or early onset of the disease.

In the course of mutation screening of the BRCA1 and BRCA2 genes in a hospital based series of patients with risk factors for hereditary breast/ovarian cancer, we identified a novel germline mutation in the BRCA2 gene (c.51dupA) in a patient with early onset bilateral breast cancer and no family history of the disease.

None of her parents carried the mutation, and paternity was confirmed. Subsequent molecular analysis demonstrated that the mutation was a novel de novo germline mutation located in the paternal allele of the BRCA2 gene.

INTRODUCTION

It is currently estimated that 5-10% of all breast cancers are hereditary and a proportion of them attributable to mutations in several highly penetrant susceptibility genes. Mutations in the tumor-suppressor genes BRCA1 (MIM#113705) and BRCA2 (MIM#600185) confer an increased risk of developing breast cancer and ovarian cancer [START_REF] Easton | Breast and ovarian cancer incidence in BRCA1 mutation carriers. Breast Cancer Linkage Consortium[END_REF][START_REF] Easton | Cancer risks in two large breast cancer families linked to BRCA2 on chromosome 13q12-13[END_REF].

Family history is essential for identifying individuals at risk for mutations in the BRCA genes in the clinics. Hallmark characteristics include a personal or family history of early onset breast cancer, multiple family members diagnosed with breast or ovarian cancers, multiple generations affected, breast cancer bilaterality, the occurrence of male breast cancer, and ethnicity (descent from a population with high incidence of founder mutations, such as Ashkenazi Jewish or Icelandic ancestry).

A negative family history, however, does not exclude the presence of a germ line mutation in BRCA1 or BRCA2 genes. Indeed, it may reflect a small family size, predominance of males in the pedigree, incomplete penetrance, premature death of at risk women, or inadequacy of the cancer history information [START_REF] Weitzel | Limited family structure and BRCA gene mutation status in single cases of breast cancer[END_REF]. In patients without a positive family history, mutation testing of these genes may be considered when early onset, multifocality, bilaterality or other features suggestive of a hereditary component are present. Furthermore, recent studies show that tumor phenotype, such as the so called triple-negative (absence of estrogen and progesterone receptors and her2-neu expression) breast cancer, is an indicator that may help to identify candidates for BRCA1 mutation testing, especially among young women without family history (4), who otherwise would not have been eligible.

Since the identification of BRCA1 and BRCA2, more than 3600 distinct genetic variants (including deleterious mutations, polymorphisms, and unclassified variants) have been reported for these genes (BIC database) (5). Despite the high number of mutations identified and the large number of studies carried out world wide, to our knowledge there is only one published report of a de novo mutation in BRCA1 (6) and three in BRCA2 [START_REF] Robson | Unique de novo mutation of BRCA2 in a woman with early onset breast cancer[END_REF][START_REF] Van Der Luijt | De novo recurrent germline mutation of the BRCA2 gene in a patient with early onset breast cancer[END_REF][START_REF] Hansen | Novel de novo BRCA2 mutation in a patient with a family history of breast cancer[END_REF].

During the course of the molecular analysis of BRCA1 and BRCA2 on hereditary breast/ovarian cancer families and women diagnosed with breast cancer at young ages, we identified a novel de novo BRCA2 mutation located in exon 2 in a Spanish patient with early onset bilateral breast cancer without a family history of breast/ovarian cancer. Furthermore, we ascertained the presence of the mutation in the paternal allele.

Personal and family history

The proband was a 38 year old woman who had been diagnosed at the ages of 27 and 37 with bilateral infiltrating ductal carcinomas of the breast. The first tumor was estrogen and progesterone receptor negative, and the second one was estrogen and progesterone receptor positive, and HER2 negative.

No other breast or ovarian cancers were present in the pedigree (figure 1). Following genetic counseling, blood and tumour samples were collected from the proband for mutation screening.

Mutation identification

Genomic DNA was prepared from 10 ml EDTA blood samples according to standard procedures. Analysis of the entire coding and flanking BRCA1/2 sequences, were carried out by direct sequencing (Abi Prism 3130 DNA Sequencer, Applied Biosystems).

Mutation screening of the BRCA2 gene in the proband indicated in exon 2 the presence of one bp duplication (c.51dupA, according to HGVH nomenclature) (c.279_280insA according to BIC nomenclature) (BRCA2 GenBank entry: NM_000059). The insertion results in a frame shift and a premature termination of translation at codon 30 in exon 3 of BRCA2. As far as we know this mutation has not been previously reported by the Breast Cancer Information Core or another database, and it has not been published before.

After identification of the mutation the analysis was then carried out on DNA samples obtained from the proband's mother, father, and siblings. Surprisingly, neither of her parents was found to carry the mutation, suggesting that this germ line alteration had occurred de novo. The presence of the mutation in the proband was confirmed on an independent DNA sample obtained from peripheral blood leukocytes, and in DNA extracted from micro dissected archival breast-cancer tissue. However, no apparent LOH was identified in the tumor.

Paternity confirmation

To confirm paternity, a set of highly polymorphic short tandem repeat (STR) markers was analyzed by QF-PCR analysis using the ANEUFAST Kit (Genomed Ltd). The markers included in the kit were: D21S1414, D21S1446, D21S1411, D21S1435, D13S631, D13S305, D13S634, D13S258, D18S525, D18S391, D18S386, D18S390, AMXY, X22, HPRT, DXYS218, and SRY. PCR amplification and fragment analysis were performed according to the manufacturer's instructions. Markers were analyzed on an ABI Prism 3130 DNA Sequencer (Applied Biosystems).

All markers proved to be highly informative, consistent with the reported paternity with high probability. This result confirmed that the duplication identified in the proband was a de novo germ line mutation in BRCA2 that occurred during parental germ-cell gametogenesis.

Parental origin of the mutation

To determine whether the mutation had occurred on the maternal or paternal allele, we analyzed a polymorphism located near the site of mutation in the 5'UTR part of the BRCA2 gene (-26G>A according to HGVH numbering, -203G>A according to BIC). This single nucleotide polymorphism was fully informative because the father was homozygous GG, and the mother was homozygous AA (fig. 1).

An allele specific PCR was performed using primers designed to distinguish between the two SNP alleles, and therefore the allele carrying the mutation from the wild-type allele. Specific primers were designed using the software Primer3 in combination with MFEprimer to search specificity and SNP blast alignments.

The forward primer sets were designed to distinguish the -26A and the -26G allele with the last nucleotide: 5'-TCTGTTTTGCAGACTTATTTACCAAA/G-3', respectively. The primer reverse was: 5'-GTTTCCTCTTTATCCACTAGACGTTC-3'. Primer sets were tested on the samples from both the father and the mother, used as homozygote controls. PCR was carried out using standard conditions (available upon request).

The -26G allele was present in cis with the mutated c.51dupA allele. In accordance, the mutation was absent in the -26A allele sequence (figure 2). These data indicate that the BRCA2 c.51dupA mutation was on the father's allele and also further suggest that this mutation probably arose as a de novo event in a testicular germ cell.

DISCUSSION

We describe the identification of the BRCA2 c.51dupA mutation in a woman affected by bilateral early onset breast cancer at the ages of 27 and 37 and no family history of the disease. No one else in the family was identified to carry this mutation, and paternity was confirmed with the analysis of polymorphic markers. We therefore conclude that the identified novel mutation in the proband is a de novo mutation.

The presence of the alteration in the paternal allele was determined by the analysis of a polymorphism located near the mutation (-26G>A), taking advantage that the father was homozygous GG, and the mother was homozygous AA for this polymorphism. The result suggests a de novo event in a testicular germ cell, although an occurrence in the zygote can not be discarded. This is in agreement with previous findings in de novo mutations in BRCA1 and BRCA2, in which the paternal origin could be ascertained (5,8), and also in other hereditary cancer syndromes (neurofibromatosis type 1, MEN2B and retinoblastoma) [START_REF] Carlson | Parent-of-origin effects in multiple endocrine neoplasia type 2B[END_REF][START_REF] Kato | Parental origin of germ-line and somatic mutations in the retinoblastoma gene[END_REF]. It has been suggested that the origin of new mutations may be influenced by both genomic imprinting effects and the increased number of cell divisions in spermatogenesis compared with oogenesis. However, other familiar cancer syndromes do not exhibit a marked bias for a paternal origin of new mutations [START_REF] Richards | Molecular analysis of de novo germline mutations in the von Hippel-Lindau disease gene[END_REF].

Although this specific mutation has not previously been described, several other presumably deleterious alterations have been reported in its vicinity in exon 2 (BIC). Examples include c.245delAA (reported three times), c.254delC (reported seven times), c.264insT, c.264delT, c.265G>T, and c.265insT (reported once each), c.279delAC (reported five times), and c.291delA (reported twice), suggesting that this area of the gene could be prone to mutations.

The observation that a previous known recurrent mutation in BRCA genes may appear as a de novo alteration suggest the existence of hot spots for small alterations. As an example, the BRCA2 c.3036_3039del4 mutation may have arisen on many separate occasions in various ethnic groups, according to the results of haplotype studies, and it has also been identified as a de novo mutation [START_REF] Van Der Luijt | De novo recurrent germline mutation of the BRCA2 gene in a patient with early onset breast cancer[END_REF]. The authors suggested that these occurrences could be related with tandemly repeated sequences, which favor misalignments during DNA replication.

Although all germ line mutations started as a de novo mutation in some ancestor, the proportion of de novo mutations among gene carriers seems to be low. To our knowledge, there is only one published report of a proven de novo mutation in the BRCA1 gene and three in the BRCA2 gene, and there is only one previous report of a novel de novo mutation in BRCA2.

Haplotype studies of founder mutations in BRCA1 and BRCA2 demonstrated that they remain present in the population for many generations, probably due to the fact that cancer usually occurs after the reproductive capacity has been fulfilled. However, BRCA mutation studies are usually performed in families with multiple cases of breast/ovarian cancer, although the de novo mutations could be particularly expected in early onset breast cancer patients with no family history of the disease. One may hypothesize whether prevalence of de novo mutations would increase in case BRCA genetic testing was offered to unselected patients with early onset breast cancer There are a number of reports of BRCA1 and BRCA2 germ line mutations detected in early onset breast cancer patients without family history of the disease. In a population-based series of Spanish women diagnosed with breast cancer before age 40 the prevalence of BRCA1 and BRCA2 germ line mutations was 11.6% [START_REF] De Sanjosé | Prevalence of BRCA1 and BRCA2 germline mutations in young breast cancer patients: a population-based study[END_REF]. Family history of breast cancer and ovarian cancer was absent or not suggestive of hereditary consition in one-fourth of mutation carriers. Lidereau et al [START_REF] Lidereau | Major improvement in the efficacy of BRCA1 mutation screening using morphoclinical features of breast cancer[END_REF] found that 6 of 70 women (9%) with breast cancer diagnosed at age 35 or below unselected for family history carried a BRCA1 mutation. One of them did not have any family history of breast/ovarian cancer. In a study of 254 white women from the UK, diagnosed with breast cancer before age 36, a germ line BRCA1 or BRCA2 mutation was identified in 15 women (6%), and only one had a family history [START_REF] Peto | Prevalence of BRCA1 and BRCA2 gene mutations in patients with early-onset breast cancer[END_REF]. Another recent study identified 6 mutations (11%) in 54 women diagnosed with high-grade, triple-negative invasive breast cancer at or before age 40, and little or no family history of breast or ovarian cancer (4). The authors concluded that women with early-onset triple-negative breast cancer are candidates for genetic testing for BRCA1, even in the absence of a family history of breast or ovarian cancer.

These studies underline the importance of mutation screening of the BRCA1 and BRCA2 genes in women with early onset breast/ovarian cancer or males with breast cancer, without a strong family history of the disease. The absence of family history might be related to non-informative kindreds (few women who lived until ages at risk of developing breast or ovarian cancer) or, albeit infrequent, the presence of a de novo mutation. Bearing in mind this possibility, the two parents of a new mutation carrier should be tested for the mutation to ascertain its origin. This information could be useful when considering the incidence of de novo mutations of the BRCA1 and BRCA2 genes in genetic epidemiological studies.

Figure 1 :

 1 Figure 1: family pedigree: BC: breast cancer; colorectal (CR). Between parenthesis: age at diagnosis. The BRCA2 -26G/A and wt/279inA genotypes are indicated.

Figure 2 :

 2 Figure 2: Electropherograms of reverse sequences corresponding to the two alleles specifically amplified from the DNA of the BRCA2 mutation carrier. The sequence of the paternal allele shows the presence of 5'UTR-26G and c.279insA genotype. The sequence of the maternal allele shows the presence of 5'UTR-26A and the wild-type (wt) genotype.

Acknowledgements

This work was in part funded by a grant from Fundación de Investigación Médica Mutua Madrileña.


Giovanna Vecchi

Paolo Verderio

Sara Pizzamiglio

Siranoush Manoukian

Monica Barile

Stefano Fortuzzi

Fernando Ravagnani

Marco A Pierotti

Paolo Radice
email: paolo.radice@istitutotumori.mi.it

Paolo Peterlongo

Giovanna De Vecchi

A E Paolo

Verderio Ae

A E Siranoush

Manoukian Ae

Monica Barile Ae

A E Fernando

Ravagnani Ae

Radice Ae

Á P Radice

Á P Peterlongo

Á S Pizzamiglio

Evidences for association of the -652 6N del promoter polymorphism with age at diagnosis in familial breast cancer cases

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

To the Editor, Recently, a study conducted in Chinese individuals reported that a 6-nucleotide deletion in the promoter of the CASP8 gene (the -652 6N del; rs3834129) was strongly associated with decreased cancer risk in several types of cancers including breast cancer (BC) [START_REF] Sun | A six-nucleotide insertiondeletion polymorphism in the CASP8 promoter is associated with susceptibility to multiple cancers[END_REF]. Here, we studied the effect of this polymorphism in a series of 580 Italian familial BC index cases and 406 controls. The cases were originally ascertained through the Genetic Services of Fondazione IRCCS Istituto Nazionale Tumori (INT) or Istituto Oncologico Europeo (IEO) in Milan, as eligible for mutation analysis in BRCA genes based on criteria including family history and age at cancer diagnosis [START_REF] Manoukian | Germline mutations of TP53 and BRCA2 genes in breast cancer/sarcoma families[END_REF]. All the females affected with BC as the first diagnosed cancer (median age: 43; range: 21-80), who tested negative for BRCA disease-causing mutations, were included in this study. The controls were Italian female blood donors who were C45 years at the blood draw (median age, 54; range, 45-71) recruited at INT. The genotyping was performed comparing the length of PCR fragments of the normal and the deleted allele with a size marker using Denaturing High-Performance Liquid Chromatography (assay and primer sequences are available upon request).

In cases and controls, common homozygous (nor/nor), heterozygous (nor/del) and rare homozygous (del/del) were 162 (27.9%), 301 (51.9%) and 117 (20.2%); and 106 (26.1%), 206 (50.7%) and 94 (23.2%), respectively, consistent with Hardy-Weinberg equilibrium. By logistic regression analysis adjusted for age [START_REF] Hosmer | Applied logistic regression[END_REF], we observed that the odds ratio (OR) for heterozygous and rare homozygous compared with common homozygous was 1.05 (95% confidence interval (CI) = 0.74-1.49) and 1.09 (95% CI = 0.71-1.67), respectively, and the per-allele OR was 0.96 (95% CI = 0.78-1.18). These results provided no evidence for association between the -652 6N del polymorphism and familial BC unlinked to BRCA genes, confirming the findings obtained in German, English and Polish individuals [START_REF] Frank | The CASP8 -652 6N del promoter polymorphism and breast cancer risk: a multicenter study[END_REF][START_REF] Cybulski | A sixnucleotide deletion in the CASP8 promoter is not associated with a susceptibility to breast and prostate cancers in the Polish population[END_REF]. We pursued the study of the -652 6N del polymorphism. Of interest was the investigation of the association between the polymorphism and age at BC diagnosis in cases. The three genotypes were collapsed into two: (del/del), and (nor/-) by aggregating common homozygous and heterozygous cases; the age at diagnosis was categorized into four classes according to the pertinent age centiles (25th: 35; 50th: 43; 75th: 50). We assessed the associations between each age class and genotype by the logistic regression model considering as reference group the cases with younger age at diagnosis. We observed a statistically significant association between these two variables (Table 1). In particular, our results suggested an increasing trend of the del/del genotype with later age at BC diagnosis (trend test P-value = 0.01).

In conclusion, our results confirmed those obtained in previous Europeans studies. Nevertheless, we observed that the -652 6N del polymorphism of CASP8 was associated with age at diagnosis in familial BC cases. Thus, we suggest that this polymorphism may have an effect in postponing the BC onset in predisposed individuals. To our knowledge, this is the first study that investigated this latter aspect; consequently, our results should be taken with caution and further analyses are necessary to clarify the effect of this polymorphism on BC.

Table 1

 1 Association of genotypes of the CASP8 -652 6N del polymorphism with age at breast cancer diagnosis in 580 familial breast cancer index cases

	Age at	N	del/del	nor/-(%) OR b 95% CI c P-value
	diagnosis		(%)
	B35 a	173 22 (12.7) 151 (87.3) 1.00
	36-43	120 27 (22.5) 93 (77.5) 1.99 1.07-3.70 0.03
	44-50	148 34 (23.0) 114 (77.0) 2.05 2.14-3.69 0.02
	[50	139 34 (24.5) 105 (75.5) 2.22 1.23-4.01 0.01
	a Reference group
	b OR, Odds ratio

c CI, Confidence interval

Acknowledgements This work was supported by Fondazione Italiana per la Ricerca sul Cancro (FIRC; Special Project'Hereditary tumors'); Associazione Italiana per la Ricerca sul Cancro (AIRC; Grant number 4017); Ministero dell'Universita' e Ricerca (MiUR; Grant number: RBLA03BETH); and Istituto Superiore di Sanita `(ISS, Grant number: 526D/41).


Gilles Trombettoni

Gilles Chabert
email: gilles.chabert@ensieta.com

Constructive Interval Disjunction

This paper presents two new filtering operators for numerical CSPs (systems with constraints over the reals) based on constructive disjunction, as well as a new splitting heuristic. The fist operator (CID) is a generic algorithm enforcing constructive disjunction with intervals. The second one (3BCID) is a hybrid algorithm mixing constructive disjunction and shaving, another technique already used with numerical CSPs through the algorithm 3B. Finally, the splitting strategy learns from the CID filtering step the next variable to be split, with no overhead.

Experiments have been conducted with 20 benchmarks. On several benchmarks, CID and 3BCID produce a gain in performance of orders of magnitude over a standard strategy. CID compares advantageously to the 3B operator while being simpler to implement. Experiments suggest to fix the CID-related parameter in 3BCID, offering thus to the user a promising variant of 3B.

Introduction

We propose in this paper new advances in the use of two refutation principles of constraint programming: shaving and constructive disjunction. We first introduce shaving and then proceed to constructive disjunction that will be considered an improvement of the former.

The shaving principle is used to compute the singleton arc-consistency (SAC) of finite-domain CSPs [START_REF] Debruyne | Some Practicable Filtering Techniques for the Constraint Satisfaction Problem[END_REF] and the 3B-consistency of numerical CSPs [START_REF] Lhomme | Consistency Tech. for Numeric CSPs[END_REF]. It is also in the core of the SATZ algorithm [START_REF] Li | Anbulagan: Heuristics Based on Unit Propagation for Satisfiability Problems[END_REF] proving the satisfiability of boolean formula. Shaving works as follows. A value is temporarily assigned to a variable (the other values are temporarily discarded) and a partial consistency is computed on the remaining subproblem. If an inconsistency is obtained then the value can be safely removed from the domain of the variable. Otherwise, the value is kept in the domain. This principle of refutation has two drawbacks. Contrarily to arc consistency, this consistency is not incremental [START_REF] Bessière | Optimal and Suboptimal Singleton Arc Consistency Algorithms[END_REF]. Indeed, the work of the underlying refutation algorithm on the whole subproblem is the reason why a single value can be removed. Thus, obtaining the singleton arc consistency on finite-domain CSPs requires an expensive fixed-point propagation algorithm where all the variables must be handled again every time a single value is removed [START_REF] Debruyne | Some Practicable Filtering Techniques for the Constraint Satisfaction Problem[END_REF]. SAC2 [START_REF] Barták | A new Algorithm for Singleton Arc Consistency[END_REF] and SAC-optim [START_REF] Bessière | Optimal and Suboptimal Singleton Arc Consistency Algorithms[END_REF] and other SAC variants obtain better average or worst time complexity by managing heavy data structures for the supports of values (like with AC4) or by duplicating the CSP for every value. However, using these filtering operators inside a backtracking scheme is far from being competitive with the standard MAC algorithm in the current state of research. In its QuickShaving [START_REF] Lhomme | Quick Shaving[END_REF], Lhomme uses this shaving principle in a pragmatic way, i.e., with no overhead, by learning the promising variables (i.e., those that can possibly produce gains with shaving in the future) during the search. Researchers and practitioners have also used for a long time the shaving principle in scheduling problems. On numerical CSPs, the 2B-consistency is the refutation algorithm used by 3B-consistency [START_REF] Lhomme | Consistency Tech. for Numeric CSPs[END_REF]. This property limited to the bounds of intervals explains that 3B-consistency filtering often produces gains in performance.

Example. Figure 1 (left) shows the first two steps of the 3B-consistency algorithm. Since domains are continuous, shaving does not instantiate a variable to a value but restricts its domain to a sub-interval of fixed size located at one of the endpoints. The subproblems are represented with slices in light gray. The 2Bconsistency projects every constraint onto a variable and intersects the result of all projections. In the leftmost slice, 2B-consistency leads to an empty box since the projections of the first and the second constraint onto x 2 are two intervals I 1 and I 2 with empty intersection. On the contrary, the fixed-point of projections in the rightmost slice is a nonempty box (with thick border).

The second drawback of shaving is that the pruning effort performed by the partial consistency operator to refute a given value is lost, which is not the case with constructive disjunction 1 .

Constructive disjunction was proposed by Van Hentenryck et al. in the nineties to handle efficiently disjunctions of constraints, thus tackling a more general model than the standard CSP model [START_REF] Van Hentenryck | Design, Implementation, and Evaluation of the Constraint Language CC(FD)[END_REF]. The idea is to propagate independently every term of the disjunction and to perform the union of the different pruned search spaces. In other terms, a value removed by every propagation process (run with one term/constraint of the disjunct) can be safely removed from the ground CSP. This idea is fruitful in several fields such as scheduling, where a common constraint is that two given tasks cannot overlap, or 2D bin packing problems where two rectangles must not overlap.

Constructive disjunction can also be used to handle the classical CSP model (where the problem is viewed as a conjunction of constraints). Indeed, every variable domain can be viewed as a unary disjunctive constraint that imposes one value among the different possible ones (x = v 1 ∨ ... ∨ x = v n , where x is a variable and v 1 , ..., v n are the different values). In this specific case, similarly to shaving, the constructive disjunction principle can be applied as follows. Every value in the domain of a variable is assigned in turn to this variable (the other values are temporarily discarded), and a partial consistency on the corresponding subproblems is computed. The search space is then replaced by the union of the resulting search spaces. One advantage over shaving is that the (sub)filtering steps performed during constructive disjunction are better reused. This constructive "domain" disjunction is not very much exploited right now while it can sometimes produce impressive gains in performance. In particular, in addition to all-diff constraints [START_REF] Régin | A Filtering Algorithm for Constraints of Difference in CSPs[END_REF], incorporating constructive domain disjunctions into the famous Sudoku problem (launched, for instance, when the variables/cases have only two remaining possible values/digits) often leads to a backtrack-free solving. The same phenomenon is observed with shaving but at a higher cost [START_REF] Simonis | Sudoku as a Constraint Problem[END_REF].

This observation has precisely motivated the research described in this paper devoted to the application of constructive domain disjunction to numerical CSPs. The continuous nature of interval domains is particularly well-suited for constructive domain disjunction. By splitting an interval into several smaller intervals (called slices), constructive domain disjunction leads in a straightforward way to the constructive interval disjunction (CID) filtering operator introduced in this paper.

After useful notations and definitions introduced in Section 2, Sections 3 and 4 describe the CID partial consistency and the corresponding filtering operator. A hybrid algorithm mixing shaving and CID is described in Section 5. Section 6 presents a new CID-based splitting strategy. Finally, experiments are presented in Section 7.

Definitions

The algorithms presented in this paper aim at solving systems of equations or, more generally, numerical CSPs. Definition 1. A numerical CSP (NCSP) P = (X, C, B) contains a set of constraints C and a set X of n variables. Every variable x i ∈ X can take a real value in the interval x i and B is the cartesian product (called a box) x 1 × ... × x n . A solution of P is an assignment of the variables in X satisfying all the constraints in C. Remark 1. Since real numbers cannot be represented in computer architectures, the bounds of an interval x i should actually be defined as floating-point numbers.

CID filtering performs a union operation between two boxes. Definition 2. Let B l and B r be two boxes corresponding to a same set V of variables. We call hull of B l and B r , denoted by Hull(B l , B r ), the minimal box including B l and B r .

To compute a bisection point based on a new (splitting) strategy, we need to calculate the size of a box. In this paper, the size of a box is given by its perimeter.

Definition 3. Let B = x 1 × ... × x n be a box. The size of B is n i=1 (x i -x i )
, where x i and x i are respectively the upper and lower bounds of the interval x i .

CID-consistency

The CID-consistency is a new partial consistency that can be obtained on numerical CSPs. Following the principle given in introduction (i.e., combining interval splitting and constructive disjunction), the CID(2)-consistency can be formally defined as follows (see Figure 1).

Definition 4. (CID(2)-consistency)

Let P = (X, C, B) be an NCSP. Let F be a partial consistency.

Let B l i be the sub-box of B in which x i is replaced by

[x i , xi ] (where xi is the midpoint of x i ). Let B r i be the sub-box of B in which x i is replaced by [ xi , x i ]. A variable x i in X is CID(2)-consistent w.r.t. P and F if B = Hull(F (X, C, B l i ), F (X, C, B r i ))
. The NCSP P is CID(2)-consistent if all the variables in X are CID(2)-consistent. For every dimension, the number of slices considered in the CID(2)-consistency is equal to 2. The definition can be generalized to the CID(s)-consistency in which every variable is split into s slices.

In practice, like 3B-w-consistency, the CID-consistency is obtained with a precision that avoids a slow convergence onto the fixed-point. We will consider that a variable is CID(2,w)-consistent if the hull of the corresponding left and right boxes resulting from subfiltering reduces no variable more than w.

Definition 5. (CID(2,w)-consistency) With the notations of Definition 4, put

B = Hull(F (X, C, B l i ), F (X, C, B r i )). A variable x i in X is CID(2,w)-consistent if |x i | -|x i | ≤ w, where x i and x i are the domain of x i in resp. B and B . The NCSP is CID(2,w)-consistent if all the variables in X are CID(2,w)-consistent.
Algorithm CID details the CID(s,w)-consistency filtering algorithm. Like the 3Bconsistency algorithm, CID iterates on all the variables until a stop criterion, depending on w, is reached (see Definition 5): the Repeat loop is interrupted when no variable interval has been reduced more than w2 .

Every variable x i is "varcided", i.e., handled by the procedure VarCID. The domain of x i is split into s slices of size |x i | s each by the procedure SubBox. The partial consistency operator F (e.g., 2B or a variant of the latter called Box-consistency [START_REF] Van Hentenryck | Numerica: A Modeling Language for Global Optimization[END_REF]) filters the corresponding sub-boxes, and the union of the resulting boxes is computed by the Hull operator. Note that if the subfiltering operator F applied to a given sub-box sliceBox detects an inconsistency, then the result sliceBox' is empty, so that there is no use of performing the union of sliceBox' with the current box in construction.

Algorithm CID (s: number of slices, w: precision, in-out P = (X, C, B): an NCSP, F : subfiltering operator and its parameters)

repeat P old ← P LoopCID (X, s, P , F ) until StopCriterion(w, P , P old ) end. Procedure LoopCID (X, s, in-out P , F ) for every variable xi ∈ X do VarCID (xi, s, P , F ) end end. Procedure VarCID (xi, s, (X, C, in-out B), F ) B ← empty box for j ← 1 to s do sliceBox ← SubBox (j,

A CID-Based Solving Strategy

To find all the solutions of a numerical CSP, we propose a strategy including a bisection operation, CID filtering and an interval Newton [START_REF] Neumaier | Interval Methods for Systems of Equations[END_REF]. Between two bisections, two operations are run in sequence:

1. a call to CID (how to fix the parameters is discussed just below), 2. a call to an interval Newton operator.

The Right Set of Parameters for CID Filtering

First of all, the subfiltering operators we chose for CID are 2B and Box. The classical user-defined parameter w-hc4 (percentage of the interval width) is used by the subfiltering operator (Box or 2B) inside CID to control the propagation loop. The parameter s is the number of slices used by the VarCID procedure.

Although useful to compute the CID-consistency property, the fixed-point repeat loop used by Algorithm CID does not pay off in practice (see below). In other words, running more than once LoopCID on all the variables is always counterproductive, even if the value of w is finely tuned. Thus, we have set the parameter w to ∞, that is, we have discarded w from the user-defined parameters.

Endowed with the parameters s and w-hc4, CID filtering appears to be an efficient general-purpose operator that has the potential to replace 2B/Box (alone) or 3B. For some (rare) benchmarks however, the use of only 2B/Box appears to be more efficient.

To offer a compromise between pure 2B/Box and CID, we introduce a third parameter n defined as the number of variables that are varcided between two bisections in a round-robin strategy: given a predefined order between variables, a VarCID operation is called on n variables (modulo n), starting at the lattest varcided variable plus one in the order. (This information is transmitted through the different nodes of the tree search.) Thus, if n is set to 0, then only 2B/Box filtering is called between two bisections; if n = n (n is the number of variables in the system), then CID is called between two bisections.

We shall henceforth consider that CID has three parameters: the number of slices s, the propagation criterion w-hc4 of 2B/Box used for subfiltering and the number n' of varcided variables.

Default Values for CID Parameters

So far, we have proposed an efficient general-purpose combination of CID, interval Newton and bisection. However, such a strategy is meaningful only if default values for CID are available. In our solver, the default values provide the following CID operator: CID(s=4, w-hc4=10%, n'=n).

Experiments have led us to select s = 4 (see Section 7.2):

-The optimal number of slices lies between 2 and 8.

-Selecting s = 4 generally leads to the best performance. In the other cases, the performance is not so far from the one obtained with a tuned number of slices.

Discarded Variants

Several variants of CID or combinations of operators have been discarded by our experiments. Mentioning these discarded algorithms may be useful. First, different combinations of bisection, CID and interval Newton have been tried. The proposed combination is the best one, but adding an interval Newton to the 2B/Box subfiltering (i.e., inside CID filtering) produces interesting results as well.

Second, we recommend to forget the fixed-point parameter w in CID. Indeed, a lot of experiments confirmed that relaunching LoopCID several times in a row between two bisections is nearly never useful. The same phenomenon has been observed if the relaunch criterion concerns several dimensions, i.e., if the reduction of box size (perimeter or volume) is sufficiently large. A third experiment running LoopCID twice between two splits leads to the same conclusion. Finally, the same kind of experiments have been conducted with no more success to determine which specific variables should be varcided again in an adaptive way. All these experiments give us the strong belief that one LoopCID, i.e., varciding all the variables once, is rather a maximal power of filtering.

Third, in a previous workshop version of this paper, we had proposed a CID246 variant of CID, in which the number s of slices was modified between two splits: it was alternatively 2, 4 or 6 : s = ((i modulo 3) + 1) × 2), where i indicates the i th call to LoopCID. The comparison with the standard CID was not fair because the parameter s in CID was set to 2. It turns out that CID with s = 4 yields nearly the same results as CID246 while being simpler.

Finally, we also investigated the option of a reentrant algorithm, under the acronym k-CID. As k-B-consistency [START_REF] Lhomme | Consistency Tech. for Numeric CSPs[END_REF] generalizes the 3-B-consistency, it is possible to use (k -1)-CID as subfiltering operator inside a k-CID algorithm. Like 4-B-consistency, 2-CID-consistency remains a theoretical partial consistency that is not really useful in practice. Indeed, the pruning power is significant (hence a small number of required splits), but the computational time required to obtain the solutions with 2-CID plus bisection is often not competitive with the time required by 1-CID plus bisection.

3B, CID and a 3BCID Hybrid Version

As mentioned in the introduction, the CID partial consistency has several points in common with the well-known 3B-consistency partial consistency [START_REF] Lhomme | Consistency Tech. for Numeric CSPs[END_REF].

Definition 6. (3B(s)-consistency)

Let P = (X, C, B) be an NCSP. Let B l i be the sub-box of B in which

x i is replaced by [x i , x i + |x i | s ]. Let B r i be the sub-box of B in which x i is replaced by [x i -|x i | s , x i ]. Variable x i is 3B(s)-consistent w.r.t. P if 2B(X, C, B l i ) = ∅ and 2B(X, C, B r i ) = ∅. The NCSP P is 3B(s)-consistent if all the variables in X are 3B(s)- consistent.
For practical considerations, and contrarily to finite-domain CSPs, a partial consistency of an NCSP is generally obtained with a precision w [START_REF] Lhomme | Consistency Tech. for Numeric CSPs[END_REF]. This precision avoids a slow convergence to obtain the property. Hence, as in CID, a parameter w is also required in the outer loop of 3B.

When the subfiltering operator is performed by Box consistency, instead of 2B-consistency, we obtain the so-called Bound consistency property [START_REF] Van Hentenryck | Numerica: A Modeling Language for Global Optimization[END_REF].

The 3B algorithm follows a principle similar to CID, in which VarCID is replaced by a shaving process, called VarShaving in this paper. In particular, both algorithms are not incremental, hence the outside repeat loop possibly reruns the treatment of all the variables, as shown in Algorithm 3B.

Algorithm 3B (w: stop criterion precision, s : shaving precision, in-out P = (X, C, B): an NCSP, F : subfiltering operator and its parameters) repeat for every variable xi ∈ X do VarShaving (xi, s, P , F ) end until StopCriterion(w, P ) end.

The procedure VarShaving reduces the left and right bounds of variable x i by trying to refute intervals with a width at least equal to |x i | s . The following proposition highlights the difference between 3B filtering and CID filtering. This theoretical property is based on the fact that, due to the hull operation in VarCID, the whole box B can be reduced on several, possibly all, dimensions. With VarShaving, the pruning effort can impact only x i , losing all the temporary reductions obtained on the other variables by the different calls to F . Proposition 1 states that the pruning capacity of CID is greater than the one of 3B. In the general case however, 3B-consistency and CID-consistency are not comparable because s is the exact number of calls to subfiltering F inside VarCID (i.e., the upper bound is reached), while s is an upper bound of the number of calls to 2B by VarShaving. Experiments will confirm that a rough work on a given variable with CID (e.g., setting s = 4 ) yields better results than a more costly work with 3B (e.g., setting s = 10).

The 3BCID Filtering Algorithm

As mentioned above, the 3B and CID filtering operators follow the same scheme, so that several hybrid algorithms have been imagined. The most promising version, called 3BCID, is presented in this paper.

3BCID manages two parameters : the numbers s CID and s 3B of slices for the CID part and the shaving part. Every variable x i is handled by a shaving and a VarCID process as follows.

The interval of x i is first split into s 3B slices handled by shaving. Using a subfiltering operator F , a simple shaving procedure tries to refute these slices to 3 An additional assumption related to floating-point numbers and to the fixed-point criterion is required in theory to allow a fair comparison between algorithms: the 2B/Box subfiltering operator must work with a subdivision of the slices managed by 3B and CID.

the left and to the right (no dichotomic process is performed). Let s lef t (resp. s right ) be the leftmost (resp. rightmost) slice of x i that has not been refuted by subfiltering, if any. Let x i be the remaining interval of x i , i.e., s lef t ≤ x i ≤ x i ≤ s right . Then, if x i is not empty, it is split into s CID slices and handled by CID. One performs the hull of the (at most) s CID + 2 boxes handled by the subfiltering operator F : s lef t , s right and the s CID slices between s lef t and s right .

It is straightforward to prove that the obtained partial consistency is stronger than 3B(s 3B )-consistency.

The experiments will show that 3BCID with s CID = 1 can be viewed as an improved version of 3B where constructive disjunction produces an additional pruning effect with a low overhead.

A New CID-Based Splitting Strategy

There are three main splitting strategies (i.e., variable choice heuristics) used for solving numerical CSPs. The simplest one follows a round-robin strategy and loops on all the variables. Another heuristic selects the variable with the largest interval. A third one, based on the smear function [START_REF] Neumaier | Interval Methods for Systems of Equations[END_REF], selects a variable x i implied in equations whose derivative w.r.t. x i is large.

The round-robin strategy ensures that all the variables are split in a branch of the search tree. Indeed, as opposed to finite-domain CSPs, note that a variable interval is generally split (i.e., instantiated) several times before finding a solution (i.e., obtaining a small interval of width less than the precision). The largest interval strategy also leads the solving process to not always select a same variable as long as its domain size decreases. The strategy based on the smear function sometimes splits always the same variables so that an interleaved schema with round-robin, or a preconditionning phase, is sometimes necessary to make it effective in practice.

We introduce in this section a new CID-based splitting strategy. Let us first consider different box sizes related to (and learnt during) the VarCID procedure applied to a given variable x i :

-Let OldBox i be the box B just before the call to VarCID on x i . Let NewBox i be the box obtained after the call to VarCID on x i . -Let B l i and B r i be the left and right boxes computed in VarCID, after a reduction by the F filtering operator, and before the Hull operation.

The ratio ratioBis leads to an "intelligent" splitting strategy. The ratio

ratioBis= f (Size(B l i ),Size(B r i )) Size(NewBox)
, where f is any function that aggregates the size of two boxes (e.g., sum), in a sense computes the size lost by the Hull operation of VarCID. In other words, B l i and B r i represent precisely the boxes one would obtain if one splits the variable x i (instead of performing the hulloperation) immediately after the call to VarCID; NewBox is the box obtained by the Hull operation used by CID to avoid a combinatorial explosion due to a choice point.

Thus, after a call to LoopCID, the CID principle allows us to learn about a good variable interval to be split: one selects the variable having led to the lowest ratioBis. Although not related to constructive disjunction, similar strategies have been applied to finite-domain CSPs [START_REF] Geelen | Dual Viewpoint Heuristics for Binary Constraint Satisfaction Problems[END_REF][START_REF] Refalo | Impact-Based Search Strategies for Constraint Programming[END_REF].

Experiments, not reported here, have compared a large number of variants of ratioBis with different functions f . The best variant is ratioBis

= Size(B l i )+Size(B r i ) Size(NewBox)
.

Experiments

We have performed a lot of comparisons and tests on a sample of 20 instances. These tests have helped us to design efficient variants of CID filtering.

Benchmarks and Interval-Based Solver

Twenty benchmarks are briefly presented in this section. Five of them are sparse systems found in [START_REF] Neveu | When Interval Analysis helps Interblock Backtracking[END_REF]: Hourglass, Tetra, Tangent, Ponts, Mechanism. They are challenging for general-purpose interval-based techniques, but the algorithm IBB can efficiently exploit a preliminary decomposition of the systems into small subsystems [START_REF] Neveu | When Interval Analysis helps Interblock Backtracking[END_REF]. The other benchmarks have been found in the Web page of the COPRIN research team or in the COCONUT Web page where the reader can find more details about them [START_REF]Web page of COPRIN[END_REF]. The precision of the solutions. i.e., the size of interval under which a variable interval is not split, is 1e -08 for all the benchmarks, and 5e -06 for Mechanism. 2B is used for all the benchmarks but one because it is the most efficient local consistency filtering when used alone inside 3B or CID. Box+2B is more adequate for Yamamura8. All the selected instances can be solved in an acceptable amount of time by a standard algorithm in order to make possible comparisons between numerous variants. No selected benchmark has been discarded for any other reason! All the tests have been performed on a Pentium IV 2.66 Ghz using the interval-based library in C++ developed by the second author. This new solver provides the main standard interval operators such as Box, 2B, interval Newton [START_REF] Neumaier | Interval Methods for Systems of Equations[END_REF]. The solver provides round-robin, largest-interval and CID-based splitting strategies. Although recent and under developement, the library seems competitive with up-to-date solvers like RealPaver [START_REF] Granvilliers | RealPaver: An Interval Solver using Constraint Satisfaction Techniques[END_REF]. For all the presented solving techniques, including 3B and 3BCID, an interval Newton is called just before a splitting operation iff the width of the largest variable interval is less than 1e -2.

Results Obtained by CID

Table 1 reports the results obtained by CID(s, w-hc4, n ), as defined in Section 4.

The drastic reduction in the number of required bisections (often several orders of magnitude) clearly underlines the filtering power of CID. In addition, impressive gains in running time are obtained by CID for the benchmarks on the top of the table, as compared to standard strategy using 2B or 2B+Box, an interval Newton and a round-robin splitting policy 4 .

CID often obtains better running times than the standard strategy, except on Bellido, Trigexp2-5 and Caprasse, for which the loss in performance is small. However, it is not reasonable to propose to the user an operator for which three parameters must be tuned by hand. That is why we have also reported the last three CID columns where only 0 or 1 parameter has been tuned. The default values (fourth CID column with s = 4, w-hc4= 10%, n = n) yield very good results: it outperforms the standard strategy in 15 of the 21 instances. In particular, setting s = 4 provides the best results in 12 of the 21 instances.

The second and third CID columns report very good results obtained by a filtering algorithm with only one parameter to be tuned (like with 2B or Box). Hence, since CID with only parameter n to be tuned (second CID column) allows a continuum between pure 2B and CID (n = 0 amounts to a call to 2B), a first recommendation is to propose this CID variant in interval-based solvers.

The second recommendation comes from a combinatorial consideration. In a sense, constructive interval disjunction can be viewed as a "polynomial-time splitting" since VarCID performs a polynomial-time hull after having handled the different slices. However, the exponential aspect of (classical) bisection becomes time-consuming only when the number of variables becomes high. This would explain why CID cannot pay off on Trigexp2-5 and Caprasse which have a very small number of variables and lead to no combinatorial explosion due to bisection. (The intuition is confirmed by the better behavior of CID on the (scalable) variant of Trigexp2 with 9 variables.) Thus, the second recommendation would be to use CID on systems having a minimal number of variables, e.g., 5 or 8.

Comparing CID, 3B and 3BCID

Table 2 reports the results obtained by CID, 3B and 3BCID (see Section 5). All the results have been obtained with a parameter w-hc4 set to 5%.

Several trials have been performed for every algorithm, and the best result is reported in the table. For 3B, seven values have been tried for the parameter s 3B : 4, 5, 7, 10, 20, 50, 100.

For CID, nine values of the parameters have been tried: five values for the number of slices s CID (2, 3, 4, 6, 8; fixing n = n), and four values for the parameter n (1, 0.5n, 0.75n, 1.2n; fixing s CID = 4). For 3BCID, eight combinations of parameters have been tried: four values for s CID (1,2,3,4) combined with two values for s 3B [START_REF] Neumaier | Interval Methods for Systems of Equations[END_REF]20). The main conclusions drawn from Table 2 are the following:

-3BCID and CID always outperform 3B. Even the standard strategy outperforms 3B for 9 benchmarks in the bottom of the table. -3BCID is competitive with CID. 3BCID is better than CID concerning 11 benchmarks. CID remains even better for Mechanism. We wonder if it is related to its large number of variables.

The good news is that the best value for s CID in 3BCID is often s CID = 1. In only four cases, the best value is greater, but the value s CID = 1 also provides very good results. This suggests to propose 3BCID with s CID = 1 as an alternative of 3B. In other words, 3BCID with s CID = 1 can be viewed as a promising implementation of 3B. This is transparent for a user who has to specify the same parameter s 3B , the management of constructive disjunction being hidden inside 3BCID (that performs a Hull operation of at most 3 boxes since s CID = 1).

Comparing Splitting Strategies

Table 3 applies the three available splitting strategies to CID with n = n and s = 4. We underline some observations. The new CID-based splitting strategy is better than the other strategies on 13 of the 20 instances, especially on Design. The largest interval strategy is the best on only one instance. The round-robin strategy is the best on 6 instances. On the 7 instances for which the CID-based strategy is not the best, the loss in performance is significant on Hayes.

The behavior of the CID-based strategy with s = 6 (not reported here) is even better, the round-robin strategy being the best on only 3 instances. This would suggest that the ratioCID learned during a VarCID operation is more accurate with a higher number of slices.

Conclusion

This paper has introduced two new filtering operators based on the constructive disjunction principle exploited in combinatorial problems. The first experimental results are very promising and we believe that CID and 3BCID have the potential to become standard operators in interval constraint solvers. The CID operator also opens the door to a new splitting strategy learning from the work of CID filtering.

The experiments lead to clear recommendations concerning the use of these new filtering operators. First, CID can be used with fixed values of parameters s and w-hc4, letting the user only tune the third parameter n (i.e., the number of variables that are varcided between 2 bisections). This allows the user to select in a sense a rate of CID filtering, n = 0 producing the pure 2B/Box. Used this way, CID could maybe subsume existing filtering operators. Second, 3BCID with s = 1 can be provided as a promising alternative of a 3B operator.

Several questions remain open. It seems that, due to combinatorial considerations, CID is not convenient for small problems while it seems more interesting for large-scale systems. A more complete experimental study should confirm or contradict this claim. Also, 3BCID should be compared to the weak-3B operator implemented in RealPaver [START_REF] Granvilliers | RealPaver: An Interval Solver using Constraint Satisfaction Techniques[END_REF] 5 . A comparison with filtering algorithms based on linearization, like Quad [START_REF] Lebbah | A Rigorous Global Filtering Algorithm for Quadratic Constraints[END_REF], will be performed as well.

Moreover, the CID-based splitting strategy merits a deeper experimental study. In particular, a comparison with the smear function will be performed once the latter is implemented in our solver.

An interesting future work is to propose adaptive variants of CID that can choose which specific variable should be varcided or bisected next.

Fig. 1 .

 1 Fig. 1. Shaving and CID-consistency on a simple example with two constraints. The constraints are represented with their intersection in dark gray. Left: The first two steps of 3B. Right: the result of VarCID on variable x1 (with 2 slices). The subboxes B l 1 and B r 1 are represented with thick borders; the resulting box appears in dotted lines.

  s, xi, B) /* the j th sub-box of B on xi */ sliceBox' ← F (X, C, sliceBox) /* perform a partial consistency */ B ← Hull(B , sliceBox') /* Union with previous sub-boxes */ end B ← B end.

Proposition 1 .

 1 Let P = (X, C, B) be an NCSP. Consider the box B obtained by CID(s,w) w.r.t. 2B and the box B obtained by 3B(s,w) 3 . Then, CID(s,w) filtering is stronger than 3B(s,w) filtering, i.e., B is included in or equal to B .

Table 2 .

 2 Comparison between CID, 3B and 3BCID. The first three columns recall resp. the name of the benchmark, its number of variables and the CPU time in seconds required by the strategy 2B/Box + Newton + bisection with round-robin. The other columns report the CPU time required to solve the benchmarks with CID, 3B and 3BCID. The best CPU time result is bold-faced.

	Name	n 2B/Box CID 3B 3BCID(sCID = 1) 3BCID(sCID = 2)
	BroydenTri 32 758 0.23 0.22	0.18	0.19
	Hourglass 29	24	0.45 0.73	0.43	0.50
	Tetra	30 401 13.6 20.7	17.1	18.8
	Tangent	28	32	4.13 8.67	3.18	4.13
	Reactors	20 156 18.2 24.2	15.5	16.9
	Trigexp1	30 3.4 0.10 0.26	0.12	0.11
	Discrete25 27 5.2 1.37 2.19	1.26	1.13
	I5	10 692 139 144	115	123
	Transistor 12 179 71.5 77.9	49.3	46.9
	Ponts	30 10.8 3.07 5.75	4.19	4.43
	Yamamura8	8	13	9.0 9.1	10.3	10.7
	Design	9 395 300 403	228	256
	D1	12 4.1 1.78 2.99	1.64	1.76
	Mechanism 98 111	79 185	176	173
	Hayes	8 155	99 188	102	110
	Kinematics1 6	84 76.1 136	76.6	81.4
	Eco9	8	26 19.3 40.1	27.0	30.3
	Bellido	9	80	95 143	93	102
	Trigexp2-9 9 61.8 52.2 74.5	39.9	45.1
	Caprasse	4 2.6 3.1 9.38	4.84	5.35

Note that optimized implementations of SAC reuse the domains obtained by subfiltering in subsequent calls to the shaving of a same variable.

From a theoretical point of view, in order that the stop criterion leads to a (non unique) fixed-point, it is necessary to return the box obtained just before the last filtering, i.e., the box in P old in Algorithm CID.

Note that this strategy is inefficient for Trigexp1 (solved in 371 seconds) and for Mechanism (that is not solved after a timeout (TO) of several hours). However, a reasonable running time can be obtained with a variant of 2B that push all the constraints of the NCSP in the propagation queue after every bisection.

An implementation of both operators in a same solver would lead to a fair comparison.

Acknowledgements

Special thanks to Olivier Lhomme for useful discussions about this research. Also thanks to Bertrand Neveu, Arnold Neumaier and the anonymous reviewers.

Table 1. Comparison between [CID + interval Newton + round-robin bisection strategy] and [a standard strategy]: 2B/Box + interval Newton + round-robin splitting. n is the number of variables. The column #s yields the number of solutions. The first column w-hc4 is the user-defined parameter w-hc4 used by 2B or Box. The last 3 columns s, w-hc4 and n indicate the values of parameters that have been tuned for CID (first CID column). The second CID column reports the results of CID when s = 4 and w-hc4 = 10%, i.e., when only n is tuned. The third CID column reports the results of CID when s = 4 and n = n, i.e., when only w-hc4 is tuned. The fourth CID column reports the results of CID with the default values for parameters, i.e., s = 4, w-hc4= 10%, n = n. Every cell contains two values: the CPU time in seconds to compute all the solutions (top), and the number of required bisections (bottom). For every benchmark, the best CPU time is bold-faced.


Nicolas Pessemier
email: pessemie@lifl.fr

Olivier Barais
email: barais@lifl.fr

Lionel Seinturier
email: seinturi@lifl.fr

Thierry Coupaye
email: thierry.coupaye@rd.francetelecom.com

Laurence Duchien
email: duchien@lifl.fr

A Three Level Framework for Adapting Component-Based Systems

This paper deals with the issue of software adaptation. We focus on Component-Based Software Development including Architecture Description Languages, and clearly identify three levels of adaptation. We argue that capturing functional and non-functional changes in a system requires various types of adaptation tools working at different granularities and times in the system lifecycle, with various actors.

Introduction

Adaptation has always been an important challenge for software engineering. Systems have to be continuously revised to address new functional or nonfunctional requirements, changing environment. The need for adaptation may appear at any time in the software lifecycle: development, deployment, supervision and maintenance (evolutive, corrective). Changes that can be anticipated at development and deployment time are referred to as static adaptation, and changes applied at execution time without stopping the system, as dynamic adaptation. Maintenance changes can be done statically or dynamically.

Researchers have come with various solutions to address the issue of adaptation. These include model transformations in Model Driven Engineering [START_REF]OMG MDA specification[END_REF], approaches based on reflection [START_REF] Maes | Meta-Level Architectures and Reflection[END_REF], adaptive agent platforms [START_REF] Mathieu | Principles for dynamic multi-agent organizations[END_REF], object and component-based approaches that propose open containers in EJB and CCM models [START_REF] Popovici | Spontaneous Container Services[END_REF], component assembly reconfiguration [START_REF] Dowling | The k-component architecture meta-model for selfadaptive software[END_REF][START_REF] Bruneton | An open component model and its support in Java[END_REF], adaptors for component [START_REF] Becker | The impact of software component adaptors on quality of service properties[END_REF], and Aspect Oriented Programming techniques (AOP) [START_REF] Vanderperren | JAsCoAP: Adaptive programming for componentbased software engineering[END_REF][START_REF] Pawlak | JAC : An aspect-based distributed dynamic framework[END_REF].

In this position paper, we propose a multi-level model that aims at capturing static and dynamic changes in a Component-Based Software Development (CBSD) and Architecture Description Languages (ADLs) context. We promote the use of AOP techniques to enable the integration for both functional and nonfunctional adaptation. Context-aware and auto-adaptive mechanisms are out of the scope of this paper.

The paper is structured as follows. Section 2 identifies the different adaptation levels, and describes the adaptation techniques currently available at each level. Section 3 shows how our recent work integrating components and aspects, Fractal 1 Aspect Component (FAC) [START_REF] Pessemier | Components, ADL & AOP: Towards a common approach[END_REF] addresses one of the levels identified in Section 2. Section 4 explains how we envision a framework that captures all of these levels. Finally, Section 5 gives conclusions and future work.

Three levels of adaptation

Numerous component models have emerged the last two decades, targeting applications, systems, middleware and operating systems. In this paper, we focus on Component-Based Software Development (CBSD), which is concerned with the assembly of highly reusable and configurable software components [START_REF] Szyperski | Component Software: Beyond Object-Oriented Programming[END_REF], including Architecture Description Languages (ADLs) [START_REF] Medvidovic | A classification and comparison framework for software architecture description languages[END_REF], which clarify and ease the description of component assemblies.

This section identifies the entities that need to be adapted because of changes in functional and non-functional requirements. In the CBSD and ADLs contexts, one may want to adapt a component access points, the bindings between heterogeneous components, the composition of a composite component, or some programs that represent component behavior. We identify three separate levels of adaptation, each of them working at various granularities: architecture, component and program levels of adaptation.

Architecture level adaptation A system architecture defines a plan that clearly represents the system structure, indicating how components are bound together, as well as the nesting relationship between components. Architecture adaptation relies on reconfiguration and recomposition of the component assembly: adding or replacing a component, inserting connectors between heterogeneous components, changing the component hierarchy, and so on.

By considering a software architecture description as a model, model transformation approaches based on Model Driven Engineering (MDE) adapt the architecture through successive transformations. For example, TranSAT is a framework for adapting a software architecture to new concerns through transformations [START_REF] Barais | A framework to specify incremental software architecture transformations[END_REF].

Transformation is not the only adaptation mechanism. To deal with the assembling of heterogeneous COTS components, connectors that adapt the incoming and outcoming component operations are generally used. For example, Unicon proposes specific adaptors that are connectors, which mediate interactions among components by specifying protocols [START_REF] Shaw | Abstractions and implementations forarchitectural connections[END_REF].

Component level adaptation A component is a unit for the management of configuration, security, faults, etc., i.e., a functional entity together with a set of associated non-functional properties. These non-functional properties are typically handled by so-called "containers" in component models such as Enterprise JavaBeans or the CORBA Component Model, or "membranes" in the Fractal component model which embody interception-based mechanisms such as reflection or AOP.

Various techniques based on the interception of the original component behavior are employed to adapt components, such as K-Component [START_REF] Dowling | The k-component architecture meta-model for selfadaptive software[END_REF], the opencontainer approach [START_REF] Popovici | Spontaneous Container Services[END_REF]. The K-Component model relies on a specific adaptation language (Adaptation Contract Description Language) and an adaptation manager that is aware of any changes and can adapt the base system through structural reflection. The open-container approach enables new technical services to be added to EJB and CCM containers.

Program level adaptation

At this level, we consider programs as entities encapsulated by components. Numerous techniques exist to perform program adaptation, such as AOP [START_REF] Vanderperren | JAsCoAP: Adaptive programming for componentbased software engineering[END_REF][START_REF] Pawlak | JAC : An aspect-based distributed dynamic framework[END_REF], reflection [START_REF] Maes | Meta-Level Architectures and Reflection[END_REF], program transformation [START_REF] Visser | A Survey of Rewritting Strategies in Program Transformation Systems[END_REF], e.g. Java byte-code transformations (e.g. ASM [16]).

Dynamic component adaptation with FAC

This section presents our solution to the dynamic component adaptation issue with our most recent work, Fractal Aspect Component (FAC), which introduces AOP concepts into the Fractal component model [START_REF] Bruneton | An open component model and its support in Java[END_REF]. A previous paper [START_REF] Pessemier | Components, ADL & AOP: Towards a common approach[END_REF] presented the basic elements of the first version of FAC. This Section sums up its features and discusses the issue of software adaptation with FAC. Our previous work on JAC [START_REF] Pawlak | JAC : An aspect-based distributed dynamic framework[END_REF] and TranSAT [START_REF] Barais | A framework to specify incremental software architecture transformations[END_REF] covers the program and architecture levels, respectively.

The first subsection introduces the Fractal component model, then its extension FAC for AOP. Finally, we present how FAC addresses adaptation at the component level described in Section 2.

Fractal

Fractal [START_REF] Bruneton | An open component model and its support in Java[END_REF] is a general software component model with the following mean features:

dynamic components, interfaces and bindings: components are runtime entities that do exist at runtime and can be manipulated as such for management purpose. Components communicate through bindings between interfaces, which are the only access points to components. A binding is a communication channel between a client interface and a server interface. hierarchical components: composite components contain recursively primitive components at arbitrary levels to provide a uniform view of software systems at various levels of abstraction. shared components: a (sub)component can be contained in several (super) components,. This is very useful typically to model resources which are intrinsically shared. reflexive components: architectural introspection for system monitoring and intercession for dynamic reconfiguration.

openness: the model is defined as a set of concepts (component, interface, binding, membrane, controller, etc.) embodied in an API. It typically proposes some APIs to configure components assemblies by means of binding (between client and server interfaces), containment and lifecyle (start, stop). Controllers that are optional, can be specialized and extended at will, and of course new controllers can be defined.

Interestingly here, a Fractal component is composed out of a membrane and a content. The content is either a primitive component in an underlying programming language or a set of components. The membrane embodies most of the reflexive capabilities by means of controllers that can export or not control interfaces. In Julia, a Java execution support for Fractal components, a mixinbased mechanism is used to build controllers that are composed, if needed, with interceptors to build membranes that control the encapsulated components. In AOKell, another Java execution support for Fractal component under development by the authors, (AspectJ) aspects are used to program membranes.

FAC

FAC is an extension of Fractal, which integrates the notion of aspects into the Fractal model. It aims at capturing the crosscutting properties of a system. In FAC, aspects are Fractal components, called Aspect Components, with a specific server interface implementing the AOP Alliance API 3 .

Aspect Components are woven and unwoven at run-time. The process of weaving is very similar to the process of binding a functional client interface and a server interface in Fractal. We call a crosscutting binding the interaction between a set of components and an aspect component. Crosscutting bindings are defined by an API or at the ADL level. Pointcuts are defined through regular expressions when a crosscutting binding is defined. A pointcut selects the components, interfaces and methods on which the aspect component will apply. FAC allows structural and behavioral pointcuts as we will see in the following subsection.

Runtime adaptation with FAC

In FAC adding a new behavior consists of writing the new behavior in an aspect component and defining where this new behavior applies. The way the new behavior will be triggered can be expressed with structural or behavioral specifications.

Structural elements, such as a method signature, a functional interface, or a component, can be used as joinpoints in the system. Each required or provided operation defined by a component can potentially be intercepted and augmented with new features.

FAC allows an aspect to be triggered on a specific sequence of external component interactions. Each component interaction is captured by the aspect component that will be triggered if the sequence of interactions matches. Cflows in JAsCo [START_REF] Vanderperren | JAsCoAP: Adaptive programming for componentbased software engineering[END_REF], EAOP [START_REF] Douence | A model and a tool for event-based aspect-oriented programming (EAOP)[END_REF] and AspectJ can similary trigger aspects on protocols. These approaches work at the program level, whereas FAC works at the component level.

Towards an integration of the three levels

Our objective is to build a three level model (architecture, component, program), which captures any functional and non-functional changes at any time in the software lifecycle. In our vision, the model needs to address the following issues:

who realizes the modifications: the architect, the programmer, the administrator, when are the modifications applied: static or dynamic adaptation, Different actors are involved in a system lifecycle. Each actor needs to perform adaptation at the level he works with. For example, an architect would perform architecture and component level adaptation; a programmer would perform program adaptation. The important point here is that each actor needs a way to adapt the system at a step of the lifecycle. The three levels can fulfill these needs. The issue of who will adapt the system when changes need to be performed remains open.

The three levels need to capture both static and dynamic adaptation. Predictable changes can be defined through adaptation policies. If static adaptation is important, unpredictable changes might appear during run-time. Currently runtime changes are addressed by FAC at the component level.

Our objective is to extend FAC to the architecture and the program levels. Previous works around TranSAT and JAC will inspire the extension.

Conclusions & future work

We have proposed a three-level model for adaptation in a component-based context. We have shown that in order to capture any changes in a component system, different granularities have to be considered.

The architecture is likely to evolve through transformations and reconfigurations of components interactions and composition. Component interfaces frequently need to be adapted to new requirements. Finally, when changes apply to specific part of a program encapsluted into a component, only this part needs to be updated or intercepted.

Our proposal uses AOP techniques at the three levels due to its ability to ease the integration of crosscutting concerns.

Open issues For the moment, only the component level is fully integrated into the Fractal component model. When assembling the three levels, we are likely to run into consistency issues. The connection between each level is a true challenge. For example, what happens to a previously adapted component when the architecture is restructured.

The model allows various actors to add aspects at the three different levels. The architect defines a set of transformation rules. The programmer independently introduces aspects at the lower (program) level. The question of the administrator remains undefined. More likely, he will have to deal with aspects at the three levels.

The question of applying changes at design time or runtime is still open. For example, the question of adapting architecture at run-time through transformations certainly requires precautions.

Acknowledgment

This work was partially funded by France Telecom under the external research contract number 46 131 097.

AOP Alliance http://sourceforge.net/projects/aopalliance is an open-source initiative to define a common API for AOP frameworks. The API is implemented by Spring and JAC[START_REF] Pawlak | JAC : An aspect-based distributed dynamic framework[END_REF].