Qiang Li

Romain Berraud-Pache

Yongjie Yang

Christelle Souprayen

Maguy Jaber
email: maguy.jaber@sorbonne-universite.fr

Biocomposites based on bentonite and Lecithin: an experimental approach supported by molecular dynamics

Keywords: organoclay, bentonite, lecithin, bio-surfactant, molecular dynamics

Natural bio-surfactants have recently attracted much more attention due to their biodegradability and biocompatibility. They are often associated with clay materials to synthesize organoclays and can therefore be ideal materials for environmentally friendly oil-based drilling fluids. In this study, a bio-organoclay was obtained by modifying bentonite with natural soybean lecithin, and the effects of reaction temperature, time, pH, and lecithin concentration on the properties of modified bentonite were analyzed. Structural insights such as clay properties, intercalation process and lecithin organization were obtained using a large variety of experimental techniques and molecular dynamics simulations. The results of this study suggest that some experimental conditions have an important impact on the basal space of the bentonite. Reaction time and temperature did not have a significant effect on the final properties of the modified bentonite. However, by increasing the pH of the clay material or with a high concentration of lecithin, the interlayer space fluctuates from 1.21 to 5.96 nm. The lecithin molecules adopt a new spatial conformation in the interlayer space becoming perpendicular to the clay surface, which largely increase the interlayer space.

Introduction

Clay minerals have been known and applied since antiquity as one of the most important groups of geomaterials. Clay minerals are generally regarded as a group of phyllosilicates whose particles are less than 2 m. The phyllosilicates structures are based on tetrahedral (T) and octahedral (O) sheet, which can form anisotropic TO or TOT layer in a 1:1 or 2:1 ratio [START_REF] Bergaya | Chapter 1 General Introduction: Clays, Clay Minerals, and Clay Science[END_REF]. Stacking of these layers by van der Waals force or weak dipolar interaction lead to the creation of interlayers space which are occupied by inorganic cations, balancing the charge deficiency caused by isomorphous substitution of the sheets [START_REF] Xie | Thermal characterization of organically modified montmorillonite[END_REF]. Clay minerals have become essential in modern industry and everyday's life thanks to being abundant, inexpensive and environmentally friendly. In the past two decades, the application of clay minerals in rheological control agents, oil-based drilling fluid, adsorbents of organic pollutants, paints and cosmetics have been widely reported [START_REF] Li | Recent researches on natural pigments stabilized by clay minerals: A review[END_REF][START_REF] Lima | Saponite-anthocyanin derivatives: The role of organoclays in pigment photostability[END_REF][START_REF] Park | Structural characterisation and environmental application of organoclays for the removal of phenolic compounds[END_REF][START_REF] Trigueiro | Going through the wine fining: Intimate dialogue between organics and clays[END_REF][START_REF] Zhuang | Organoclays used as colloidal and rheological additives in oil-based drilling fluids: An overview[END_REF]. Nowadays, modification of clay minerals has attracted more and more attention [START_REF] Pereira | Green biosorbents based on chitosan-montmorillonite beads for anionic dye removal[END_REF][START_REF] Xavier | Thermally activated palygorskites as agents to clarify soybean oil[END_REF], and the exploration of novel modification methods on clay minerals has never stopped [START_REF] Zhu | Novel intercalation mechanism of zwitterionic surfactant modified montmorillonites[END_REF].

Bentonite, has gathered considerable research interest due to its availability in mine deposits and soils, nontoxic nature, and high cation exchange capacity (CEC) [START_REF] Churchman | Chapter 11.1 Clays and Clay Minerals for Pollution Control[END_REF]. Montmorillonite (Mt), the main ingredient of bentonite, belongs to the smectite groups where two silica tetrahedral sheets are layered between an alumina octahedral sheet (TOT) [START_REF] Cui | A novel material of cross-linked styrylpyridinium salt intercalated montmorillonite for drug delivery[END_REF]. The montmorillonite layers are negatively charged due to isomorphic substitution [START_REF] Bergaya | Handbook of clay science[END_REF]. In general, the aluminum cations in the octahedral sheet is replaced by magnesium ones. Owing to the special properties of montmorillonite, organic modification by exchange the interlayer inorganic cations by organic ones is commonly used to develop organoclays.

In previous studies, quaternary ammonium salts were widely applied in montmorillonite modification and exhibit superior performances in oil-based drilling fluid [START_REF] Zhuang | Comparative study on the use of cationic-nonionic-organo-montmorillonite in oil-based drilling fluids[END_REF]; [START_REF] Zhou | Applied properties of oil-based drilling fluids with montmorillonites modified by cationic and anionic surfactants[END_REF]; [START_REF] Zhang | Effect of modification extent of montmorillonite on the performance of starch nanocomposite films[END_REF]; [START_REF] Makhoukhi | Preparation, characterization and thermal stability of bentonite modified with bis-imidazolium salts[END_REF][START_REF] Makhoukhi | Synthesis of bisimidazolium-ionic liquids: Characterization, thermal stability and application to bentonite intercalation[END_REF][START_REF] Xie | Thermal Stability of Quaternary Phosphonium Modified Montmorillonites[END_REF], notably a better dispersibilty.

Furthermore, the intercalation of oil between the montmorillonite layers induces the layers to swell and exfoliate while the edges and faces of the dispersed layers form a "kind of house-of-cards structure" resulting in a gel system [START_REF] Agwu | A critical review of drilling mud rheological models[END_REF].

However, the quaternary ammonium salt and quaternary phosphonium salt surfactants usually induce environmental problems due to their toxicity and poor biocompatibility.

This limitation restricts their potential use in some application fields [START_REF] Liu | Preparation and characterization of organo-vermiculite based on phosphatidylcholine and adsorption of two typical antibiotics[END_REF].

In the last few years, there has been a tremendous amount of interest and various efforts regarding the preparation of bio-organoclays to solve the main problems listed above, notably biocompatibility [START_REF] Biswas | Biocompatible functionalisation of nanoclays for improved environmental remediation[END_REF]. Phospholipids, especially lecithin, have been reported to be good candidates to synthesize bio-organoclays. [START_REF] Merino | Preparation and characterization of soy lecithin-modified bentonites[END_REF] investigated the effect of lecithin concentration and reaction time on modified bentonite and considered that lecithin-bentonites are promising eco-friendly fillers for bio and nanocomposites. [START_REF] Nagy | Intercalation of lecithins for preparation of layered nanohybrid materials and adsorption of limonene[END_REF] studied the adsorption characteristics of nanocomposites containing lecithin and bentonite composite. In addition, the hybrid materials obtained from lecithin-modified clay minerals have received great attention in the fields of biomedicine and pharmaceuticals [START_REF] Dening | Montmorillonite-lipid hybrid carriers for ionizable and neutral poorly water-soluble drugs: Formulation, characterization and in vitro lipolysis studies[END_REF][START_REF] Ruiz-Hitzky | CLAY-BASED BIOHYBRID MATERIALS FOR BIOMEDICAL AND PHARMACEUTICAL APPLICATIONS[END_REF][START_REF] Sabzevari | Development and characteristics of layered EGCG/Montmorillonite hybrid: An oral controlled-release formulation of EGCG[END_REF].

Phospholipids are a class of lipids constituted of a phosphate polar head-group attached to non-polar hydrocarbon chains. Lecithin is one of the most common phospholipids and mainly composed of phosphatidylcholine (PC) [START_REF] Cui | Phospholipids in foods: prooxidants or antioxidants?[END_REF]. It can be extracted from vegetables and animal sources such as soybeans, rice beans, sunflower, marine sources, egg yolk, and milk. Lecithin extracted from soybeans is recognized to be more stable, safer, and affordable from the production point of view [START_REF] Le | Soy Lecithin-Derived Liposomal Delivery Systems: Surface Modification and Current Applications[END_REF]. PC contains a choline part, i.e. a positively charge trimethyl-amino group, in addition to the negative charge on the phosphate group [START_REF] Bot | Inter-relationships between composition, physicochemical properties and functionality of lecithin ingredients[END_REF]. The pKa value of the phosphate group is around 1.5 and it can be protonated at acidic conditions (pH<pKa), which means that the lecithin can exchange interlayer cations in clay minerals.

This publication deals with the preparation of new organoclays based on bentonite and soybean lecithin. The effects of reaction temperature, time, pH, and lecithin concentration on the properties of modified bentonite were analyzed by a variety of characterization techniques such as X-ray diffraction (XRD), Fourier transform infrared (FTIR), Thermogravimetric analyses (TG) and Molecular Dynamics simulations (MD). The interaction between bentonite and lecithin, the intercalation behavior, and the configuration of lecithin in the interlayer space are reported through experiments and molecular dynamics simulations. This study is expected to provide valuable insights into into the preparation of bioorganoclays from lecithin. In addition, some conditions can largely impact the physical properties of the organoclay and help design relevant environmentally-friendly materials.

Materials and methods

Modified bentonite preparation

Bentonite was first pre-swollen in distilled water and stirred for 16h, while lecithin was dissolved in ethanol. The 10 ml of 0.01g/ml bentonite dispersion was added to the 10 ml lecithin solution with different concentrations (0.1~3.0CEC) under constant stirring for 1.0h of contact time. The molecular structure and functional groups of PC (C 42 H 80 NO 8 P, molecular weight=758.06g/mol) are described in Fig. 1.

To adjust the pH of the mixture between 1.0 and 9.0, a solution of 6.0 mol/L of HCl was added dropwise. The solution was then sonicated and heated through an oil bath at different temperatures (room temperature, 40, 60, 80°C). After this, the mixture was centrifuged and the resulting precipitate washed several times with a 1:1 ethanol-distilled water solution. The resulting precipitate was dried in an oven at 60°C for 48h. Finally, the modified bentonite powder was finely ground in an agate mortar.

The schematic representation of experimental workflow followed for preparing organo-bentonite is provided in Fig. 2.

Further description of the materials and characterization technique are available in supplementary information (SI).

Results and discussion

Effect of reaction temperature

The effect of reaction temperature on the interlayer space and thermal stability of modified bentonite was studied by a series of experiments with pH=1.0 and 1.0CEC.

The XRD patterns of bentonite and modified bentonite prepared at different temperatures were shown in Fig. 3. The bentonite presented a reflection at 2θ=7.28° with a basal spacing d 001 of 1.21 nm. This reflection shifted to 2θ = 6.15° in the patterns of modified bentonite (room temperature), and the corresponding basal spacing is d 001 = 1.44 nm, indicating that the lecithin molecules were introduced into the bentonite interlayer space [START_REF] Songurtekin | Histidine modified montmorillonite: Laccase immobilization and application to flow injection analysis of phenols[END_REF]. Since the TOT layer thickness of montmorillonite is 0.96 nm, the lecithin intercalation increased the interlayer space of sample by 0.48 nm. The intercalation behavior is attributed to the monolayer arrangement of lecithin molecules in the interlayer space [START_REF] Ouellet-Plamondon | The effect of cationic, non-ionic and amphiphilic surfactants on the intercalation of bentonite[END_REF]. In addition, the XRD results of bentonite modified with lecithin at different temperatures showed that temperature do not have an effect on the intercalation behavior of lecithin. FTIR spectroscopy was applied to investigate and compare the functional groups present in raw bentonite, lecithin and modified bentonite. FTIR spectra (Fig. 3) of all modified bentonite samples displayed a band at 3620 cm -1 attributed to the -OH stretching vibration of the hydroxyl groups of the bentonite structure. The absorption band centered at around 1004 cm -1 is attributed to the Si-O-Si stretching band of bentonite [START_REF] Xue | FTIR investigation of CTAB-Al-montmorillonite complexes[END_REF]. The bands at 2924 cm -1 and 2853 cm -1 are assigned to the -CH 2 asymmetric and symmetric stretching vibrations of the lecithin, respectively [START_REF] Li | An FTIR investigation of hexadecyltrimethylammonium intercalation into rectorite[END_REF][START_REF] Zhang | Adsorption of mixed cationic-nonionic surfactant and its effect on bentonite structure[END_REF]. An intense band attributed to the C=O group of lecithin occurred at 1735 cm -1 , and another one centered at 1465 cm -1 belonged to the deformation vibrations of CH 2 /CH 3 [START_REF] Liu | Preparation and characterization of organo-vermiculite based on phosphatidylcholine and adsorption of two typical antibiotics[END_REF][START_REF] Nagy | Intercalation of lecithins for preparation of layered nanohybrid materials and adsorption of limonene[END_REF]. The presence of lecithin in the modified bentonite was confirmed by the appearance of the bands centered at 2924 cm -1 , 2853 cm -1 and 1465 cm -1 , respectively. The apparent shift of the C=O stretching band at 1735 cm -1 in lecithin to 1708 cm -1 in modified bentonites indicated possible interactions with the clay layers surface [START_REF] Merino | Preparation and characterization of soy lecithin-modified bentonites[END_REF].

Various reports in the literature indicated that thermogravimetric analysis is often used to research the thermal stability of organoclays [START_REF] Corcione | Characterization of Nanocomposites by Thermal Analysis[END_REF].

The way in which the mass loss steps occur provided information on the structure of the intercalated molecules [START_REF] Xi | Thermogravimetric analysis of organoclays intercalated with the surfactant octadecyltrimethylammonium bromide[END_REF]. The decomposition of bentonite modified with lecithin often occurs in three steps: dehydration of adsorbed water, lecithin decomposition, and silicate dehydroxylation [START_REF] Zhu | Preparation and characterization of zwitterionic surfactant-modified montmorillonites[END_REF].

The thermal gravimetric (TG) and differential thermogravimetry (DTG) results

for bentonite, lecithin and modified bentonite were compared in Fig. 3 and the lecithin loading amounts were calculated according to the formula in Eq. ( 1) [START_REF] Zhu | Novel intercalation mechanism of zwitterionic surfactant modified montmorillonites[END_REF])

𝑄 𝑙 = 𝑄 𝑚 (1-𝑄 𝑚 )×𝐶𝐸𝐶×𝑀 (1)
where 𝑄 𝑙 is the loading amount of lecithin, 𝑄 𝑚 is the mass loss in the temperature range of 150~450 °C, M is the molar mass of lecithin. The mass loss results of the modified bentonite and loading amount of lecithin are summarized in Table S1.

In the curve for bentonite (Fig. 3), two major peaks were presented. The first mass loss from the ambient temperature to 150°C and is assigned to dehydration of physisorbed and represent 6.9%. The other mass loss between 450°C and 900°C is attributed to the dehydroxylation of the aluminosilicate layer at 688°C [START_REF] Khalaf | Synthesis and characterization of cationic gemini surfactant modified Na-bentonite and its applications for rubber nanocomposites[END_REF]. The mass loss of lecithin mainly occurred between 150 and 450 °C with a mass loss of 73.5%. The temperature corresponding to the highest rate of mass loss was at 334°C for lecithin. These results were in accordance with previous literature reports [START_REF] Wicklein | Bio-organoclays based on phospholipids as immobilization hosts for biological species[END_REF]. Three steps of the mass loss were observed for the organoclays: the first mass loss which is attributed to the dehydration of physisorbed water varied between 1.5% and 1.8%. The most remarkable difference between the bentonite and the organic bentonite is in the temperature range 150~450°C. When the reaction was carried out at room temperature, 40°C, 60°C and 80°C, the second mass loss in the temperature of 150~450℃ was 34.4%, 32.5%, 31.4% and 25.7%, respectively, which is associated with lecithin decomposition [START_REF] Ouellet-Plamondon | The effect of cationic, non-ionic and amphiphilic surfactants on the intercalation of bentonite[END_REF]. It is found that there are two peaks in this range, the peaks at 200~260, 270~340 °C correspond to the decomposition of the adsorbed surfactant and intercalated surfactant lecithin, respectively. The third mass loss step between 450 to 900 °C is attributed to the dehydroxylation of the structural OH units of the bentonite.

As can be seen from Table S1, with the reaction temperature increase, the mass loss of loaded lecithin decreases from 0.58CEC (for room temperature) to 0.38CEC (for 80℃). This phenomenon occurs because temperature influences the lecithin molecules adsorption capacity.

The macroscale appearance of the organic bentonite samples obtained at different reaction temperature are shown in Fig. S1. There was an obvious difference in appearance characters of organic bentonite samples produced at different temperatures. The organic bentonite samples presented black flake solid at reaction temperature below 60°C, while the sample was the yellowish-brown powder when the temperature was 80°C. The reason for this result may be that temperature affects the adsorption capacity of lecithin molecules on the surface of bentonite. As the temperature increased, the adsorption capacity of lecithin on the bentonite surface decreased, which led to the diminution of the lecithin content in the organic bentonite.

Therefore, the appearance of samples changed from black flake solid to yellowish-brown powder. This was also consistent with the TG analysis results.

Effect of reaction time

The effect of the length of the reaction time on the properties of modified bentonite was also studied. The reaction temperature was set to 60℃. Then, the reaction time was varied from 0.5h to 6.0h. X-ray diffraction patterns of the modified bentonite at different reaction times were illustrated in Fig. 4. The bentonite showed an interlayer basal spacing of 1.21 nm. After 0.5h of reaction, the X-ray reflection of modified bentonite shifted to a lower angle and the basal spacing increased from 1.21 to 1.42 nm. This indicated that the intercalation behavior of lecithin molecules was completed at a short time (0.5h).

Additionally, the basal spacing d 001 values (~ 1.42 nm) and reflection intensity did not change for the organo-bentonite samples at different reaction time, which could be attributed to the monolayer arrangement of the lecithin molecules in the interlayer space. This finding indicated that reaction time had no effect on the basal spacing of the modified bentonite. The result has been found to be in good agreement with the literature [START_REF] Merino | Preparation and characterization of soy lecithin-modified bentonites[END_REF]. The bands in the FTIR spectra were consistent with the ones detailed in the previous section (i.e., the effect of reaction temperature). Upon intercalation with different reaction times, the FTIR experimental results remained consistent. It showed that the reaction time had no influence on the properties of lecithin-modified bentonite, which is agreement with the results of XRD.

The thermal stability of modified bentonite was evaluated by TG analysis and the results of samples were shown in Fig. 4. For modified bentonite, between 150 and 450°C, the mass loss is mainly caused by the lecithin decomposition. (32.6%). When the reaction time increased from 0.5h to 6.0h, the mass loss of lecithin decreased from 32.6% to 27.7%, which demonstrated that the lecithin molecules rearrangement were taken place with the increase of reaction time [START_REF] Merino | Preparation and characterization of soy lecithin-modified bentonites[END_REF][START_REF] Wicklein | Bio-organoclays based on phospholipids as immobilization hosts for biological species[END_REF]. The loaded amount of lecithin molecules slightly decreases with the increases of time. This was also evidenced from the appearance of the samples (Fig. S2). The appearance turned from flack solid to powder as the reaction time increase. The DTG of the modified bentonites showed two peaks between 150 and 450 °C, which are attributed to lecithin decomposition. It can be seen from Fig. 4, the intensity of the first peak increased with reaction time, whereas the second peak intensity decreased. Changes in the endothermic peak intensity suggested different conformation states and environments of lecithin in the modified bentonite [START_REF] Silva | Modification of bentonites with nonionic surfactants for use in organic-based drilling fluids[END_REF][START_REF] Wei Xie | Thermal Degradation Chemistry of Alkyl Quaternary Ammonium Montmorillonite[END_REF]. In addition, organo-bentonites began to decompose at slightly higher temperature with the reaction time increased.

Effect of pH

The effect of pH on the final performance of modified bentonite was studied.

The reaction temperature was set to 60℃ and the reaction time was 1.0h. The pH of the mixture solution was varied from pH=1.0 to pH=9.0. This showed that when the solution pH reached 3.0, lecithin molecules conformation has changed and the basal spacing was well expanded, increasing from 1.21 to 5.19 nm. The (001) reflections of samples at pH=5.0, 7.0, 9.0 appeared at 2θ = 1.69°, 1.71° and 1.72°, corresponding to d 001 -value of 5.22, 5.16 and 5.13 nm, respectively. In addition, the (002) reflection appears when mixture solution pH exceeds 3.0, indicating that more surfactants were intercalated into the layer, and multiple arrangement models of the lecithin molecule were formed [START_REF] Zhu | Preparation and characterization of zwitterionic surfactant-modified montmorillonites[END_REF]. It could be concluded that the pH value of the solution has a great effect on the basal spacing and the intercalation behavior of lecithin. Fig. 5 exhibited the FTIR spectra of modified bentonite under different reaction pH. The bands around 1735 cm -1 are attributed to the C=O group of lecithin and the bands at 1245 cm -1 is assigned to the PO 2 vibration [START_REF] Nzai | Determination of phospholipids in vegetable oil by fourier transform infrared spectroscopy[END_REF]. When pH=1.0, the band assigned to C=O stretching shifts from 1735 cm -1 to 1708 cm -1 , and the PO 2 vibration shifts from 1245cm -1 to 1200 cm -1 in modified bentonite. However, when the pH varied from pH=3.0 to pH=9.0, there was no shift of the C=O stretching band and the PO 2 vibration. The protonation of the phosphate group on lecithin is the main reason for this result. The discrepancy reflects the changes of the lecithin properties at different pH conditions. This change is not only directed by the lecithin molecule structure and conformation, but also by interaction with mineral surface. Phosphatidylcholine (PC), which is the main component of lecithin, contains a choline part that has a negative charge on the phosphate group and a positive charge on the trimethyl-amino group (Fig. 1) [START_REF] Bot | Inter-relationships between composition, physicochemical properties and functionality of lecithin ingredients[END_REF]. The pKa value of the phosphate groups PC is around 1.5 [START_REF] Ogawa | Production and Characterization of O/W Emulsions Containing Droplets Stabilized by Lecithin -Chitosan -Pectin Mutilayered Membranes[END_REF]. A.J. De Koning and K.B.

Mcmullan [START_REF] De Koning | Hydrolysis of phospholipids with hydrochloric acid[END_REF], who investigated the acid hydrolysis of phospholipids, have shown that the oxygen atom in the phosphate group is available for protonation. In a strongly acidic medium(pH<pKa), the phosphate group is protonated, resulting in a positively charged molecule. This change in properties causes different lecithin molecule arrangement, resulting in obvious increase in the interlayer space. The appearance characteristics of the organic bentonite samples indicated that the samples were homogeneous powder when the pH exceeds 3.0 (Fig. S3). The appearance of the samples also reveals the effect of pH on the intercalation behavior of lecithin.

The TG and DTG results for modified bentonite samples at different pH were shown in Fig. 5 and Table S3. When the pH of the solution is 1.0, the maximum mass loss is between 150 and 450°C (31.4%). However, it can be found that, when the pH is higher than 1.0, all the TG curves exhibited similar variation tendencies from room temperature to 900°C, and the amount of lecithin decomposition was around 28.0% and the loaded amount of lecithin was around 0.43CEC between 150 and 450 °C. The corresponding DTG curves in Fig. 5 showed that when pH≥3.0, there were two peaks.

The center of the peak was 318°C, corresponding to lecithin decomposition and the center of the peak was 615°C, corresponding to the dehydroxylation of the aluminosilicate layer, respectively. However, when pH=1.0, there was three peaks.

The centers of the peaks were 241,321 and 590°C, respectively. Lecithin molecules can exhibit cationic properties due to the protonated choline groups in the highly acid condition (pH=1.0), while display zwitterionic nature when pH≥3.0 [START_REF] Liu | Preparation and characterization of organo-vermiculite based on phosphatidylcholine and adsorption of two typical antibiotics[END_REF][START_REF] Ouellet-Plamondon | The effect of cationic, non-ionic and amphiphilic surfactants on the intercalation of bentonite[END_REF]. We have also observed that at pH = 1.0 there are more lecithin molecules absorbed that at pH= 3.0 (Table S3) despite having a smaller d 001 , i.e. 1.43 vs 5.19 nm. The main reason for this result is the interaction of protonated lecithin with the negatively charged clay surface at pH=1.0. Some surfactant molecules attach to the bentonite surface increased the amount of lecithin, which can be confirmed by a new peak at 241°C for DTG curves.

Effect of lecithin concentration

The effect of lecithin concentration on the interlayer space and thermal stability of modified bentonite was studied. The amounts of lecithin selected for the experiment were equivalent to 0.1, 0.5, 1.0, 2.0, and 3.0 times of the bentonite CEC.

The pH of the mixture solution was adjusted to pH=1.0, the temperature was set to 60℃ and the reaction time was 1.0h. .38, 1.43, 1.43, 5.96 and 5.52nm after modification with 0.1, 0.5, 1.0, 2.0 and 3.0CEC, respectively. When the lecithin concentration was between 0.1 and 1.0 CEC, the d 001 reflection increased slightly from 1.38 to 1.43 nm, which is correspond to lateral monolayer arrangement of the lecithin molecule. From 2.0 to 3.0 CEC, lecithin expanded the bentonite basal spacing d 001 up to nearly 5.52nm, which hold an interlayer space of 4.56nm (after subtraction of the TOT layer thickness value of 0.96 nm). These results indicated that the lipid bilayer adopt a different conformation in the interlayer space (Fig. 7). In regards to the length of one PC molecule (about 3nm) we can imagine that PC molecules are now perpendicular to the clay surface in an upright position. In addition, when the lecithin concentration is increased from 2.0 to 3.0 CEC, the 001 reflections turn to be much shaper and intensity become much higher, which suggested that the lecithin molecules arrangement in the clay layers were more ordered. For organic bentonite modified with 0.5, 1.0, 2.0CEC, the elemental composition of the samples were determined by XRF analysis, obtaining data in Table 1. The raw bentonite had alumina and silica as the major species, at 22.9% and 65.1% by weight, respectively. Na + and Ca 2+ are the main exchangeable cation of bentonite. It was found that P 2 O 5 were present in organic bentonite at 3.59%(0.5CEC), 6.17%(1.0CEC) and 11.4%(2.0CEC), respectively. This implies that the intercalation of lecithin molecules was successful by ion exchange. In addition, the experimental results suggest obvious decreases in the cations of the interlayer (Na + , Ca 2+ ), which confirms that cation exchange and replacement are the mechanisms of action in the modification process. The peaks that appeared in the FTIR spectra were consistent with the ones detailed in the previous section (i.e., the effect of reaction temperature). The absorption peak intensity of samples increased as a function of the lecithin concentration, indicating that more lecithin was adsorbed onto the clay surface and intercalated into the interlayer of bentonite. It can be seen from Fig. S4 that the sample color was getting darker and gradually changing from powder to flake solid.

This was mainly caused by the excessive loading of lecithin on the bentonite.

TG and DTG results also hint at a larger number of intercalated at higher lecithin concentrations (Table S4). The mass loss between 150°C and 450°C goes from 4.0% to 43.5% when the lecithin concentration is between 0.1 and 3.0CEC. For bentonite modified with 0.1CEC, the first degradation peak was observed at around 59°C, with a 6.7% mass loss assigned to the evaporation of the adsorbed water. When the temperature was between 150 and 450 °C, the sample exhibited only one degradation peaks at 255 °C, which can be attributed to the decomposition of intercalated lecithin molecules. The thermal decomposition stages for the 0.5CEC sample are similar to those for the 1.0CEC and 2.0CEC sample with DTG peaks (Fig. 6). But when the temperature varied between 150 and 450°C, the degradation temperature of samples shifted to a higher temperature with the lecithin concentration increased, which displays a further enhancement in the thermal stability. With the increase in surfactant concentration, a new endothermic peak appeared at ∼456 °C for 3.0CEC. This step could be ascribed to the presence of triglycerides and other impurity, which is consistent with the already published literature [START_REF] Ouellet-Plamondon | The effect of cationic, non-ionic and amphiphilic surfactants on the intercalation of bentonite[END_REF].

In order to have a deeper understanding of the physiochemical processes of organic matter and clay minerals at the microscopic level, classical molecular dynamic (MD) simulations have been proven to be an effective method to obtain structural information among the constituents [START_REF] Kovar | Mg-Al layered double hydroxide intercalated with porphyrin anions: molecular simulations and experiments[END_REF]. We have modelled the system at pH=1.0, 60°C and when a PC concentration regarding the CEC of 2.0 was added. The calculation details are available in supplementary information(SI).

Five molecular dynamics simulations (MD) of 10 ns were performed on a small slab of montmorillonite, composed of 9×9×2 (x,y,z) unit cells. At first all PC molecules are added directly inside the interlayer space of the clay randomly, the exact number is related to the experimental loading amount measured. From these dynamics results, we can draw some conclusions (Fig. 9). First we will discuss about the PC absorption. We have observed that the PC auto-organized themselves quickly, even before the MD production. The amine head points in the direction of the T layer of the montmorillonite. However, it is often not directly in interaction with this one, but in most cases, involved in a hydrogen bond network with a water molecule in between the clay structure and the PC. The second type of interaction comes from the OH group of the phosphate which is protonated at pH=1.0.

It is either directly bonded to the oxygen atom of the T sheet of the Mt or through a water molecule. In Table 2, we have printed the percentage of nitrogen (from the amine group) or O (from the OH group of the phosphate) in interaction with the surface i.e. below 0.68 nm. This distance corresponds to the sum of the Van der Waals radius of either the amine group, a water molecule and an oxygen of the silicate or the OH group of the phosphate, a water molecule and an oxygen of the silicate. For all MDs more than 90% of the lecithin molecules are in interaction with the surface.

However some of them do not interact at all and instead in interaction with other PC.

Finally, once the PC is in interaction with the montmorillonite, no major displacements are observed during the MD. This tends to validate the experimental observations where the PC is strongly absorbed in the interlayer space at 60°C.

Let's now focus in the orientation of the PC tails in the interlayer space. The PC molecule optimized in vacuo using DFT calculations has a length of 3 nm (from a carbon of the amine group to the last carbon of the tail). In comparison to the maximum interlayer space measured (4.56 nm when removing the TOT distance), 2 PC molecules cannot fit inside the interlayer space without some bending. In the Fig. S5, we have represented several possible organizations of the PC molecules. They can adopt a lot of different conformation, some are nearly linear while others are heavily bended. On top of this, several PC (green, orange in Fig. S5) interact with the surface with both amine and phosphate groups but also with the oxygen atoms of the linear chains. In the end, the disposition of PC molecules is relatively random, maybe due to the short time of the simulation.

Finally we also analyzed the distance of the interlayer space during the MD. As written before the PC tends to self-organized very quickly, and after 4 ns the stable regime is observed regarding the total energy of the system. For each MD, the relative distance of the interlayer space is reported in Table 2 and taken from the last step of the simulation. It is difficult to give a precise number as the TOT layers of the montmorillonite are slightly altered by the MD due to not being constrained. In any case, for the 5 MDs the computed d 001 distance reproduced accurately the measured one with a maximum deviation of 6 %. One of the reasons could be that we have added too many PC molecules in the interlayer space. As written before 5 to 10 % of PC molecules are not in interaction with the clay, and instead are freely moving in the interlayer space, disrupting the local order.

Conclusions

In this study, a series of organo-bentonites were synthesized by using natural Regarding the effect of the pH , the d 001 of the bentonite layer was significant higher for the samples prepared at pH≥3.0 due to the properties change of both the surface and the lecithin. For example, when the pH shifts from 1.0 to 3.0, the interlayer spacing of organoclay was increased from 1.43 to 5.19 nm, which is of great significance for the preparation of low-cost organobentonite for industrial applications.

These results demonstrate that the modified bentonite with lecithin have quite different structural properties, and they may have special applications in the industrial fields.

Fig. 1 .Fig. 2 .

 12 Fig. 1. The molecular structure and functional groups of phosphatidylcholine (PC)

Fig. 3 .

 3 Fig. 3. Top: XRD patterns (a) and FTIR spectra (b) of bentonite, lecithin and modified bentonite at

Fig. 4 .

 4 Fig. 4. Top: XRD patterns (a) and FTIR spectra (b) of bentonite, lecithin and modified bentonite

Fig. 5 .

 5 Fig. 5. Top: XRD patterns (a) and FTIR spectra (b) of bentonite, lecithin and modified bentonite at

Fig. 6 .

 6 Fig. 6. Top: XRD patterns (a) and FTIR spectra (b) of bentonite, lecithin and modified bentonite at

Fig. 7 .

 7 Fig. 7. Schematic diagram of the lecithin arrangement in the interlayer space at different

For a better understanding

  of the morphology of organoclays, TEM micrographs of raw bentonite and the obtained organoclays are presented in Fig.8. The micrograph of raw bentonite (left picture) suggested that the untreated bentonite is mainly composed of a layered structure with a d (001) measured = 1.2 nm, in good agreement with the value obtained by XRD analysis. The second micrograph of organoclay modified with 1.0CEC lecithin (middle picture) clearly displayed an increase in the interlayer spacing compared to raw bentonite. Finally, for organic bentonite modified with 2.0CEC lecithin (right picture), multiple interlayer spacings are observed at 5.8, 1.7, and 1.4 nm, slightly smaller than the XRD measured d 001 -value of 5.96 nm.Indeed, XRD results corresponds to an average value while TEM measurements are based on individual layers.

Fig. 8 .

 8 Fig. 8. TEM micrographs of raw bentonite and organoclays modified with lecithin at different

Fig. 9 .

 9 Fig. 9. Snapshot of the last step of the MD3. The N and PO 4 group of the PC molecules are

  soybean lecithin at different experimental conditions. The effects of reaction temperature, time, pH, and lecithin concentration on the properties of modified bentonite were analyzed. The results of FTIR, XRD, TG and molecular dynamic simulations support the intercalation of lecithin in the interlayer space of montmorillonite. The characterization results demonstrate that the intercalation behavior of lecithin can be completed in a short time (0.5h). Lecithin concentration and pH greatly influence the structural characteristic of modified bentonite. In general, the basal spacing of the organo-bentonite has a positive correlation with lecithin concentration and pH. In the case of pH=1.0, the interlayer spacing of modified bentonite increases with the lecithin concentration and the surfactants exhibit different arrangements among the bentonite layers. Lecithin adopts a lateral monolayer arrangement at low concentrations (0.1~1.0CEC) in contrary to a lipid bilayer at high concentrations (2.0~3.0CEC), this last one being perpendicular to the surface.

  TableS2listed the percentages of mass loss of the different stages and loaded amount of lecithin. The maximum mass loss of lecithin, determined from TG curves, was completed at 0.5h

						(d)	238			6.0h
								335	586
	100	(c)				241			4.0h
								331	589
	Weight (%)	40 60 80	Ⅰ	Ⅱ bentonite lecithin 0.5h	Ⅲ	Deriv. Weight (%/℃ )	240 234	317 302	590 588	2.0h 3.0h
		20		1.0h 2.0h				321		1.0h
				3.0h			241
				4.0h					590
		0	200	6.0h	400 Temperature (℃ ) 600	800	242	321	591	0.5h
							200	400	600	800
								Temperature (℃ )

Table 1 .

 1 Chemical composition of raw bentonite and organic bentonite measured by XRF.

	lecithin		chemical composition (mass%)
	concentration
	/CEC	Na 2 O MgO CaO K 2 O Al 2 O 3	SiO 2 Fe 2 O 3 P 2 O 5	other
	0 (raw bentonite) 2.56	2.84 1.23 0.32	22.9	65.1	4.22	0.06	0.77
	0.5	0.31	2.32 0.42 0.30	23.1	64.9	4.74	3.59	0.24
	1.0	0.21	2.51 0.29 0.24	22.7	63.6	4.04	6.17	0.26
	2.0	0.15	2.30 0.32 0.24	21.3	60.1	3.97	11.4	0.24

Table 2 .

 2 Computed d 001 at the last step of the related MD and percentage of N (from amine) or OH (from phosphate) of the PC molecules in interaction with the surface at a distance of 0.68 nm.

	MD number	1	2	3	4	5
	Computed d 001 (in nm)	6.214	6.14	6.029	6.02	6.33
	%N (amine) in interaction with the surface	94%	91%	91%	92%	92%
	%OH (phosphate) in interaction with the surface 69%	63%	66%	62%	66%

9 2 4 c m -1 2 8 5

c m -1 1 7 3 5 c m -1 1 7 0 8 c m -1 1

6

c m -1 (b)

Acknowledgments

Qiang Li is grateful for the scholarship (No. 202006440010) awarded by the China Scholarship Council (CSC).


S Le Roy

V Griseri

G Teyssèdre

C Laurent

Simulation of Charge Build Up and Transport in Electron Beam Irradiated Organic Dielectrics: Comparison to Space Charge Measurements

Recently, the Pulsed Electro Acoustic method -PEAhas been adapted to perform space charge measurements in organic dielectrics under electron beam irradiation and during relaxation, considering short-circuit and open-circuit conditions for the insulation. On the other hand, a model has been developed in order to understand the behavior of space charge in spatial conditions. The aim of this paper is to present the numerical model, and to compare simulated results with experimental ones, obtained with the short-circuit PEA and the open PEA, for a PolyTetraFluoroEthylene (PTFE).

I. INTRODUCTION

Polymeric materials are commonly used in the spacecraft industry as cover parts of satellites. Owing to their insulating properties, such materials store electrical charges generated by the specific space environment conditions. These charges can lead to electrostatic discharges able to affect the spacecraft operation. In order to understand how dielectrics get charged and to prevent violent discharges, the spatial environment conditions are reproduced at lab-scale [START_REF] Dirassen | The SIRENE facility -An improvement method for simulating the charge of dielectrics in a charging electron environment[END_REF], and PEA set-ups have been implemented to measure the space charge implantation in these irradiation chambers [START_REF] Griseri | Space-Charge Detection and Behavior Analysis in Electron Irradiated Polymers[END_REF]. To complete these studies, models have been adapted to reproduce the space charge behavior of dielectrics during irradiation or for the following relaxation. In the following, we present the experimental results obtained with two PEA configurations on a PolyTetraFluoroEthylene (PTFE) during irradiation and relaxation, and compare the results with simulated ones for each configuration. We discuss model abilities and limits.

II. EXPERIMENTS

A. Experimental conditions

PTFE films of 500 µm thickness have been selected for this work. In order to introduce electrons in the bulk of the insulation, the electron beam energy has been fixed at 250 keV which leads to a maximum penetration depth of the order of 370µm The irradiation was performed for 30 min with a flux of 50 pA/cm 2 . Two PEA setups working either with floating potential or under short-circuit conditions have been installed in the chamber and measurements were recorded at the same time under exactly the same irradiation conditions. One face of the sample was metallized and stick to the ground electrode. The upper face was metallized only for short-circuit measurements. In the open PEA configuration, space charge distribution is probed using a metallic electrode positioned 1 mm above the free surface. This probing electrode is moved away during the irradiation (which is stopped for the time of measurement of 1 min).

B. Results for open-circuit configuration

As soon as the irradiation starts, a peak of negative charges appears in the bulk and it is centered at around 300 µm (Fig. 1a). A positive peak of induced charges is built up simultaneously at the ground electrode (the irradiated surface is free -without metallization). The peak amplitude grows continuously with the irradiation time. There is no evidence of charge saturation after 30 min. The relaxation was followed during 7 days under vacuum (Fig. 1b). A slow movement of the negative peak towards the back electrode is observed. The amplitude of the image charge does not change with time. It means that implanted charges move under the influence of their own electric field but none of them managed to be extracted on such time scale.

C. Results for short-circuit configuration

In short-circuit conditions, two negative charge peaks are detected in the bulk when the irradiation is initiated (Fig. 2). The first one is in the bulk at about 305 µm from the surface and the second one is near the irradiated surface at about 40 µm. At both sample/electrode interfaces, two positive peaks of induced charges are built up simultaneously (both sides of the sample are metallized). If we compare the amplitude of the signal recorded by both methods, we can see that there is a large difference. Actually the amplitude of the charge density detected with the shortcircuit set-up is much smaller than the one recorded with the open PEA equipment. This can be explained by the fact that a large amount of the charges located in the irradiation part can be extracted from the front grounded electrode during the irradiation and also during the measuring period. Electrons implanted in the bulk are driven towards the irradiated surface under the effect of the electric field created by the charges themselves. The same phenomenon could be observed in the non-irradiated part as the field tends to drive the charges in the opposite direction (towards the back electrode). However, the irradiated zone is actually more electrically conductive due to the irradiation (so-called RIC; radiation-induced conductivity). Hence, charges are evacuated essentially through the irradiated region.

III. SIMULATIONS A. Model description

A numerical model developed for the transport of charges in solid dielectrics under electrical stress [3], has been adapted to reproduce the behavior of charges in electron beam irradiated polymers, for the two configurations encountered in the experiments, i.e. 'open circuit' and 'short-circuit' (Fig. 3). The model features injection of carriers at one or two electrodes, conduction via a constant effective mobility, trapping and detrapping of each carriers into deep traps, and recombination as represented in Fig. 4. The physical hypotheses for the generation of electronic carriers due to the electron beam, i.e. generation of electron/hole pairs, have been taken from Sessler et al [4]. I.

The model used to describe the charge transport involves the coupled resolution of the following equations, neglecting the diffusion:

 j(x, t)  .n.E(x, t) transport (1)  E(x,t) x  (x,t) . 0 Poisson (2)  n(x,t) t  j(x,t) x  s(x,t) continuity ( 3
)
where x is the distance in the direction perpendicular to the electrodes, t is the time,  is the carrier mobility, n is the carrier density, E is the electric field,  is the net charge density,  is the relative permittivity (2.1 for PTFE), j is the current density. The term s(x,t) is the source term, i.e. it encompasses changes in local density by processes other than transport (electron deposition, electron/hole pairs generation, trapping, etc.). The following equations describe the source term of equation ( 3) for each kind of carriers:

                       h e 3
                   h e 3 et h 2 ht h ht 0 h ht h h h n . n . S n . n . S n . D n n 1 ) t , x ( n . B ) x ( G ) t , x ( s (6)                h ht 1 ht et 0 ht h ht 0 h ht h h ht n . n . S n . n . S n . D n n 1 ) t , x ( n . B ) t , x ( s (7)
where the indexes e and h refer to electrons and holes respectively. The parameters definitions are given in Table I. De and Dh are the detrapping coefficients, of the form:

 D e   exp w tre k B T       ( 8
)
where kB is the Boltzmann constant and  the attempt to escape frequency. G(x) in equations ( 4) and ( 6) refers to the electron/hole pair generation, of the form [4]:

 G(x)  G 0 .D(x) (9
) where G0 is the electron/hole pairs generation coefficient, and D(x) is the deposited dose, function of the energy of the electron beam, the nature of the material. J0 in equation ( 4) refers to the beam current density, function of the position in the dielectric. The corresponding profile along with the deposited dose profile have been calculated using the GEANT 4 software [5], and are given in Fig. 5a) and b) respectively, for the current experimental conditions. Beside charging by incident electrons and related effects, we have considered the possibility that charges be generated by injection at the electrodes. This has been accounted for by considering a modified-Schottky law of the form: The same equation holds at x=0 for the short circuit configuration. A is the Richardson constant and wa is the injection barrier (cf. Table I). The nature of injected carriers depends on the sign of the field at the electrode.

Simulations results presented in the following have been obtained with the optimized parameters given in Table I. It is to note that the adaptation of the parameters in order to best fit the experiments has been done manually, meaning a long lasting work. The irradiation conditions and the material features are those described in section II.

B. Results for open-circuit configuration

In the case of open circuit configuration (Fig. 3a), charges can only be injected and extracted at the right electrode (ground), the sign of the injected carriers being dependent upon the electric field. The irradiation comes from the left side (x=0). A post-treatment of the simulated results enables us to add the image charge induced by the internal charge inside the dielectric on the electrodes and to smooth the profiles in an equivalent way as the PEA method does. In this configuration, image charges can only be seen at the ground electrode. The model parameters are given in Table I, except for the recombination coefficient S0 which has been set to zero in order to obtain a better comparison between the experiment and the simulation profiles.

B.1 Irradiation: Simulated results obtained for the optimized parameters are given in Fig. 6.a for the irradiation. A negative charge peak appears quickly inside the bulk and increases with the irradiation time. The peak maximum is detected at 280 m after 30 min of irradiation. No charges are observed next to the irradiation face (left electrode), and beyond 400 m. The simulated profiles are consistent with the experimental ones (Fig. 1.a), as the model only takes into account monoenergetic electrons. During irradiation, positive charges are produced (due to the electron/hole generation process). However they do not appear as net charge since they are compensated by negative carriers produced by the generation process and by deposition of charges from the incident beam. The net charge is effectively null from x=0 to 200 m. 7 days of relaxation, the simulated results show a small quantity of positive charges close to the ground electrode. These charges have been injected from the ground electrode under the effect of the implanted charge-induced field.

C. Results for short-circuit configuration

The simulated charge profiles obtained with the optimized parameters of Table I are given in Fig. 7 for irradiation in the short-circuit configuration as shown in Fig. 3.b. In this case, charges can be injected and extracted at both electrodes. As previously, the image charges on both electrodes have been added.

Two negative charge peaks are observed during irradiation. The first peak is detected at ~40 m from the irradiation face. It increases with the irradiation time and shifts towards the left electrode. The second peak is observed at 250 m at the beginning of the irradiation. It also increases with irradiation time and shifts towards the right electrode (from 250 to 290 m). Between these peaks, the net charge is nearly zero. The negative charges, deposited by the electron beam or generated by electron/hole pair, are drifted by the implanted charges-induced field (Fig. 8) towards the irradiated surface or the back electrode, depending on their position inside the bulk. As to positive charges, the field tends to stabilize them between 100 and 250 m, giving rise to a quasi-zero net charge density.

Simulated results are in good agreement with experimental ones for the 'short-circuit PEA' configuration (Fig. 2). The model is able to reproduce the dynamic of space charge for this case and many features related to the charge profiles, particularly the appearance of a double peak. Only the density of charge seems overestimated in the simulation. However, the optimization of the parameters has been done mainly qualitatively, not quantitatively.

CONCLUSION

A numerical model has been implemented in order to reproduce original space charge measurements in space environment. The comparison between the experiment and the simulation leads to a good agreement for both configurations, i.e. the open PEA and the short-circuit PEA configurations. This is however a preliminary work, and more studies need to be done in order to further develop the model for different polymeric materials encountered on satellites, and to understand the impact of the recombination on simulated space charge profiles.

Fig. 1 :

 1 Fig. 1: Charge profile recorded with the open PEA set-up on a 500 m thick PTFE a) during 30 min irradiation under 250 keV, with a flux of 50 pA.cm -2 , and b) during 7 days relaxation under vacuum.

Fig. 2 :

 2 Fig. 2: Charge profile recorded with the short-circuit PEA set-up on a 500 m thick PTFE during 30 min irradiation under 250 keV, and 50 pA.cm -2 as flux.

3 :Fig. 4 :

 34 Fig. 4: Schematic representation of the conduction mechanism in a PTFE sample. The values and definition of the parameters are given in TableI.

Fig. 5 :

 5 Fig. 5: a) Normalized current density and b) Normalized dose function of the thickness of the sample calculated by GEANT 4 for a 500 m thick PTFE irradiated by a 250 keV electron beam, 50 pA.cm -2 .

B. 2 Fig. 6 :

 26 Fig. 6: Simulated space charge profiles for a 500 m thick PTFE in opencircuit configuration a) during 30 min of irradiation with a 250 keV electron beam and b) for the following relaxation during 7 days.

Fig. 7 :Fig. 8 :

 78 Fig.7: Simulated space charge profiles for a 500 m thick PTFE in shortcircuit configuration during 30 min irradiation with a 250 keV electron beam.

Table I :

 I Final optimized parameters used for all simulations

	Parameter	Value	Units
	Mobilities
	µe electrons	3.10 -14	m 2 .V -1 .s -1
	µh holes	8.10 -16	m 2 .V -1 .s -1
	Trapping coefficients
	Be electrons	10 -1	s -1
	Bh holes	10 -2	s -1
	Trap densities
	ne0et electrons	100	C.m -3
	nh0ht holes	100	C.m -3
	Recombination coefficients
	S0 trapped electron/trapped hole	4.10 -3	m 3 .C -1 .s -1
	S1 mobile electron/trapped hole	0	m 3 .C -1 .s -1
	S2 trapped electron/mobile hole	0	m 3 .C -1 .s -1
	S3 mobile electron/mobile hole	0	m 3 .C -1 .s -1
	Injection barrier heights
	we electrons	1.15	eV
	wh holes	1.35	eV
	Detrapping barrier heights
	wtre electrons	1.17	eV
	wtrh holes	1.05	eV
	Electron/hole pair generation
	coefficient
	G0	2.10 -1	C.m -3 .s -1

ACKNOWLEDGMENT

Authors would like to acknowledge the ONERA-DESP department and the CNES.


G Teyssedre

C Laurent

Evidence of hot electron-induced chemical degradation in electroluminescence spectra of insulating polymers

Unlike semi-conducting organics, insulating polymers exhibit electroluminescence features that cannot be interpreted on the basis of the photo physical properties of the material. In particular, it is shown that the spectral components observed in electroluminescence in three different classes of insulating polymers -polyolefin, polyester and epoxy, can only be reproduced when the material is irradiated by an electron beam. This shows that hot electron impact is a driving process in electroluminescence and that the excited states decay route goes along the chemical pathway ending with molecular fragmentation. The results allow to associate electroluminescence and electrical degradation in an implicit scheme, opening the way for defining safety limits in terms of electric stresses applied to a material for a given application.

INTRODUCTION

Search for pre-breakdown warning signs in insulating polymers has been the subject of a great deal of work in the last few decades. This is so because engineering insulating materials needs the knowledge of safety limits in terms of applied electric stresses all the more that polymers are known to be sensitive to electrical ageing that decreases their ability to sustain an electric field in time [START_REF] Dissado | Electrical Degradation in Polymers[END_REF]. Pre-breakdown warnings may differ depending on the situation. Electric and acoustic signals emitted in the presence of discharging internal cavities or during electrical treeing propagation have been used for long to diagnose defects and to monitor ageing. However, these mechanisms only appear in the presence of local field enhancement or micro voids. Otherwise, material degradation is thought to be due to trapped [START_REF] Mazzanti | Electrical aging and life models: the role of space charge[END_REF] or mobile [START_REF] Sanche | Nanoscopic aspects of electronic aging in dielectrics[END_REF] space charge and efforts have been done to define electrical field threshold for ageing based on space charge measurements. Electroluminescence (EL) seems to be appropriate to tackle the problem because degradation involves energy dissipation in the chemical bonds energy range (a few eV) that corresponds to the optical spectrum. Spectral analysis should give indication on the nature of the transition process, i.e. on dissociative vs. non dissociative excited states relaxation defining chemical vs. physical decay routes. In organic semi-conductors, electrical and optical stimulations lead to identical emission spectra [START_REF] Bradley | Electroluminescence: a bright future for conjugated polymers?[END_REF] indicating that both phenomena originate from the relaxation of the same excited states and that the process is physical in nature, i.e. there is no chemistry involved in light emission. This gave the basis for the development of the organic light emitting devices. A similar approach on large band gap polymers such as polyethylenes and polyesters showed that electrical and optical stimulations lead to quite different emission spectra [START_REF] Laurent | Hot electron and partial discharge induced ageing of polymers[END_REF]. Emission spectra in chemiluminescence (promoted upon sample oxidation in O2 atmosphere - [START_REF] Tiemblo | Chemiluminescence spectral evolution along the thermal oxidation of isotactic polypropylene[END_REF]) and recombination-induced luminescence (where light is due to the recombination of electric charges trapped at the surface of specimen - [START_REF] Teyssedre | Spectral analysis of optical emission due to isothermal charge recombination in polyolefins[END_REF]) have also been investigated. Although some of the features of the EL spectra can be reproduced using these alternative excitation sources, none of the spectra matched those obtained under electric field. It is shown here that the spectra obtained when polyethylene, polyethylene naphthalate and epoxy resin are submitted to an electron beam irradiation (cathodoluminescence -CL) match perfectly those obtained in EL.

EXPERIMENTAL Experimental set-up

Material -Samples Measurements were performed on 25 µm-thick Polyethylene Naphthalate (PEN) films, on 100 µm thick films of Low Density Polyethylene -LDPE-, on 150 µm cross-linked polyethylene -XLPE-slices from HVAC cables and on 1 mm-thick epoxy samples. Samples were metallized only for EL measurements (30 nm thick gold electrodes unless otherwise specified). The difference in sample thickness is not important for cathodoluminescence -CL-measurements as the energy of electrons used provide penetration in a very limited depth (order of 1µm).

Experiment environment The experimental set-up used for light detection has been extensively described elsewhere [START_REF] Mary | Understanding optical emissions from electrically stressed insulating polymers: electroluminescence in poly(ethylene terephthalate) ,and poly(ethylene 2, 6-naphthalate) films[END_REF]. It is currently used for carrying out electro-, photo-, recombination-induced luminescence, or even luminescence during thermal oxidation or curing of materials, providing both integral light detection by means of a photomultiplier working in photon counting mode, and spectral resolution of the emitted light through a Charge-Coupled Device -CCD-coupled to a grating monochromator. The new feature here is the introduction, in the same experimental arrangement, of an electron gun providing electrons of energy of up to 10 keV. The electron gun has been home-designed; a schema of it is shown in Figure 1. Electron emission is made using a tungsten filament, the flux being dependent on the current (of the order of 1 A) flowing in the filament. As can be seen in Figure 1, the filament itself is at high voltage and the anode is to the ground. In that way, it is expected that the electrons energy does not change to a great extent after their exit from the gun. The distance between the electron gun and the sample is about 40 mm. The axis of the electron gun is at about 50° to the normal of the sample plane. The arrangement is so for rendering possible light detection along the normal of the samples. All the experiments have been carried out under a vacuum of 5.10 -6 mb, at room temperature. Except when otherwise mentioned, the electron current was about 0.5 µA in the experiments reported therein. The size of the spot is not precisely known (a few mm²). We have verified that the current is perfectly independent from the energy of the electrons for accelerating voltages in the range 1 to 10 kV, and so whatever the electron current.

The main difficulty encountered in these measurements was the incandescence of the filament with an emission in the wavelength range over 500 nm, depending of the current of the filament, cf. Figure 2. As this emission is independent from the accelerating voltage, the baseline corresponding to the incandescence spectrum was recorded with low acceleration voltage (500 V or so) in which case the beam current is small and the light detected is constituted only of incandescence. This baseline is subtracted for correcting spectra. Note that the relative contribution of incandescence to spectra strongly diminishes when the beam current increases. [START_REF] Teyssedre | Temperature Dependence of the Photoluminescence in Poly(ethylene terephthalate) Films[END_REF]. Under field or electron-beam irradiation, new components associated with by-products dominate the emission in the phosphorescence region at 620 and 680 nm. When the beam is maintained constant for the same energy, the fluorescence contribution decreases significantly in time, shifts to the red and becomes broad. This evolution is also seen with time under stress in EL spectra. The 3 peaks observed in the phosphorescence region apparently do not evolve much, in respect to the others vs. energy beam or time. The EL and CL spectra are in quite good agreement if one has in mind that in both cases, the shape changes with excitation conditions and with time. We are very probably in conditions of heavy degradation in the two instances.

Polyethylene: Several bands are observed in the XLPE and LDPE spectra and they appear correlated to identified features. The 410 nm/420 nm shoulder is associated with an emission involved in chemiluminescence of polyolefins [START_REF] Tiemblo | Chemiluminescence spectral evolution along the thermal oxidation of isotactic polypropylene[END_REF][START_REF] Teyssedre | Spectral analysis of optical emission due to isothermal charge recombination in polyolefins[END_REF]. Short oxidation times yield spectra which are relatively narrow and peak at about 410 nm, while the spectra of the chemiluminescence emitted after a long oxidation time are broader and shifted to longer wavelengths. The 410 nm component is presumably reflecting the formation of isolated carbonyl groups. The 500 nm/510 nm shoulder has been revealed in charge recombination process [START_REF] Teyssedre | Spectral analysis of optical emission due to isothermal charge recombination in polyolefins[END_REF] and is associated with recombination occurring on poly-enone sequences. These chemicals provide adequate recombination centres (as revealed by molecular modelling) and they emit in the long wavelength range of the optical spectrum because enone compounds have low lying triplet states. The 570 nm peak seems only obtained in CL and EL, pointing out to a common origin which could be a specific degradation path involved in hot electron processes. Note that the emitting species are due to the molecular network itself since LDPE and XLPE emission spectra are similar. Additives and/or anti-oxidant cannot be involved as they were not part of the formulation of the tested LDPE material.

Epoxy resin: Again, CL and EL spectra are very similar. In CL, there is a dependency of the spectral shape on the energy beam with an increased ratio between the 450 nm/550 nm components with an increasing energy. In EL, only the main peak at 550 nm is clearly visible (although the shoulder at 450 nm can be distinguished) due to the low signal/noise ratio. Note that the epoxy is weakly emitting in EL when excited under similar conditions when compared to PEN or PE. Spectral acquisition is therefore a difficult task, all the more than the spectrum of Figure 6 was acquired at low field (12kV/mm). Indium-Tin-Oxide electrodes were used in order to avoid the emission in the red due to the radiative decay of surface plasmons excited at the metallic electrodes (see [START_REF] Teyssedre | Identification of the components of the electroluminescence spectrum of PE excited in uniform field[END_REF][START_REF] Aubert | Monitoring electrically-active defects in silica-filled epoxy using light detection[END_REF]). The photoluminescence features of the epoxy have been thoroughly studied by considering the PL of the base resin and hardener taken separately, of their mixture, and in the course of curing [START_REF] Gallot-Lavallée | Identification of photoluminescence features of an epoxy resin based on components features and curing effects[END_REF]. Most of the bands observed in the cured resin could be interpreted based on those found in the components taken separately. Some of the phosphorescence bands revealed in PL experiments are in the range of the EL and CL spectra reported in this study (up to 500 nm) but none are able to map the max of emission at 560 nm. However, when monitoring the spontaneous emission of the resin during curing (chemiluminescence path), we got a spectral shape with a maximum at 562 nm, very similar to CL and EL spectra. This chemiluminescence has been attributed to oxidation reactions of the hardener occurring during or after the curing [START_REF] Gallot-Lavallee | Curing and post-curing luminescence in an epoxy resin[END_REF]. kV/mm, using ITO electrodes (thereby avoiding surface plasmon radiation in the visible -see [START_REF] Aubert | Monitoring electrically-active defects in silica-filled epoxy using light detection[END_REF])

DISCUSSION

The similarity between EL and CL spectra in the three different classes of insulating polymers leads to the conclusion that EL involves material degradation. The signatures of charge recombination and chemiluminescence seen in the EL spectra of polyethylenes support the existence of these mechanisms under electrical stress. They can be a direct consequence of hot electron impact with the creation of reactive species (which could further react with oxygen molecules dissolved in the amorphous fraction of the polymer) and the generation of secondary electrons (which would then be trapped and available to recombine with trapped holes at low to moderate field without need to get an electronic avalanche). The extra spectral features revealed in CL, and that allow to fully understand the EL spectrum, are likely linked with a specific pathway bound to electronic impact.

The use of a 10 keV electron beam energy could appear too far from the energy of hot electrons in polymers (< 10 eV) to be typical. However, one has to keep in mind that interaction between electron beam and matter leads first to a decrease of energy of the individual electrons by X-ray emission (Bremsstrahlung) before they efficiently start their interaction with valence electrons and localized centres in the gap. It follows a set of possible excitation mechanisms among which impact ionization at moderate kinetic energy (order of 15 eV), impact excitation (10 eV), quasielastic scattering with phonons (energy < 10 eV), and finally electron trapping at thermal energy [START_REF] Sanche | Nanoscopic aspects of electronic aging in dielectrics[END_REF]. All these events are those that are thought to be important under electric field. The above results allow to associate electroluminescence and electrical ageing in an implicit scheme, opening the way for defining safety limits in terms of electric stresses applied to a material for a given application. New routes are also opened for understanding the nature of the reactive species and to develop improved formulation of polymer materials for high field application.

CONCLUSION

By irradiating various materials with energetic electrons, we were able to reproduce their EL spectrum. It gives definitive evidence that EL under uniform field can be analyzed in terms of material properties. These results allow to associate electroluminescence and electrical ageing in an implicit scheme, opening the way for defining safety limits in terms of electric stresses applied to a material for a given application. New routes are also opened for understanding the nature of the reactive species and to develop improved formulation of polymer materials for high field application.

Figure 1 :

 1 Figure 1: Schema of the core of the electron gun. The diameter of the hole of the anode is 1mm.RESULTS

Figure 2 :

 2 Figure 2: Incandescence spectrum (solid line) and apparition of the CL contribution to the spectrum when increasing the beam energy. Material = PEN; beam current = 13 nA Polyethylene naphthalate: Analysis of the photo-physical properties of PEN shows a fluorescence peaking at 430 nm and a weak phosphorescence contribution at 585/630 nm[START_REF] Teyssedre | Temperature Dependence of the Photoluminescence in Poly(ethylene terephthalate) Films[END_REF]. Under field or electron-beam irradiation, new components associated with by-products dominate the emission in the phosphorescence region at 620 and 680 nm. When the beam is maintained constant for the same energy, the fluorescence contribution decreases significantly in time, shifts to the red and becomes broad. This evolution is also seen with time under stress in EL spectra. The 3 peaks observed in the phosphorescence region apparently do not evolve much, in respect to the others vs. energy beam or time. The EL and CL spectra are in quite good agreement if one has in mind that in both cases, the shape changes with excitation conditions and with time. We are very probably in conditions of heavy degradation in the two instances.

Figure 3 :

 3 Figure 3: Polyethylene naphthalate CL spectra (open symbols) under 10keV electron beam for 3 different irradiation times, EL spectrum (solid circles) under 250kV/mm DC stress and photoluminescence spectrum (solid line).

Figure 4 :

 4 Figure 4: Additive-free Low Density Polyethylene CL (open symbols) and EL (solid circles) spectra.Excitation energies range from 2 to 10 keV for CL. The EL spectrum was realized under 50Hz 45kV/mm r.m.s AC stress. It has been corrected for surface plasmons contribution[START_REF] Teyssedre | Identification of the components of the electroluminescence spectrum of PE excited in uniform field[END_REF].


Thomas Schiex

Helene Fargier

Gerard Verfaillie

Valued Constraint Satisfaction Problems: Hard and Easy Problems*

In order to deal with over-constrained Constraint Satisfaction Problems, various extensions of the CSP framework have been considered by taking into account costs, uncertainties, preferences, priorities...Each extension uses a specific mathematical operator (+, max...) to aggregate constraint violations.

In this paper, we consider a simple algebraic framework, related to Partial Constraint Satisfaction, which subsumes most of these proposals and use it to characterize existing proposals in terms of rationality and computational complexity. We exhibit simple relationships between these proposals, try to extend some traditional CSP algorithms and prove that some of these extensions may be computationally expensive.

Introduction and related works

The CSP framework provides a very convenient framework for representing and solving various problems related to AI and OR (scheduling, assignment, design...). When a real problem is casted in the CSP framework, different types of knowledge have to be dealt with:

• Hard constraints: physical properties (eg. spatial or temporal constraints), which have to be necessarily satisfied, are naturally represented as constraints; • Preferences: properties which should be satisfied "when possible" (due dates, user preferences, cost...) are either represented as constraints or simply ignored; • Uncertainties: properties that are relevant in some situations which cannot be predicted with certainty; such properties are then ignored, or represented as constraints. Thus, such soft constraints can be either ignored, which naturally leads to a poor mean quality of the solutions or represented as hard constraints which may yield an inconsistent CSP. A better solution is to take the violation of these constraints into account in a specific criterion that should be minimized.

Various proposals have been made in this direction, extending classical CSP in order to express "soft" constraints with 'This work has been partially funded by the French Centre National d' Etudes Spati al es and by the European Euclid project CALMA. a dedicated semantics in terms of priorities [START_REF] Schiex | [END_REF][START_REF] Borning | Constraint hierarchies and logic programmi ng[END_REF], preference degrees [START_REF] Rosenfeld | Scene labeling by relaxation operations[END_REF]Martin-Clouaire, 1992;Dubois et al., 1993;[START_REF] Ruttkay | Zsofia Ruttkay. Fuzzy constraint satisfaction[END_REF], costs [Shapiro and Haralick, 1981;Dechter etal., 1990;[START_REF] Freuder | [END_REF] or probabilities [START_REF] Rosenfeld | Scene labeling by relaxation operations[END_REF][START_REF] Fargier | [END_REF]. The specific nature of the criterion optimized allows dedicated branch and bound algorithms to be defined.

In these approaches, hard constraints and preferably satisfied/uncertain constraints are expressed as constraints but a valuation (usually a number) is associated to each constraint c, or each tuple t of a constraint. This valuation expresses the impact of violating the constraint c or using the tuple t on the quality of the solution. These valuations are combined using an operator that gives them a specific semantics. For example, in [START_REF] Schiex | [END_REF], the valuations of violated constraints are combined using a max operator, which gives the valuations an interpretation in terms of priorities, while in [Shapiro and Haralick, 1981], the valuations are numbers combined using addition, with an obvious interpretation as costs.

In this paper, rather than choosing a specific set for expressing valuations and a specific operator, we observe that an ordered commutative monoid (an ordered set with an operator satisfying some properties), is enough to encompass most existing CSP extensions. The valuations are taken from the set of the monoid, combined using its operator and compared using the order. For the sake of simplicity, we consider that valuations are only associated to constraints.

Our aim is then to use this abstract framework to provide general algorithms and properties, to bring to light relations between previous proposals and to identify where the difficult problems are, and what property makes them difficult 1 .

The next section defines the valued CSP (VCSP) framework, rapidly justifies the algebraic structure used and gives some simple properties. Section 3 describes previous proposals as VCSP and shows how they relate to each other in terms of rationality and complexity. Section 4 considers the generic extension of different Backtrack based algorithms and ends with preliminary experiments on the related observed complexities of some types of VCSP.

This work is therefore related to [Shafer, 1991] which consi ders an axiomatic framework where hyper-tree structured probl ems are sol ved efficiently and to [Minoux, 1976;Bistarelli etal, 1995] where a semi-ring is used to study the possi bl e generalization of shortest path and k-consi stency enforcing algorithms respectively.

SCHIEX, FARGIER, AND VERFAILLIE 631

bilistic VCSP, obtained in polynomial time and the problem of finding one optimal assignment for the Max-VCSP may be reduced to the problem of finding one optimal assignment of the corresponding Lex-VCSP. The partition between idempotent and strictly monotonic VCSP classes is also made clear at the level of polynomial classes: the existence of an assignment with a valuation lower than v in a strictly monotonic binary VCSP with domains of cardinality two is obviously NP-hard by restriction to MAX2SAT [Garey et al, 1976]. One of the few polynomial classes which seems to extend to all classes of VCSP is the class of CSP structured in hyper-tree (see [START_REF] Dechter Era | [END_REF]Shafer, 1991]).

4 Extending traditional algorithms 4.1 Local consistency In classical binary CSP (all constraints are supposed to involve two variables only), satisfiability defines an NP-complete problem, k-consistency properties and algorithms [Freuder, 1982] offer a range of polynomial time weaker properties: enforcing strong k-consistency in a consistent CSP will never lead to an empty CSP.

From the VCSP point of view, strong k-consistency enforcing defines a kind of lower bound of the CSP valuation: if strong k-consistency enforcing yields an empty CSP, then we know that the CSP valuation is greater than T and therefore equal to T, else it is simply greater than X, which is always true.

Arc-consistency (strong 2-consistency) is certainly the most prominent level of local consistency and has been extended to Max-VCSP years ago [START_REF] Rosenfeld | Scene labeling by relaxation operations[END_REF]. In Max-VCSP, are-consistency can be defined as follows:

Definition 10 A VCSP V is said to be arc-consistent iff (1) there exists, for each variable, a value that defines an assignment with a valuation strictly lower than T and ( 2

) any assignment A of one variable can be extended to an assignment A' on two variables with the same valuation (Vp(A) = V-p (A')).

Polynomial worst-case time algorithms that enforce this property on Max-CSP are defined in [START_REF] Rosenfeld | Scene labeling by relaxation operations[END_REF]Snow and Freuder, 1990;[START_REF] Schiex | [END_REF]. These algorithms yield an are-consistent Max-VCSP with the same valuation distribution on complete assignments, and a lower bound on the VCSP valuation can easily be derived from it.

Obviously, this definition could also be used in non idempotent VCSP. But it is useless if we can not define the corresponding arc-consistency enforcing algorithms that should compute, in polynomial time, a VCSP V which is both arc-consistent and in some sense "equivalent to the original VCSP V. The strongest level of equivalence one could achieve (stronger than our strong equivalence notion, def. 9) is the equality of the valuations in both VCSP for all complete assignments.

But the generalization of AC enforcing algorithms that consists in using min and ® respectively for projection and combination of constraints fails for non idempotent monotonic VCSP as it has been shown in a similar framework (see [Bistarelli et al., 1995], in these proceedings). The distribution of valuations may be modified and the algorithm may fail to terminate. However, it is still an open question whether more drastic modifications of the algorithms/properties, or a

634

CONSTRAINT SATISFACTION weakening of the "equivalence" notion (as def. 9) would allow us to recover something related to arc-consistency.

Tree search

Following the works from [Shapiro and Haralick, 1981;[START_REF] Schiex | [END_REF][START_REF] Freuder | [END_REF]Dubois era/., 1993], we try to extend some traditional CSP algorithms to the binary VCSP framework to solve the problem of finding a provenly optimal assignment. The class of algorithms which we are interested in are hybrid algorithms that combine backtrack tree-search with some level of local consistency enforcing at each node. These algorithms have been called look-ahead, prospective or prophylactic algorithms. Some possible instances have been considered in [Nadel, 1989]: Backtrack, Forward-Checking , Really Full Look Ahead. We consider here that such algorithms are described by the type of local consistency enforcing maintained at each node: checkbackward, check forward, arc-consistency or more... In prospective algorithms, an assignment is extended until either a complete assignment (a solution) is found, or the given local consistency property is not verified on the current assignment: backtrack occurs. The extension of such algorithms to the VCSP framework, where the problem is now an optimization problem, relies on a transformation of the Backtrack tree search schema to a Depth First Branch and Bound algorithm. DFBB is a simple depth first tree search algorithm, which, like Backtrack, extend an assignment until either (1) a complete assignment is reached: a new "better" solution is found or (2) a given lower bound on the valuation of the best assignment that can be found by extending the current assignment exceeds the valuation of the current best solution found: backtrack occurs. The lower bound used defines the algorithm. Our aim is to derive a lower bound from any given local consistency property.

In classical CSP, seen as A-VCSP, the actual local consistency property used gives the "lower bound": for example, in Really Full Look Ahead, the inexistence of an arc-consistent closure of the CSP guarantees that the valuation of any extension of the current assignment will be greater than T and therefore equal to T. However, as we pointed out earlier, no arc-consistency enforcing algorithm is available for strictly monotonic VCSP. We will therefore use classical local consistency notions plus the notion of relaxation of a VCSP (which defines classical CSP) to define our class of bounds: Property 1 Given a classical local consistency property L, a lower bound on the valuation of a given VCSP V is defined by the valuation of an optimal relaxation of P among those that satisfy the "local consistency" property L used (consistency of the current assignment, absence of domain wipe-out after check-forward or arc-consistency enforcing...). This valuation is a lower bound of the valuation of an optimal assignment since the valuation of an optimal assignment is also the valuation of an optimal consistent relaxation and all the relaxations where the "local consistency" property L is not verified are non consistent.

These lower bounds verify two interesting properties:

• they guarantee that the extended algorithm will behave as the original "classical" algorithm when applied to a classical CSP seen as a A-VCSP (a classical CSP seen as a A-VCSP has only one relaxation with a valuation lower than T: itself);

• a stronger local consistency property will define a better lower bound, leading to a tree search with less nodes but possibly more computation at each node.

Extending Backtrack

Backtrack uses the local inconsistency of the current partial assignment as the condition for backtracking. Therefore, the lower bound derived is the valuation of an optimal relaxation in which the current assignment is consistent. This is simply the relaxation which precisely rejects the constraints violated by the current assignment (these constraints have to be rejected or else local inconsistency will occur; rejecting these constraint suffices to restore the consistency of the current assignment in the relaxation). The lower bound is therefore simply defined by: and is obviously computable in polynomial time.

The lower bound can easily be computed incrementally when a new variable x i is assigned: the lower bound associated to the father of the current node is aggregated with the valuations of all the constraints violated by X i using ®..

The generic VCSP algorithm defined encompass all the "Branch and Bound" algorithms defined for Max-VCSP or E-VCSP in [START_REF] Schiex | [END_REF][START_REF] Freuder | [END_REF][START_REF] Fargier | Hel ene Fargier. Probl emes de satisfaction de contraintes flexibles et application a V ordonnancement de production[END_REF][START_REF] Ruttkay | Zsofia Ruttkay. Fuzzy constraint satisfaction[END_REF]. Note that for Max-VCSP, thanks to idempotency, it is useless to test whether constraints whose valuation is lower than the lower bound associated to the father node have to be rejected since their rejection cannot influence the bound.

Extending Forward Checking

Forward-checking uses an extremely limited form of arcconsistency: backtracking occurs as soon as all the possible extensions of the current assignment A on any uninstantiated variable are locally inconsistent: the assignment is said non forward-checkable. Therefore, the lower bound used is the minimum valuation among the valuations of all the relaxations that makes the current assignment forward-checkable.

A relaxation in which A is forward-checkable (1) should necessarily reject all the constraints violated by A itself and (2) for each uninstantiated variable X i it should reject one of the sets C(x i , v) of constraints that are violated if X i is instantiated with value v of its domain. Since ® is monotonic, the minimum valuation is reached by taking into account,for each variable, the valuation of the set C(x i , v) of minimum valuation. The bound is again computable in polynomial time since it is the aggregation of (1) the valuations all the constraints violated by A itself (i.e., the bound used in the extension of the backtrack algorithm, see 4.3) and ( 2) the valuations of the constraint in all the C( xi , v). This computation needs less than (e.n.d) constraint checks and ® operations (e is the number of constraints); all the minimum valuation can be computed with less than (d.n) comparisons and aggregated with less than n ® operations. Note that the lower bound derived includes the bound used in the backtrack extension plus an extra component and will always be better than the "Backtrack" bound.

The lower bound may be incrementally computed by maintaining during tree search, and for each value v of every unassigned variable x i the aggregated valuation B(v, x i ) of all the SCHIEX, FARGIER, AND VERFAILLIE constraints that will be violated if v is assigned to X i given the current assignment. Initially, all B(y, X i ) are equal to 1. When the assignment A is extended to A' -A u {X J = u}, the B may be updated as follows:

) that takes into account all the constraints between x i and X j that are necessarily violated if, is assigned to x j . Upon backtrack, the B have to be restored to their previous values, as domains in classical Forward-checking. Note that the B offer a default value heuristic: choose the value with a minimum B.

The lower bound is simply obtained by aggregating, using ®, the valuations of all the constraints violated by the assignment and all the minimum B(v, X i ) for each unassigned variable. The aggregated valuation v(A'), A! -A U {XJ = u}), of all the constraints violated by the assignment A! is easily computed by taking the valuation v(A) computed on the father node ®'ed with B(u, Xj).

Additional sophistications include deleting values v of the domains of non instantiated variables if the aggregated valuation of v(A') and B(v,X i ) exceeds the upper bound (see [START_REF] Freuder | [END_REF]). The generic VCSP algorithm defined encompass the forward-checking based algorithm for Max-VCSP described in [START_REF] Schiex | [END_REF] or the Partial Forward-checking algorithm defined for _ VCSP in [START_REF] Freuder | [END_REF]. Note that for Max-VCSP, and thanks to idempotency, the updating of B can ignore constraints whose valuation is less than the B updated or than the current lower-bound.

Trying to extend Really Full Look Ahead

Really Full Look Ahead maintains arc consistency during tree search and backtracks as soon as the current assignment induces a domain wipe-out: the CSP has no arc-consistent closure. For a VCSP, the bound which can be derived from are-consistency will be the minimum valuation among the valuations of all the relaxations such that the current assignment does not induces a domain wipe-out.

Let us consider any class ®-VCSP of the VCSP framework such that ® is strictly monotonic and for any a, 6 € E,a,b -< be any valuation different from T and The decision problem corresponding to the computation of the lower bound in this class can be formulated as: Problem 1 (MAX-AC-CSP) Given such a &-VCSP and a valuation v, is there a set such that the relaxation has a non empty arc-consistent closure and a valuation lower than v?

Theorem 1 MAX-AC-CSP is strongly NP-complete. Sketch of proof: The problem bel ongs to NP si nce computing the arc-consistent closure of a CSP can be done in polynomial time and we have supposed that ® and are polynomial in the size of their arguments.

We give the polynomial transformation from MAX2SAT [Garey et al. t 1976] to MAX-AC-CSP. An i nstance of MAX2SAT is defined by a set of e 2-cl auses and a positive integer k, the problem being the exi stence of a consi stent subset of of cardinality larger than k. Let be the set of n prepositional variables occurring in , We consi der the binary CSP (X, D, C) which is composed For exampl e, Figure 1 illustrates the micro-structure of the CSP built from the set

The transformation is clearly polynomial. Furthermore, one may prove that the exi stence of a truth assi gnment that satisfies at l east k cl auses of $ is equivalent to the exi stence of a relaxation with a nonempty arc-consistent closure and a valuation lower than with occurrences of l This shows that MAX2SAT oc MAX-AC-CSP.

Therefore, extending Really Full Look Ahead seems difficult since computing the lower bound itself is NP-complete. For idempotent VCSP, the bound may be computed using polynomial time algorithms for enforcing are-consistency [START_REF] Rosenfeld | Scene labeling by relaxation operations[END_REF]Snow and Freuder, 1990].

Experimentations

The Forward-Checking algorithm has been coded and applied to random VCSP generated as follows: a classical random CSP with 16 variables, domains of size 9 is generated as in [Hubbe and Freuder, 1992]. A first possibilistic VCSP is obtained by randomly assigning a valuation J, i, § or 1 to each constraint. A lexicographic VCSP is then built simply by using the transformation from possibilistic to lexicographic CSP described in section 3. This VCSP is a strong refinement of the original possibilistic CSP.

Because of limited space, we only report mean number of constraint checks performed to find an optimal assignment and prove optimality for a slice of the random CSP space (see Figure 2): constraint satisfiability is fixed to 60% and the constraint graph goes from tree structured CSP to a complete graph. At each point 50 classical, possibilistic and corresponding lexicographic CSP are solved with the follow-

036

CONSTRAINT SATISFACTION

i.e., uselessly trying to anticipate a possible inconsistency, is relatively inexpensive, even for Lex-VCSP. On inconsistent CSP, possibilistic CSP are not much harder than classical CSP, but the transition phase is apparently extended to the left. Last, but not least, lexicographic CSP are incredibly more difficult which again shows the computational complexity of strictly monotonic ®: rationality seems expensive.

Stronger argument could probably be obtained using recent developments in complexity theory, the transformations of Section 3.1 defining metric reductions between optimization problems [Krentel, 1988].

Conclusion

The VCSP framework enables the expression of a large number of real constraint satisfaction/optimization problems. If idempotent VCSP have already received a lot of attention and most classical CSP algorithms/properties have been extended to this setting [START_REF] Fargier | Hel ene Fargier. Probl emes de satisfaction de contraintes flexibles et application a V ordonnancement de production[END_REF], the case of non idempotent operators, a desirable property as it has been shown, seems much harder to tackle and few CSP algorithms have been extended to this case [START_REF] Freuder | [END_REF]. Since local consistency enforcing algorithms are unavailable in this case, we have considered a general class of bounds, that could be used in a depth first branch and bound algorithm and which have been derived from classical local consistency properties. It appears that at the level of arc-consistency, the problem of computing the bound is as difficult as solving a VCSP itself and other types of bounds have to be considered.