Radhwane Takouachet

Rim Benali-Cherif

El-Eulmi Bendeif

Christian Jelsch

Fatima Yahia Cherif

Ali Rahmouni

Nourredine Benali-Cherif

The supramolecular

Keywords: Adeninium hybrid compounds, Charge transfer, Aromatic stacking interactions, Supramolecular synthons, Intermolecular interactions, DFT

come

Introduction

The ability of small molecules to interact with DNA via an intercalative, groove-binding or electrostatic mode has led to the development of many novel anticancer [1][2][3] and antimicrobial agents [4]. In this context, nucleobases are key structure directing agents due to their rich and diverse combination of hydrogen bond donor and acceptor positions. Their propensity to selfassemble through hydrogen-bonding interactions has led to a plethora of supramolecular structures. As a significant nucleobase of DNA, adenine is an important naturally occurring nitrogen heterocycle present in nucleic acids. Owing to its unique biological activity and multiple supramolecular interaction, adenine has been extensively studied in varieties of fields such as pharmacology [5][6][7] and organic functional materials [8]. Recently, adenine has attracted many researchers to study its application as a novel hole-injection layer of OLEDs [9][10][11]. In addition, interesting adeninium-based organic-inorganic materials have been studied and developed for optoelectronic structures [12]. Moreover, in the past ten years, categories of similar adeninium hybrid compounds have achieved great progresses due to their potential application in the next generation of thin-film solar cell [13,14]. The different properties mentioned above are fundamentally correlated to the structural organizations and to the various intermolecular interactions that govern them. Thereby, understanding the influence of these interactions on the structural properties will be a critical step for the systematic design of functional materials with desired properties. From the structural point of view, adenine can forms crystalline salts in which the adeninium cation can adopt a variety of tautomeric forms. A combined theoretical and experimental study placed the relative stability of the adeninium tautomers in their ground state as 1H,9H > 3H,7H > 3H,9H ≫ 7H,9H > 1H,7H [15] (Fig. 1). Indeed, our careful research on the Cambridge Structural Database (CSD, ConQuest Version 2.0.5, 2020) [START_REF] Groom | [END_REF] for crystal structures containing adeninium tautomers results in 96 hits, 66 of them contain the 1H,9H tautomer. Therefore, this tautomer is present in almost all the molecular adeninium compounds [17].

The title compounds belong to a series of new selenite-adeninium hybrid materials synthesized in order to study their potentially and interesting optical and dielectric properties [18,19]. Selenite compounds are particularly interesting due to the fact that they often exhibit antioxidant, ferro-or antiferroelectric properties, anti-inflammatory, analgesic and antimicrobial activities, and structural phase transitions [20][21][22][23][24]. In addition, the interest devoted to these compounds is based on the fact that they consist of structurally interesting substances, in which the hydrogen bonds play a very important role [25], and also because a number of them exhibit non-linear optical properties [START_REF] Benali-Cherif | Corrélations structures propriétés ONL de 3 nouveaux composés hybrides: Compréhension des propriétés optiques non linéaires à travers la structure tridimensionnelle[END_REF].

Having the motivations stated above, we report in this paper the first compound (I) based on the hydrogen diselenite anion. According to the CSD data base (CSD, ConQuest Version 2.0.5, 2020) [START_REF] Groom | [END_REF] no compound based on this anion has been reported so far, while only two compounds based on diselenites are known (CSD refcodes: AHOYAX and TUYMUV). The second compound (II) described in this paper is the sixteenth based on the hydrogen selenite anion, only fifteen hybrid compounds based on this anion have been reported in the CSD.

The two adeninium based organic-inorganic hybrid compounds (I) and (II) were characterized by single-crystal XRD studies, and a well detailed structural study was illustrated. The graph-set descriptors of the intra-and intermolecular hydrogen bonding interactions stabilizing the two compounds were also discussed. To better understand the contribution of different intermolecular interactions to the supramolecular assembly, Hirshfeld surface analysis was performed. In addition, this work was complemented by DFT calculations to evaluate the charge transfer phenomenon observed in such molecular materials.

Experimental

2.1.Chemical preparation

All starting materials were purchased from Sigma-Aldrich and used without any further purification. The crystals of the two compounds (I) and (II) were obtained by the same chemical reaction and were collected from the same patch. Equi-millimolar amounts of the two starting materials (approximately 1 mmol), adenine and the selenious acid, were dissolved in water (25 mL). After continuously stirring for 1 h, the resultant solution allowed to evaporate at room temperature. Crystals of [(C5H6N5) + .(HSe2O5) -] (I) of brown prismatic shape and of [(C5H6N5) + .(HSeO3) -] (II) of pink needle shape were isolated after five weeks. The two types of crystals were manually separated and weighed, the weight ratio (𝐈) (𝐈𝐈) is 0.28. The selected single crystals of (I) and (II) were subjected to X-ray diffraction analysis.

2.2.Single crystal X-ray diffraction and structure refinement details

The single crystal diffraction measurements were performed on a Bruker APEX II and Nonius KappaCCD diffractometers for (I) and (II) respectively equipped with a CCD area detector with a graphite monochromatized MoKα radiation, λ = 0.71073 Å. Crystal data, data collection and structure refinement details of (I) and (II) are summarized in Table 1. The structures were solved in the space groups P21/a for (I) and P21/c for (II) by direct methods using the program SIR2014 [START_REF] Burla | [END_REF], and successive Fourier difference syntheses, and were refined against F 2 by weighted full-matrix least squares methods including all reflections with SHELXL-2018 program [START_REF] Sheldrick | Crystal structure refinement with SHELXL[END_REF]. All calculations were carried out using WingX software package [29]. Structural representations were drawn using Mercury [30]. All absorption corrections were performed with the REFDELF program [31]. All non-H atoms were refined anisotropically. For both compounds all hydrogen atoms were located in difference density Fourier maps. The structures with H atom positions shifted to average bond lengths from neutron diffraction using Mercury CSD 2.0 [30] were used for the geometrical analysis.

2.3.Hirshfeld surface analyses

The fingerprint plots of contacts were generated with the CrystalExplorer3.1 software [START_REF] Spackman | Hirshfeld Surface Analysis[END_REF]. The analysis of contact types and their enrichment were computed with the MoProViewer program [33]. In order to obtain integral Hirshfeld surfaces around the cation and the anion, they were computed around an ensemble of two moieties which are not in contact with each other in the crystal. As the Hc hydrogen atoms bound to carbon are less charged than the Ho/n atoms bound to oxygen or nitrogen, the two atom types have different interaction propensities and were treated separately.

2.4.DFT calculations

The energies and electronic properties were calculated using the X-ray crystal structure with H-X bond length elongated to standard neutron diffraction values. The calculations were carried out on two possibilities of asymmetric units and under periodic boundary conditions (PBC) for (I) and (II) at DFT level. The asymetric units are noted I-1, I-2, II-1 and II-2 and showed in Figure . S3. The hybride functional B3LYP [34] and 6-31G (d, p) basis sets [35] have been used. From the literature, it is well known that B3LYP functional can give structural properties in good agreement with experimental one [START_REF] Ajayi | Solvent-free mechanochemical synthesis, hirshfeld surface analysis, crystal structure, spectroscopic characterization and NBO analysis of Bis (ammonium) Bis ((4-methoxyphenyl) phosphonodithioato)-nickel (II) dihydrate with DFT studies[END_REF][START_REF] Brahim | Computational studies of Ni (II) photosensitizers complexes containing 1, 1′-bis (diphenylphosphino) ferrocene and dithio ligands[END_REF]. Gaussian 09 was used for all calculations [38]. The visualization and analysis of the calculated results were done using Gaussview [39] and GaussSum [40] softwares.

a R(int) = Σ(F o 2 -<F o 2 >)] /Σ(F o 2 ) b R1 = Σ||F o |-|F c || /Σ|F o |. c wR2 = {[Σw(F o 2 -F c 2 ) 2 ] /[Σw(F o 2 ) 2 ]} 1/2 . d Goodness-of-fit S = [Σw(F o 2 -F c 2 ) 2 /(n -p)] 1/2 ,
where n is the number of reflections and p the number of parameters.

Results and discussion

Description of crystal structure

Structural data for (I) and (II) are given in Table 1. For comparison between adeninium cations in the two structures, bond lengths and internal angles of pyrazine and imidazole rings are collected in Table 2. Both new crystalline compounds are stabilized by several hydrogen bonds that are summarized in Table 3.

The new organic-inorganic hybrid compounds (I) and (II), were prepared from adenine and selenious acid. Our initial products were selected based on the multifold noncovalent interactions of adenine through the Watson-Crick, Hoogsteen and sugar-face N atoms or N-H bonds, with small molecules. Adenine takes part in crystalline structures via its multiple functional groups, namely a five membered imidazole ring fused to a six-membered pyrazine ring, and an external amine group. The N atoms of the adenine molecule are assigned in Fig. 1 according to IUBMB nomenclature to facilitate the description of the structure analysis. Table 2. Selected structural parameters, bond lengths (Å) and bond angles (°) of adeninium cations in (I) and (II).

(I) (II) The crystal structure of (I) with the formula (C5H6N5) + .(HSe2O5) -belongs to the monoclinic P21/c space group. The asymmetric unit consists of one adeninium cation and one hydrogen diselenite anion. Structural analysis by X-ray diffraction has shown that proton transfer has taken place and the adeninium cation is in the common 1H,9H tautomeric form (Fig. 2). The protonation process is confirmed by the larger endocyclic angle around the protonated nitrogen site N1 on the Watson-Crick face. Hence, the internal angle at N1 [C6-N1-C2 = 123.74 (18)°] is increased from the mean reported value of 119.8° for unprotonated adenine [41]. This protonation enlarges the C-N-C angle by +3.94° (see Table 2). As in most purine derivatives, the adeninium base is close to flatness and the pyrimidine and imidazole rings are slightly folded around the C4-C5 bond by 1.83°. Examining the interatomic distances and angles of the adeninium cations in (I) shows that the majority of the bond lengths and angles found in (I) are fairly similar to those in the adeninium cations protonated at the N1 and N9 atoms [12,[42][43][44][45][46][47][48].

Bond lengths (Å) N6-C6 N1-C6 C6-C5 N3-C4 N3-C2 N1-C2 C4-C5 N7-C5 N7-C8 N9-C8 N9-C4 Bond angles (°) C2-N1-C6 N1-C6-C5 C4-C5-C6 N3-C4-C5 C2-N3-C4 N3-C2-N1 N7-C5-C4 N9-C4-C5 C8-N7-C5 N7-C8-N9 C4-N9-C8
Pyrazine Imidazole Pyrazine

Imidazole

The hydrogen diselenite anion (HSe2O5) -is formed from two selenious acid groups (H2SeO3), that have a common oxygen atom as a bridge between two selenium atoms. This bridged selenium-oxygen distance is elongated with bond lengths of 1.8148 ( 14) Å and 1.8281 ( 14) Å for Se1-O12 and Se2-O12 respectively. The first O3-Se2-O4 group shows two short Se-O bonds (Se2-O3 = 1.6619 ( 14) Å and Se2-O4 = 1.6569 (15) Å), whereas the second group O1-Se1-O2 has only one short bond length [Se1-O2 =1.6186 (15) Å]. One notes that the Se1-O1 bond is significantly longer (1.7508 ( 16) Å) indicating that the hydrogen atom (H1) is connected to the O1 atom causing elongation of the selenium-oxygen bond (Table S1). It is noteworthy that this is the first time that hydrogen diselenite anion has been observed in a crystalline form [START_REF] Groom | [END_REF]. The structure of (I) can be described as the succession of cationic layers sandwiched between parallel bilayers of hydrogen diselenite anions developing along the b-axis (Fig. 3).

In (I), the adeninium cations are arranged into; a centrosymmetric homosynthon 𝑅 (10) ring motifs [49] through a double N6-H6N•••N7 iii interaction that mimics the Hoogsteen pattern and a centrosymmetric homosynthon 𝑅 (8) ring motif via two N9-H9N•••N3 iv interactions that mimics the sugar pattern (Fig. 4) [50][51]. The whole Watson-Crick edge and atom C8 from the Hoogsteen edge are interacting with hydrogen diselenite anions (Fig. 4).

Adeninium base pairs are stacked together through an inversion center and the interplanar distance is 3.361( 14) Å (Fig. 5a) to form planar ribbons parallel to the [101] direction. The borders of these organic ribbons are framed by hydrogen diselenite ions (Fig. 4). Each adeninium cations dimer is interacting with four different hydrogen diselenite anions through

N6-H66N•••O3 ii (dD•••A= 2.878 (2) Å) and N1-H1N•••O4 ii (dD•••A=2.635 (2) Å)
hydrogen bonds, giving rise to an 𝑅 (8) heterosynthon on the Watson-Crick edge [52][53][54][55], and through weak and non-conventional C8-H8•••O12 and C2-H2•••O2 i intermolecular interactions thereby forming 𝑅 (10) and 𝑅 (11) ring motifs (Fig. 4). To the best of our knowledge, these three supramolecular features have been observed in only one similar compounds, the adeninium dichromate [56]. Moreover, the cationic molecules stack together to form twodimensional organic layers as shown in Fig. 3.

Additionally, the oxygen O1-H1 group of the selenite anion is hydrogen bond donor to the O3 oxygen of translated neighbour (X+1,Y,Z) to form a chain of formula (HSe O ) along the a-axis. This chain is described by the 𝐶 (6) graph set via the O1-H1

•••O3 i hydrogen bond [dD•••A = O1-H1•••O3= 2.621 (2)
Å] (Fig. 4). According to the geometrical parameters (Table 3), the O1-H1 Moreover, anions molecules play an important role in the three-dimensional network. They maintain cohesion in the organic ribbons layers, as the four oxygen atoms out of five are involved in hydrogen bonding as acceptors, while the OH group is hydrogen bond donor (Table 3 and Fig. 5b). Furthermore, this OH oxygen atom O1 exhibits an electrostatic contacts with the π -hole of C2 carbon atom of the pyrimidine ring, resulting in a very short O1-C2ring contact, the distance of O1 to the ring plane is only 2.94(2) Å. This cation•••O -supramolecular association contributes to the stabilization of the molecular structure of (I) (Fig. 5b). This oxygen atom, potential acceptor, is indeed not involved in any hydrogen bond.

Crystal Structure of Adeninium hydrogen selenite (II)

The crystal structure of (II) with the formula (C5H6N5) + .(HSeO3) -has an asymmetric unit containing one adeninium cation and one hydrogen selenite anion held together by hydrogenbonding and electrostatic interactions (Fig. 5). As observed in (I), the proton is also transferred from the selenious acid to the aromatic nitrogen (N1). This proton transfer enlarges the C2-N1-C6 endocyclic angle by +3.8° (see Table 2) in comparison to the unprotonated adenine [41]. The geometrical features of the adeninium cations are similar to those previously described in (I). Indeed, the adeninium cations exhibit the usual 1H, 9H tautomeric form and are nearly planar, with an r.m.s. deviation of 0.002 Å from the (C6/N1/C2/N3/C4-C5/N7/C8/N9) least-squares plane. The maximum deviations (0.0230(2) Å) from this mean plane was observed for the N1 atom. S1) are typical and are in good agreement with those observed in similar compounds [57].

Fig. 6. The asymmetric unit of adeninium hydrogen selenite (II) showing the atom-numbering scheme. Displacement ellipsoids are drawn at the 50% probability level.

The structure is built up from tunnels, prolonged along the b-axis at (½, y, ½) and (0, y, 1). These tunnels are formed by the intersections of two types of chains. The first one is the combination of the inorganic hydrogen selenite anions and the second is constituted by the protonated adeninium organic groups (Fig. 7a). This type of stacking has been observed in adeninium bis (adeninium) selenate bihydrates [58] and in cytosinium hydrogen selenite [57] compounds.

In (II), the 1H,9H-adeninium cations form together a non centrosymmetric Hoogsteen/sugar edge pair with N6-H66N•••N3 i and C2-H2•••N7 interactions thereby generating an 𝑅 (8) hetero-synthon motif [59] that contains both strong and weak hydrogen bonds. From the variety of bidentate hydrogen-bonded dimers that could be formed by adeninium cations, only this base pair is observed in (II). Instead, the Watson-Crick face and atom N9 from the sugar edge are involved in direct interactions with the hydrogen selenite anions.

Adeninium moieties are located in layers parallel to the (a,b) plane around z=n, with the stacking occurring in the a direction. Along the b-direction, the base pairs are arranged together into one dimensional cationic ribbons. The ribbon edges are bordered by hydrogen selenite anions which form together a supramolecular homo-synthon dimer assembled with two centrosymmetric related Se1•••O3 ionic interactions with Se•••O distances of 3.233(2) Å (Fig. 7b). This dimer is further linked to its inversion-related dimer through four hetero-synthons ionic dimers which are formed by means of O1•••Se1 electrostatic interactions and O1-H1•••O3 iii hydrogen bond (Table 3). These six dimers lead to the formation of a hexameric intermolecular interactions network. The hexamers centers are repeated at the middle of the four edges of the ab plane (Fig. 8a). Further, the connectivity between these hexamers generates a threedimensional honeycomb-like inorganic framework (Fig. 8b). The two-dimensional honeycomb-like layers are stacked along the crystallographic c-axis (Fig. 8b). The O1 oxygen atom (from the SeOH moiety) does not form any hydrogen bond, but is involved in three long distance H

•••O electrostatic interactions (dH•••O >2.7 Å), the shortest being the Se-O1-H1•••O1
Each adeninium cation interacts through its Watson-Crick face (N1 and N6 atoms) with the anionic homosynthon mentioned above through moderates N1-H1N•••O3 and N6-H6N•••O2 ii hydrogen bonds. Due to the interaction with inorganic dimers on one side, and with the inversion-related inorganic dimer on the other side, the N9 atom from the sugar face of adeninium cation is free to establish a N9-H9N•••O2 iv hydrogen bond to generate an 𝑅 (8) motif spread out along the b-direction. In addition, another 𝑅 (22) ring type is created by the interactions of four adeninium cations with two hydrogen selenite anions (Fig. 7b).

Similarly to (I), the cationic ribbons in (II) stack together to form two-dimensional layers running in the a-direction (Fig. 9). These layers are held together through aromatic stacking interactions established between, one via an inversion centre (dplanes= 3.270(4) Å) and one via a 2-fold axis. The distance of the C2•••C2 interaction around the 2-fold rotation axis centre is dC2•••C2 = 3.364 (4) Å. Each adeninium cation forms a total of four aromatic stacking interactions, i.e. two on each side of the moiety (Fig. 9). An energetic analysis of protonated nucleobases/chloride crystal structures [17,60] showed that the organic cations can form metastable base pairs which are stabilized by the surrounding anions. Furthermore, hexamers play an important role in stabilizing the crystal packing, in which each hexamer contribute to bridge three successive ribbons layers via hydrogen bond interactions (Fig. 9) In summary, in both compounds the adeninium cations adopt the most common 1H, 9Hadeninium tautomer, and their geometrical parameters is almost identical (see Table 2). The configuration of the adeninium cations is comparable to the thirteen adeninium-based organicinorganic hybrid compounds with the same tautomeric form reported in the CSD [START_REF] Groom | [END_REF]. An illustration of this comparison is represented in Fig. 10.

The structural investigation shows that the 1H,9H-adeninium in both crystal structures generate cationic ribbons, where they are formed from centrosymmetric homosynthons in (I) and heterosynthons in (II). Therefore, the supramolecular homo and hetero-synthon motifs are one of the classical motifs frequently observed in similar adenine-based hybrid compounds formed with different oxoanions [61][62][63][64][65].

Moreover, the inspection of hydrogen bonding network in both compounds shows a direct hydrogen-bond interactions between the adeninium cations and the hydrogen (diselenite/selenite) anions. In (II), the adeninium cations are connected to anions via three N- In the molecular packing of the two compounds, anions play an important role in maintaining the three-dimensional network through hydrogen bonds and electrostatic charge-charge interactions. In (I) the anions exercise their role in solo while in (II) they do it as hexamers.

In addition to the N-H•••N and C-H•••N hydrogen bonds connecting the purine bases in (I) and (II), weak stacking interactions are observed between the aromatic rings of the adeninium base in both compounds. It is interesting to note that the molecular arrangement of the adeninium cations in (I) is completely different to that observed in (II). While in (II), an arrangement of parallel cationic layers is found, the organic (C5H5N6) + adeninium planes in (I) take different orientations in the successive organic layers to form a zigzag pattern.

D-H•••A D-H (Å) H•••A (Å) D•••A (Å) D-H•••A(°) Compound (I) O1-H1•••O3 i C2-H2•••O2 i N6-H66N•••O3 ii N1-H1N•••O4 ii N6-H6N•••N7 iii N9-H9N•••N3 iv Compound (II) N6-H66N•••N3 i N6-H6N•••O2 ii N1-H1N•••O3 O1-H1•••O3 iii N9-H9N•••O2 iv 0.

Hirshfeld surface analysis and contacts enrichment ratio

The intermolecular contact types were computed by Hirshfeld surface analysis in order to evidence which contacts play a major role in the crystal packing stabilization. The enrichment ratio [START_REF] Jelsch | The enrichment ratio of atomic contacts in crystals, an indicator derived from the Hirshfeld surface analysis[END_REF] is a powerful descriptor to find which type of contacts are over-or under-represented in the crystal packing. The enrichment Exy compares the actual contacts Cxy and the Rxy "random" contacts, computed as if all types of contacts were equi-probable. The two crystals show globally similar packing trends with alternative layers of anions and cations, which is reflected by the correlation of the contacts types reaching 70% and of the contacts enrichment ratios at 54%. Fig. 12 shows the Hirshfeld interface between the cation and anion layers which are parallel to the (a,b) plane. The contact surface of the organic cation layers is constituted by up to 84% of hydrogen atoms (Table.S2). At the layers interface, the contacts of selenium with all atoms of the cation (C, Hc, N) are favoured except those with the positively charged Hn atoms.

Overall, hydrogen occupies the largest proportion of the Hirshfeld surfaces, reaching 28.9% for (I) and 34% for (II) most of which is constituted by the polar Hn/o type (Table.

DFT quantum chemical calculations

Frontier molecular orbital analysis

The Frontier molecular orbitals (FMOs) of dimers complexes are imperative parameters for determining the way the monomers molecules interacts. As appear from Fig. 13, the HOMO orbitals of the two compounds are exclusively delocalised on the atoms of anions, when these laters have small contributions in the LUMO orbitals that are mainly located over all adeninium atoms. The LUMO orbitals in the two compounds are dues to the interactions between π-type atomic orbitals. As shown by Fig. 13, the interactions between adeninium and hydrogen diselenite in configuration I-1 result in lower HOMO energy and higher energy LUMO than their interactions in configuration I-2. Consequently the HOMO-LUMO gap of configuration I-1 is larger than the HOMO-LUMO gap of configuration I-2. These constatations with the comparison of total configurations energies let to conclude that the configuration I-1 is more stable than configuration I-2. The same conclusion is made for II. In that case, the configuration II-2 is more stable than configuration II-1. Under periodic bondary conditions, the anion-cation dimers exhibit smaller energy in magnitude than their isolated configurations (Table S4).

The density of state (DOS) and the partial density of state (PDOS) spectrum created by convoluting the molecular orbital using GAUSSIAN curves of unit height and full width at half-maximum of 0.2, demonstrate the number of molecular orbitals and the contributions of adeninium and hydrogen diselenite (I) or hydrogen selenite (II) to the molecular orbitals in certain energy range. Compounds (I) and (II) exhibit équivalent DOS and PDOS spectra in both configurations (Fig. 14). The energy difference between the consecutive orbitals are generally small. From PDOS (Fig. 14), we note that the occupied orbitals with highest energy are those of the anionic moities (HSe2O5) -and (HSeO3) -for (I) and (II) respectively. The lowest energy virtual orbitals are pure adeninium orbitals in both compounds. The interactions between the orbitals of the two entities occur at lower energies. The firsts excited states can be expected to have similar structure to the fondamental state, and feeble energy electronic transitions shall occur without geometric relaxations.

Molecular electrostatic potential (MEP)

The purpose of the studies of molecular electrostatic potential (MEP) surfaces of (I) and (II) is to resolve the existence of electrostatic interactions between the adeninium cations and hydrogen selenite/diselenite anions based on their charge distribution. The attractive or repulsive nature of electrostatic interactions of (I) and (II) with other units in crystals can be also identified [START_REF] Seminario | Recent Developments and Applications of Modern Density Functional Theory[END_REF]. The MEP surfaces of the studied compounds (Fig. 15) show that the interaction region between the adeninium cation and the protonated hydrogen diselenite are very attractive in both configurations. The same behaviour is observed in both compounds. The regions around the (HSe2O5) -and (HSeO3) -anions are very attractive toward positive charge. These results are good arguments for the stability of the crystal structure for both compounds.

Mulliken partial charges

The results reported in Table 5 allow to compare the Mulliken partial charges in both compounds. The atoms C6, C8, N6, H6N, and H9N exhibit partial charges different by about 0.05e. These differences are attributed, on the one hand, to the adeninium orientation change toward the hydrogen diselenite and hydrogen selenite in (I) and (II) respectively and, on the other hand, to the difference between the charge distributions of the two anions. The sum of partial charges of adeninium cation is 0.75 (I-1), 0.925 (I-2), 0.72 (PBC) in (I) and 0.827 (II-1), 0.79 (II-2), 0.799 (PBC) in (II). It can be concluded that charge transfer occurs from anions to adeninium cations. This observation is in accordance with the study of protonated nucleobases in their chloride salt crystals which found that the cations are not fully ionized [17,60]. This charge transfer is more pronouced when the configuration is more stable and confirmed by results of calculations under periodic boundary conditions.

Conclusion

To summarize, we have reported in this work, the synthesis, experimental and theoretical characterization of two new adeninium-based organic-inorganic hybrid compounds of formula: (C5H6N5) + .(HSe2O5) -(I) and (C5H6N5) + .(HSeO3) -(II). The molecular structures of the studied compounds were determined by single crystal X-ray diffraction study. The atomic arrangement of (I) can be described as the succession of cationic layers sandwiched between parallel bilayers of hydrogen diselenite anions developed along the b-axis, while in (II) the structure is built up from tunnels, prolongated along the b-axis. The structural investigation reveals the ability of the 1H,9H adeninium cations to exhibit a variety of hydrogen bonding motifs with hydrogen selenite/diselenite anion. Furthermore, supramolecular homo and hetero-synthons found in (I) and (II) play an important role in shaping these supramolecular compounds. From the structural comparative study, the stacking interactions present in both compounds were found to be geometrically different. The stacking of organic cations is stabilized in the crystal packing of (I) and (II) by the ionic bridges with the surrounding anions; this effect should be considered as important in crystal engineering There is an interesting electrostatic association, seen only in compound (I), between the SeOH oxygen electron lone pairs and the aromatic cation. In addition, the complementary Hirshfeld surface analysis, enrichment ratios (E) and fingerprint plots were used to investigate the relative proportions of intermolecular close contacts existing within the compounds. These analyzes have shown that O•••H interactions represent the major contribution of the total Hirshfeld surface in both compounds.

Moreover, HOMO/LUMO energy gaps, MEP surfaces and atomic partial charges have been computed using DFT calculations to get a close insight into the studied compounds. The DFT calculations allowed completing experimental results and show an interesting charge transfer from the inorganic anions to the organic cations.

The results discussed in this work can be useful for investigating the bioactivité process of similar molecular materials through, for example, docking approaches.

Fig. 1 .

 1 Fig. 1. Adenine structure showing the numbering scheme and characterized by three pairing edges: Watson-Crick, Hoogsteen and sugar.

Fig. 2 .

 2 Fig. 2. The asymmetric unit of adeninium hydrogen diselenite (I) showing the atomnumbering scheme. Displacement ellipsoids are drawn at the 50% probability level.

Fig. 3 .

 3 Fig. 3. A view of the crystal packing of (I) showing the stacking of adeninium cations and hydrogen diselenite anions.

Fig. 4 .

 4 Fig. 4. Part of packing diagram of (I) showing the 1D cationic ribbons framed by hydrogen diselenite anions and illustrating the formation of 𝑅 (8), 𝑅 (10), 𝑅 (11) and 𝑅 (10) ring motifs and 𝐶 (6) infinite chain. Dashed lines indicate N/O-H•••O, N-H•••N and C-H•••O hydrogenbonding interactions.

Fig. 5 .

 5 Fig. 5. A fragment of the (I) crystal structure, (a) Crystallographic autostereogram of the stacking interaction between adeninium cations contributing to the maintenance of the organic layers. The a axis corresponds to the horizontal direction. (b) Electrostatic interaction between the O1 atom and the adeninium cation. Intermolecular interactions are shown as black dashed lines.

  Inspection of the anion bond distances shows the presence of two short and one long Se-O bond, clearly indicating the protonation of O1 atom [Se-O1= 1.773(2) Å] , whereas both O2 and O3 atoms are bare [Se-O2= 1.638(2) Å and Se-O3= 1.673(2) Å]. This observation confirms that one of the protons was transferred from the selenious acid to the adenine molecule. The hydrogen selenite anion (HSeO3) -forms a trigonal prism with the three oxygen atoms and one selenium atom at the apexes. The geometrical features of the inorganic anions (HSeO3) -(Table

Fig. 7 .

 7 Fig. 7. (a) The crystal packing of (II) in projection along the b-axis, showing the cationic and anionic entities arranged in tunnels. (b) A fragment of (II) showing the supramolecular synthons and the graph set describing intermolecular interactions

Fig. 8 .Fig. 9 .

 89 Fig. 8. Molecular packing diagram of hydrogen selenite anions in (II) showing honeycomb-like molecular network. (a) 2D crystallographic autostereogram and (b) 3D view

  H•••O hydrogen bonds, while in (I), the two entities are connected through two N-H•••O interactions and two C-H•••O weaker hydrogen bonds.

Fig. 10 .

 10 Fig. 10. Comparison of the geometry of adeninium cations in (I) and (II) with the thirteen 1H, 9H-tautomers of adeninium cations deposited in the CSD with their REFCODE.

  (i) x+1, y, z; (ii) x+1, y, z+1; (iii) -x, -y, -z+1; (iv) -x+1, -y, -z; Symmetry codes for (II): (i) -x+½, y-½, -z; (ii) -x+1, -y+1, -z+1; (iii) x+½, -y+ 3 2 , z; (iv) x-½, -y+ 3 2 , z-1.

  4). For both compounds, the major contacts are constituted by strong O•••H-N/O and N•••H-N hydrogen bonds. The Ho/n•••O contacts are enriched (E = 1.46 for (I) and E = 2.37 for (II)); the difference corresponds to the presence of three strong N-H•••O hydrogen bonds in (II) and only two in (I). Furthermore, there is a double proportion of Se•••O electrostatic interactions in crystal compared to compound (II), due to the presence of hydrogen diselenite ion in the (I) crystal. The Se…O contacts are moderately over-represented in both crystals. Also, the C-H•••O weak hydrogen bonds have a higher content and are more enriched in (I) than in (II). The hydrophobic C•••C contacts are limited (below 6%) in the two crystals but are among the most enriched at Ecc>1.8 due to stacking between the aromatic pyrazine rings. The C•••N and to a lesser extend the N•••N contacts are also quite favoured as a consequence of the aromatic stacking. The fingerprints of both compounds (Fig. 11) exhibit some similarity in the global shape and the contributions of the different types of intermolecular contact. The O•••H/H•••O contacts can be considered as dominant and appear as a pair of sharp symmetric spikes at short distance. The N•••H contacts contribute also secondarily to the spikes. The presence of these long spikes at short intermolecular distances is characteristic of strong O-H•••O and N-H•••O hydrogen bonds.

Fig. 11 .

 11 Fig. 11. Fingerprint plots showing the main contacts of the two compounds. Reciprocal contacts were not merged; they can be deduced by symmetry of the plots.

Fig. 12 .

 12 Fig. 12. Crystallographic autostereogram view of Hirshfeld surface at the interface of the organic cations layer (shown in front) and the layer of selenite anions (compound II). Surface coloring: red: oxygen, yellow: selenium, light grey: Hc hydrogen, light blue: Ho hydrogen (H-O).

Fig. 13 .

 13 Fig. 13. HOMO and LUMO plots and HOMO-LUMO gaps of configurations I-1, I-2 and II-1, II-2 for (I) and (II) respectively

Fig. 14 .

 14 Fig. 14. DOS (A, C, E and G) and PDOS (B, D, F and H) spectra of configurations I-1, I-2 and II-1, II-2 for (I) and (II) respectively, and their energy levels of the Frontier Molecular Orbitals.

Fig. 15 .

 15 Fig. 15. Molecular electrostatic potential (MEP) of configurations I-1, I-2 and II-1, II-2 for (I) and (II) respectively showing the intermolecular interactions. The iso-surface was drawn at 0.0004 e/(Bohr) 3 level of electron density

Table 1 .

 1 Main crystallographic data and structure refinement details for (I) and (II).

	Crystal data	(I)	(II)
	Empirical Formula	C5 H7 N5 O5 Se2	C5 H7 N5 O 3 Se
	Molecular weight (g/mol)	375.08	264.12
	Diffractometer,	Bruker APEX-II CCD	Nonius KappaCCD
	Radiation type	Mo K (=0.71073 Å)	Mo K (=0.71073 Å)
	T (K)	293(2)	293(2)
	Calculated density (Mg/m 3 )	2.410	2.034
	Crystal system	Monoclinic	Monoclinic
	Space group	P 21/c	P 21/a
	a (Å)	6.2851 (3)	6.5612 (2)
	b (Å)	21.0046 (2)	12.7621 (2)
	c (Å)	8.1402 (2)	10.4529 (3)
	 (°)	105.838 (1)	99.846 (3)
	V (Å 3 )	1033.84 (6)	862.38 (4)
	Z	4	4
	µ (mm _1 )	7.17	4.35
	Crystal size (mm)	0.15 × 0.10 × 0.08	0.15 × 0.05 × 0.04
	No. of measured, independent and	19963, 5116	13979, 2507
	observed [I > 2(I)] reflections	3995	1940
	R(int) a	0.044	0.085
	Refinement
	R[F 2 > 2(F 2 )] b , wR(F 2 ) c , S d	0.033, 0.087, 1.07	0.034, 0.091, 1.03
	No. of unique reflections	5116	2507
	No. of parameters	154	127
	Δρmax, Δρmin (e Å -3 )	1.16, -0.88	0.55, -0.71

  •••O3 and the N1-H1N•••O4 hydrogen bonds seem to be the strongest hydrogen bonds in the 3D molecular packing of (I). The electrostatic attractive contact d=2.77 Å between atoms Se1 and O4 (symmetry X, ½-Y, ½+Z) is much shorter than the sum of van der Waals radii 1.90+1.52 = 3.42 Å. There are five other Se•••O contacts in crystal I which are all shorter than the sum of van der Waals radii (in the range 2.97-3.21 Å).

Table 3 .

 3 Geometric parameters of the O/N-H•••O/N hydrogen bonds parameters (Å, °).

  Table.4. Analysis of contacts on the Hirshfeld surface. Reciprocal contacts X…Y and Y…X are merged. The second line shows the chemical content on the surface. The % of contact types between chemical species is given in the next six lines, followed by their enrichment ratios. The major contacts, as well as the most enriched ones, are highlighted in bold characters. The polar Hn/o hydrogens bound to nitrogen or carbon are distinguished from the less charged Hc atoms bound to a carbon atom.

	(I)	O	N	Ho/n	Se	Hc	C
	surf%	23.8	13.4	20.4	18.4	8.5	15.6
	O	0.0
	N	2.4	1.8		%	contacts
	Ho/n	14.9	12.4	0.5
	Se	15.9	1.1	5.8	4.6
	Hc	8.6	0.4	3.0	2.7	0.0
	C	7.5	5.5	4.5	2.3	2.2	4.1
	O	0.00
	N	0.38	1.11			enrichment
	Ho/n	1.46	2.36	0.11
	Se	1.75	0.24	0.75	1.34
	Hc	2.06	0.17	0.86	0.87	0.00
	C	1.01	1.44	0.71	0.41	0.87	1.81
	(II)	O	N	Hn/o	Se	Hc	C
	%	18.7	15.9	22.6	13.3	11.4	18.1
	O	0.0
	N	1.0	3.3		%	contacts
	Hn/o	21.2	6.5	2.7
	Se	7.6	1.5	5.1	1.9
	Hc	5.6	4.7	2.2	7.0	0.6
	C	2.8	10.2	6.3	2.8	0.9	6.1
	O	0.00
	N	0.17	1.41			enrichment
	Hn/o	2.37	0.92	0.50
	Se	1.44	0.36	0.79	0.97
	Hc	1.35	1.43	0.43	2.33	0.54
	C	0.41	1.91	0.77	0.56	0.24	1.98

Table . 5

 . . Mulliken atomic partial charges in (I) and (II).

			(I)			(II)
		Config. I-1 Config. I-2	PBC	Config. II-1 Config. II-2	PBC
	1 Se	1,021	1,022	1,042	-	-	-
	2 Se	0,988	0,872	1,017	0,875	0,888	0,904
	3 O	-0,557	-0,576	-0,611	-0,704	-0,631	-0,664
	4 O	-0,661	-0,672	-0,685	-0,592	-0,617	-0,610
	5 O	-0,594	-0,627	-0,607	-0,660	-0,725	-0,729
	6 O	-0,553	-0,576	-0,585	-	-	-
	7 O	-0,712	-0,688	-0,663	-	-	-
	8 H	0,319	0,318	0,371	0,255	0,294	0,298
	9 N	-0,562	-0,581	-0,573	-0,572	-0,555	-0,567
	10 N	-0,643	-0,651	-0,665	-0,538	-0,521	-0,545
	11 C	0,634	0,651	0,665	-0,652	-0,641	-0,653
	12 C	0,201	0,224	0,202	-0,490	-0,542	-0,514
	13 N	-0,489	-0,447	-0,490	-0,428	-0,492	-0,487
	14 C	0,513	0,540	0,526	0,491	0,495	0,281
	15 C	0,276	0,272	0,283	0,277	0,291	0,208
	16 N	-0,569	-0,543	-0,579	0,216	0,204	0,618
	17 N	-0,495	-0,513	-0,511	0,637	0,632	0,355
	18 C	0,292	0,380	0,288	0,302	0,303	0,511
	19 H	0,165	0,166	0,192	0,334	0,315	0,314
	20 H	0,151	0,173	0,125	0,302	0,325	0,312
	21 H	0,331	0,292	0,341	0,299	0,341	0,340
	22 H	0,341	0,303	0,341	0,161	0,189	0,163
	23 H	0,310	0,333	0,293	0,313	0,301	0,308
	24 H	0,294	0,326	0,282	0,175	0,145	0,155

Acknewlegments

We gratefully acknowledge the X-ray diffraction platform PMD 2 X of the Institut Jean Barriol at Université de Lorraine, Pr H. Merazig, Unité de Recherche de Chimie de l'Environnement et Moléculaire Structurale, CHEMS, Université de Constantine, Algeria, and Dr M. Giorgi, Faculté des Sciences et Techniques de Saint Jerôme, Marseille, France, for providing access to the X-ray diffraction facilities. We gratefully acknowledge Pr S. Humbel, CTOM, Aix Marseille Univ, CNRS, Centrale Marseille, iSm2, Marseille, France for providing calculation facilities. We also thank the Algerian MESRS (Ministère de l'Enseignement Supérieur et de la Recherche Scientifique) and DGRSDT (Direction Générale de la Recherche Scientifique et du Développement Technologique) and Abbes Laghrour Khenchela University, for financial support.

Appendix A. Supplementary data CCDC N o . 1996166 for compound (I) and CCDC N o . 1578761 for compound (II) contains the supplementary crystallographic data for this paper. The data can be obtained via www.ccdc.cam.ac.uk/datarequest/cif by e-mailing data_request@ccdc.cam.ac.uk or by contacting the Cambridge Data Cente, 12 Union Road, Cambridge, CB2IEZ, UK Supplementary materials . Table S1. Selected structural parameters, bond lengths (Å) and bond angles (°) of anions in (I) and (II)


Nadia Kari
email: nadia.kari@univ-paris-est.fr

Divitha Seetharamdoo
email: divitha.seetharamdoo@ifsttar.fr

Jean-Marc Laheurte

François Sarrazin

Modal Analysis of Chiral Metamaterial Using Characteristic Mode Analysis and Eigenmode Expansion Method

A chiral metamaterial (MTM) is analyzed using two modal analysis methods: Characteristic Mode Analysis (CMA) and Eigenmode Expansion Method (EEM). Chiral MTMs are commonly associated to antennas and other microwave devices due to their ability to interact with electromagnetic waves and alter their polarizations. Here, the interaction of a chiral helix with linearly polarized electromagnetic plane waves is studied and asymmetric transmission is demonstrated. The different metrics given by CMA and EEM are analyzed and compared. It is shown that the modal weighing coefficient is a good metric to analysis the chiral properties of the MTM and these results are validated using a full-wave approach. It is also shown that if the two modal approaches propose very close results qualitatively, the maximum value of the modal current density obtained by EEM is closer to the one obtained by full-wave simulations. The modal approaches presented to analyse chiral MTM can be applied for the analysis of circularly polarised chiral metamaterial-inspired antennas.

I. INTRODUCTION

Over the last two decades, numerous research works have investigated Metamaterials (MTMs) which are highly desirable for applications ranging from antennas to microwave devices. The significant contribution of MTMs in improving antenna performances, such as gain [START_REF] Xiong | Impedance bandwidth and gain improvement for microstrip antenna using metamaterials[END_REF], bandwidth and radiation pattern [START_REF] Alu | Epsilon-nearzero metamaterials and electromagnetic sources: Tailoring the radiation phase pattern[END_REF] has been widely demonstrated. In [START_REF] Ziolkowski | Metamaterial-inspired engineering of antennas[END_REF], MTM-inspired antennas include resonant parasitic elements into the nearfield region of a driven radiator so that the strong coupling between them helps to achieve high radiation efficiency. More recently, exotic electromagnetic properties of chiral MTMs have been experimentally demonstrated including negative index refraction [START_REF] Li | Chiral metamaterials with negative refractive index based on four "u" split ring resonators[END_REF], [START_REF] Wang | Nonplanar chiral metamaterials with negative index[END_REF], elliptical or circular dichroism [START_REF] Zhukovsky | Elliptical dichroism: operating principle of planar chiral metamaterials[END_REF], polarization transformation [START_REF] Chin | Metamaterial polarizers by electricfield-coupled resonators[END_REF] and giant optical activity [START_REF] Li | Magnetic resonance hybridization and optical activity of microwaves in a chiral metamaterial[END_REF]. Another appealing feature is the circular conversion dichroism yielding an asymmetric transmission phenomenon which can be of interest for the design of circularly polarized MTM antennas [START_REF] Rabah | Analysis of miniature metamaterial and magnetodielectric arbitrary-shaped patch antennas using characteristic modes: Evaluation of the q factor[END_REF].

Calculation of the effective parameters (electric permittivity and magnetic permeability) [START_REF] Mendhe | Metamaterial properties and applications[END_REF], [START_REF] Ziolkowski | Applications of metamaterials to realize efficient electrically small antennas[END_REF] is a common technique for the design and evaluation of MTMs. However, numerical techniques based on modal expansions such as the Eigenmode Expansion Method (EEM) [START_REF] Ramm | Theoretical and practical aspects of singularity and eigenmode expansion methods[END_REF] and Characteristic Mode Analysis (CMA) [START_REF] Vogel | Characteristic mode analysis: Putting physics back into simulation[END_REF] are now extensively studied [START_REF] Chen | Characteristic modes: Theory and applications in antenna engineering[END_REF] to bring more physical insight on the radiation phenomena. EEM and CMA are attractive methodologies for MTM antenna designs because they are excitation independent and applicable to arbitrarily shaped structures. Furthermore, since it has been claimed [START_REF] Ziolkowski | Metamaterial-inspired engineering of antennas[END_REF] that enhanced antenna performances of electrically small MTM antennas are obtained by stored energy compensation, the evaluation of modal stored energies by MTMs is of great interest. Stored energy is based on the knowledge of the current sources of energy densities and on the evaluation of eigenvalues [START_REF] Capek | The measurable q factor and observable energies of radiating structures[END_REF], [START_REF] Ozuem | Stored energy evaluation of metamaterials based on theory of characteristic mode[END_REF]. The comparison between CMA and EEM is interesting since CMA is an approximate and fast approach with real eigenvalues and eigencurrents, whereas EEM is an absolute approach with complex eigenvalues and eigencurrents.

To date, chiral MTMs have been analysed using the numerical or analytical evaluation of reflection and transmission coefficients [START_REF] Semchenko | Stored and absorbed energy of fields in lossy chiral single-component metamaterials[END_REF]. The purpose of this paper is to demonstrate that modal approaches can bring more physical insight for the design of efficient chiral antennas. To support this objective, it is essential to show which metrics of modal approaches are relevant to highlight the properties of chiral MTM and how to compare them to existing techniques [START_REF] Saenz | Modeling of spirals with equal dielectric, magnetic, and chiral susceptibilities[END_REF]. In [START_REF] Kari | Analysis of a chiral helix metamaterial using eigenmode expansion method and characteristic mode theory[END_REF], an intrinsic chiral MTM based on a spiral helix was analyzed for the first time using both EEM and CMA. The net stored energy of the inclusion was evaluated and it was demonstrated that a circular polarized (CP) wave is transmitted by the helix when it is excited by a linearly polarized plane wave at normal incidence. In this expanded paper, we are more specifically interested in studying, interpreting and comparing the metrics given by both CMA and EEM methods for the chiral MTM helix. These metrics include stored energy, Modal Significance (MS), modal surface current density and Modal Weighting Coefficients (MWCs). The asymmetric transmission of the chiral helix is demonstrated using the MWCs and validated by a comparison with a full-wave analysis. A qualitative and quantitative analyses will also be proposed to highlight the most appropriate modal approach for studying this chiral MTM.

The paper is organized as follows. In section II, CMA and EEM are introduced and compared. Section III gives a brief review of the chiral MTM helix under consideration and details its properties such as the asymmetric transmission of linearly polarized EM waves. In section IV, results in terms of modal metrics are presented along with a numerical validation using a full-wave analysis. Section V finally discusses the relevance of the modal approaches for studying chiral MTM while proposing a critical comparison between the two approaches CMA and EEM.

II. MODAL APPROACHES

A. Eigenmode Expansion Method (EEM)

The eigenmodes are described by the standard eigenvalues equation [START_REF] Ramm | Theoretical and practical aspects of singularity and eigenmode expansion methods[END_REF], [START_REF] Harrington | Theory and computation of characteristic modes for conducting bodies[END_REF] as follows:

Z( I eem n ( r, ω)) = Υ eem n I eem n ( r, ω). ( 1
)
where Z is a linear operator, I eem n and Υ eem n are the eigencurrents and eigenvalues, respectively, r represents the field point and ω denotes the angular frequency. The EEM can be computed from a modal decomposition of the Method of Moments (MoM) impedance matrix [START_REF] Harrington | Field computation by moment methods[END_REF]. It is obvious from (1) that the eigenvalues and the eigencurrents are independent from the incident field. Both Υ eem n and I eem n are complex quantities.

Let us consider a Perfect Electric Conductor (PEC) body excited with an incident field E i . The induced current I produced by the incident field radiates a scattered field E s . After applying the boundaries conditions on the tangential field, the scattered field can be defined by [START_REF] Harrington | Field computation by moment methods[END_REF]:

[ E s ] tan = -Z( I eem ). (2)
Equation ( 2) demonstrates that the tangential component of the electric field and the current distribution have the same behavior on the surface of PEC bodies. Applying the orthogonality, the total current is given by:

I eem = n I eem n , E i Υ eem n I eem n , I eem n I eem n . (3)
Using ( 1) and ( 2) and considering the Poynting theorem, the eigenmodes can be expressed as

Υ eem n = P rad ( I eem n ) + jω[W m ( I eem n ) -W e ( I eem n )] I eem n * , I eem n , (4)
where P rad ( I eem n ) is the radiated power and [W m ( I eem n ) -W e ( I eem n )] represents the net stored energy of the eigenmode. After normalizing (4) to I eem n * , I eem n , the eigenvalues become:

Υ eem n = P rad ( I eem n ) + jω[W m ( I eem n ) -W e ( I eem n )]. (5)
To easily manipulate the eigenvalues of the eigenmodes, which are complex quantities as defined above, it is important to define the ratio between the imaginary and real parts of the eigenvalues Υ eem n [START_REF] Bernabeu-Jiménez | A comparison between natural resonances and characteristic mode resonances of an infinite circular cylinder[END_REF], [START_REF] Garbacz | A general expansion for radiated and scattered fields[END_REF]. Using (5), we can introduce:

λ eem n = [W m ( I eem n ) -W e ( I eem n )] P rad ( I eem n ) . (6)
As λ eem n represents the ratio between the net stored power and the radiated power, it gives some physical insight on the nature of the eigenmodes [START_REF] Huang | Study on the relationships between eigenmodes, natural modes, and characteristic modes of perfectly electric conducting bodies[END_REF]. Therefore, for antennas and scattering problems, it is interesting to focus on the eigenmodes with the smallest magnitude of λ eem n .

B. Characteristic Mode Analysis (CMA)

Characteristic modes (CMs) can be defined with the generalized eigenvalues problem [START_REF] Chen | Characteristic modes: Theory and applications in antenna engineering[END_REF]:

X( I cha n ( r, ω)) = λ cha n R( I cha n ( r, ω)), (7)
where λ cha n are the characteristic values, I cha n are the characteristic currents, and R and X are respectively the real and imaginary parts of the impedance operator [START_REF] Harrington | Field computation by moment methods[END_REF], R = Z+Z * 2 and X = Z-Z * 2j being symmetric and real matrices [START_REF] Chen | Characteristic modes: Theory and applications in antenna engineering[END_REF], [START_REF] Warnick | Numerical analysis for electromagnetic integral equations[END_REF]. Since I cha n is a real quantity, the characteristic currents are equiphase. The characteristic values are defined by:

λ cha n = [W m (I cha n ) -W e (I cha n )] P rad (I cha n ) . ( 8
)
Based on the reciprocity theorem, it is known that if Z is a linear symmetric operator then R and X are real symmetric operators. Therefore, the characteristic values λ cha n and the characteristic currents I cha n are real quantities. It is important to note that the characteristic values and currents are independent of any excitation. The characteristic currents I cha n on the PEC depend only on the conductor shape and size [START_REF] Harrington | Theory and computation of characteristic modes for conducting bodies[END_REF]. The total current I cha n can be defined as the combination of all modal currents:

I cha = N n=1 c n I cha n , (9)
where c n is the complex modal expansion coefficient which defines the weighting of each mode of the total current. The total current can also be written as:

I cha = N n=1 V i n I cha n 1 + jλ cha n , (10)
where V i n represents the modal excitation coefficient. By combining ( 9) and [START_REF] Mendhe | Metamaterial properties and applications[END_REF], the modal expansion coefficients can be expressed as:

|c n | = V i n 1 + jλ cha n = |V i n |MS, and (11)
MS = 1 1 + jλ cha n . (12)
From [START_REF] Ziolkowski | Applications of metamaterials to realize efficient electrically small antennas[END_REF], it is interesting to note that the excitation of the desired mode not only requires a large Modal Significance (MS) but also a large modal excitation coefficient. Moreover, to better define the coupling between the nth characteristic current and an external excitation, we define the MWCs as follows:

W n = V i n 1 + jλ cha n . ( 13
)
The eigenvalues of the CMs represent the ratio between the net stored power and the radiated power. As for the EEM, the net stored energy within a scattering or radiation problem is proportional to the magnitude of the eigenvalues.

C. Stored energy for CMA and EEM

For both EEM and CMA, the eigenvalues give a physical insight in terms of net stored energy. Modes with positive eigenvalues are linked to magnetic stored energy, whereas modes with negative eigenvalues are linked to electric stored energy. Zero eigenvalues indicate a resonance. Also, the evaluation of the stored energy in the near-field allows to better classify the MTM as a magnetic or an electric structure, i.e., to better associate MTMs to antennas according to their electric or magnetic nature. The expression of the stored energy for the radiating structure was determined in [START_REF] Capek | The measurable q factor and observable energies of radiating structures[END_REF]. Other approaches were proposed in [START_REF] Ozuem | Stored energy evaluation of metamaterials based on theory of characteristic mode[END_REF], [START_REF] Vandenbosch | Reactive energies, impedance, and q factor of radiating structures[END_REF]. It is important to note that for EEM, the computation of the stored energy is based on the ratio between the imaginary and real parts of the eigenvalues, as mentioned in [START_REF] Zhukovsky | Elliptical dichroism: operating principle of planar chiral metamaterials[END_REF]. In this paper, the evaluation of the stored energy W sto is based on the expression [START_REF] Capek | Optimal composition of modal currents for minimal quality factor q[END_REF] given by:

W sto = 1 4ω I H X I, ( 14
)
where X is expressed in ( 13) by:

X = ω ∂X ∂ω , (15)
I represents the eigencurrents and the superscript H denotes the Hermitian transpose. The stored energy W sto is the contribution of electric (W e ) and magnetic (W m ) energies. These quantities are defined as:

W m = 1 8ω I H X m I, and (16)
W e = 1 8ω I H X e I, (17)
where X is the reactance part of the impedance matrix and X e = X -X and X m = X + X . These equations are used both for CMA and EEM to compute the energy stored by complex structures. For CMA, the stored energies are real quantities and for EEM, the stored energies are complex quantities since the eigencurrents are complex values. The net stored energy is thus evaluated as e(W m -W e ).

D. Comparison between CMA and EEM

The main features and properties of the metrics associated to the two modal approaches are summarised in Table I. CMA is an approximate approach since the characteristic values and currents are assumed real, i.e, the phase current is neglected, making the interpretation of CMs easier. A major feature that makes CMA attractive is that the CMs are orthogonal in terms of currents and far fields. Thus, the CMs form a very useful basis set in the expansion of any possible fields or currents associated with a PEC body. On the other hand, EEM is an absolute approach because the eigen values and currents are complex quantities. The EEM eigenmodes do not hold the electromagnetic power orthogonality in general since the eigenmodes are complex. In section IV, a comparison between the two methods is performed.

III. DESCRIPTION OF CHIRAL METAMATERIAL

In this section, a brief review of chirality is introduced. Chiral MTMs represent a special category of artificial structures The stored energy is complex (complex currents) and the net stored energies is evaluated as the real part of the stored energy The characteristic (eigen) values and currents are independent from the source.

referring to geometries that cannot superpose to their mirror images and have no plane of symmetry. The electromagnetic properties of chiral material are Optical Activity (OA) and Circular Dichroism (CD). OA represents the rotation of a polarization wave after propagating through a chiral material. CD defines the absorption or transmission between the Left Hand Circularly Polarized (LHCP) and the Right Hand Circularly Polarized (RHCP) waves [START_REF] Ma | Meta-chirality: Fundamentals, construction and applications[END_REF]. As a consequence of anti-symmetry in chiral MTMs, a high coupling between the magnetic and electric fields exists in this category of MTMs.

The relationship equation between the electric and magnetic fields is described by:

D = E + jκ H, and (18)
B = µ H + jκ E, (19)
where D, E, H, B are the displacement vector, electric field, magnetic field and the magnetic flux density, respectively. The parameters , µ and κ are the permittivity, permeability and the chiral parameter, respectively. The latter defines the coupling strength between the magnetic and the electric fields. When η is equal to zero, [START_REF] Saenz | Modeling of spirals with equal dielectric, magnetic, and chiral susceptibilities[END_REF] and ( 19) have the same form as isotropic materials. In Table II, a comparison of the properties of a chiral medium and a simple isotropic medium is presented.

It is interesting to note that the intrinsic wave impedance is independent of η. Due to the existence of η, the degeneracy of the two CP waves is broken, i.e., the refractive index is increased for one CP and reduced for the other one [START_REF] Huang | Asymmetric electromagnetic wave transmission of linear polarization via polarization conversion through chiral metamaterial structures[END_REF].

There are two types of chiral MTMs, the extrinsic chiral MTM, with a non-symmetry of the 3D structure and the intrinsic chiral MTM such as the chiral helix which has intrinsic chirality for its continuous stereo structure [START_REF] Ma | Meta-chirality: Fundamentals, construction and applications[END_REF]. The latter type of chiral MTMs is widely used to achieve the

Characteristics

Isotropic Medium

Chiral Medium

Constitutive relations

D = E D = E + jκ H H = B/µ B = µ H + jκ E Wave-numbers k = ω √ µ k ± = ω[±γ + √ µ c c ] Eigenmodes Linear po- larization Circular polariza- tion Intrinsic impedance ζ = √ µ ζ c = √ µ c c
broadband conversion of polarization in the terahertz range.

In this paper, we are interested in the optimal chiral helix characterized by its equivalent magnetic, dielectric and chiral properties [START_REF] Saenz | Modeling of spirals with equal dielectric, magnetic, and chiral susceptibilities[END_REF]. The equivalence between these three properties leads to a circularly polarized wave transmitted by the optimal helix [START_REF] Saenz | Modeling of spirals with equal dielectric, magnetic, and chiral susceptibilities[END_REF]. Fig. 1 shows the structure of the optimal helix that will be studied using CMA and EEM. The design of the structure consists in a single turn PEC strip helix whose dimensions are R = 7.75 mm, h = 12 mm, 2r = 1.55 mm with a pitch angle of α = 13.65 • [START_REF] Saenz | Modeling of spirals with equal dielectric, magnetic, and chiral susceptibilities[END_REF].

IV. RESULTS

A. Modal Analysis of the Chiral MTM

The MoM solver of the commercial tool FEKO is used to design the chiral helix described in section III and calculate its impedance matrix Z. The Z-matrix is extracted and the CMs and eigenmodes are computed. For EEM, the eigen modes are sorted according to the ratio between the imaginary and real parts of the complex eigenvalues. The chosen frequency band is relatively narrow and no modal tracking issues were observed for CMA and EEM for the first two modes.

The different modal metrics of CMA and EEM are analysed and discussed showing how the properties of chiral MTMs can be highlighted using these metrics. The modal approach differs from [START_REF] Saenz | Modeling of spirals with equal dielectric, magnetic, and chiral susceptibilities[END_REF], [START_REF] Cheng | Asymmetric chiral metamaterial circular polarizer based on twisted split-ring resonator[END_REF] where reflection and transmission coefficients, either numerically or analytically determined, are used for the analysis of the chiral MTMs.

1) Modal net stored energy: The modal net energy stored e(W m -W e ) by the eigenmodes and CMs of the chiral helix are evaluated and compared. The first two modes are calculated for both modal methods assuming that only two modes are sufficient to analyze electrically small structures [START_REF] Cabedo-Fabres | The theory of characteristic modes revisited: A contribution[END_REF]. e(W m -W e ) are plotted in Fig. 2 for CMA and EEM. For modes 1 and 2, the net stored energy (normalised to the radiated power) is similar for CMA and EEM. A resonance is identified when e(W m -W e ) is zero. For both CMA and EEM, the helix resonates at 2.82 GHz. The net stored energy of mode 1 is positive before the resonant frequency and negative after the resonant frequency, showing that the energy switches from magnetic to electric at resonance. Mode 2 presents a net stored magnetic energy greater than the electric one in the whole frequency band of interest for both methods. It is found that the eigenmodes and the CMs behave similarly in terms of net stored energy.

2) Modal Significance (MS): In CMA and EEM theories, the MS is an important parameter as it states the coupling capabilities of each mode to the external source. As described in [START_REF] Ramm | Theoretical and practical aspects of singularity and eigenmode expansion methods[END_REF], the MS transforms the eigenvalues interval from [-∞,+∞] to [0, 1]. Fig. 3 shows the MS evaluated by CMA and EEM.

Only mode 1 is a resonating mode since it has MS > 0.7 [START_REF] Chen | Characteristic modes: Theory and applications in antenna engineering[END_REF] for both CMA and EEM. The resonant frequency is 2.82GHz. The MS of mode 2 and 3 is less than 0.7 in the whole frequency band. The MS of the CMs is similar to the MS of the eigenmodes for the chiral helix.

3) Modal surface current distribution: To provide a better analysis of the eigenmodes and CMs, it is essential to study the current distribution of the different modes. Fig. 4 presents the modal current of the first two modes for both methods.

For CMA, the current are real quantities, as demonstrated in section II. Therefore, the characteristic currents are equiphase. For EEM, the eigenmodes are complex and the current distribution is not equiphase (phase not shown). For both methods, only mode 1 can radiate since it is a resonating mode. Unlike mode 2, the current is asymmetric and this will cause a cancellation of the electric field E in the far field region. The other modes can hardly be excited at 2.82 GHz, since their MS is pretty low. The two methods behave similarly in terms of current distribution but they show differences in terms of magnitude (for mode 1, the maximum value is 1.1 Am -2 for CMA and 0.065 Am -2 for EEM).

4) Modal Weighting Coefficient (MWC) : In this part, the asymmetric transmission property of the chiral helix is analyzed using MWCs, the figure of merit characterizing how each mode reacts under an external excitation. The excitation is provided by a linearly-polarized plane wave propagating in the forward or backward directions at an incidence angle of 45 • The two possible configurations of polarization TE and TM are depicted in Fig. 5.

In the TE case, the electric field E is polarized along the helix axis ( x axis) whereas the magnetic field H is along the helix axis in the TM case. The excitation source is placed at ±d in the x direction to analyze the two opposite directions of propagation. Then, the MWC of the dominant mode, i.e., mode 1, is computed for the forward and backward propagation. Fig. 6. shows the MWC of mode 1 under TE and TM polarizations. It is clear from Fig. 6 that an asymmetric transmission is observed since the response of the chiral helix is different for forward and backward propagation. The difference between the two responses is very large in the TM case and much lower in the TE case. We conclude that the helix response is more affected by a magnetic excitation as the net stored energy in the near region of the helix is electric as demonstrated above.

To sum up the previous results, it has been demonstrated that the different metrics evaluated by both CMA and EEM are similar in terms of stored energy, MS and modal current distribution. Therefore chiral helices can be analyzed using either CMA or EEM. In addition, MWC is a good metric to highlight chiral properties in modal techniques.

B. Full Wave Simulation of the Chiral MTM

In this section, the properties of the chiral MTM are analysed in terms of cross polarization conversion using the scattering parameters of an array of periodically distributed chiral helices with a periodicity of 15 mm and 20 mm along the y and x axes respectively. The periodic array is investigated with the frequency domain finite-element solver of the commercial simulation tool ANSYS HFSS. Floquet-Bloch periodic boundary conditions are applied. Floquet ports are used for the excitation and an incidence angle of 45 • is applied. Only the fundamental mode is considered in each configuration. The reflection coefficients are presented Fig. 7 for the TE and TM configurations and the forward and backward propagation directions with a 45 • incidence angle. The resonant frequency is at 2.82 GHz. For the TE configuration, the reflection coefficients for the two opposite propagation directions show a slight difference of 1 dB while the difference is more significant of 4 dB for the TM configuration. This highlights that the full-wave simulations validate the asymmetric transmission of chiral helices previously demonstrated by modal analysis (MWCs).

V. DISCUSSIONS

The results presented in section IV-A-4 has shown that Modal Weighting Coefficient is good metric to demonstrate chiral properties. This has been further validated by the fullwave analysis presented in IV-B. Indeed for the chiral MTM (Fig. 1), the asymmetric transmission is slightly different for the TE forward and backward propagation. For the TM configuration, the difference on the reflection coefficients is more remarkable for the two opposite propagation directions. A good agreement between the modal analysis and the full wave simulation results is found. To provide further comparison between the two modal techniques (EEM and CMA), the surface current density on the chiral MTM is calculated. Fig. 8 shows the current given by the full wave analysis and modal approaches for mode 1 by CMA and EEM.

Mode 1 being resonant and predominant, it is the only mode shown here. The maximum values of the magnitude of the surface current density are given in Table . III. Though, from a qualitative point of view, the current distribution is identical in all approaches and from a quantitative point of view, EEM shows closer results to the full wave analysis. To conclude, the results given by CMA and EEM show similarities in terms of net stored energy, current distribution and modal significance, therefore chiral MTMs can be analyzed using CMA or EEM. Moreover, modal approaches can be used to demonstrate the asymmetric transmission of chiral MTMs.

VI. CONCLUSION

This paper described the analysis of a complex MTM, i.e. a chiral MTM inclusion based on a spiral helix using two modal analyses, CMA and EEM. The chiral helix with a single turn is characterized by an intrinsic chirality, i.e., a CP wave transmission at normal incidence. The two methods showed similarities in terms of resonant frequency, modal significance, net stored energies and surface current density distribution. Similar current distributions were observed for both modal methods and the full-wave analysis one. However, current values (maximum of current at resonance) are much closer to the direct analysis for EEM.

To demonstrate that chiral MTMs exhibit an asymmetric transmission for linear polarization, the MWCs were evaluated for TE and TM configurations of forward and backward propagation directions at an incidence angle of 45 • . Different MWCs were observed for the two propagation directions which was validated and confirmed using the full wave simulation.

The effect of the chiral MTM helix on the field polarization can be exploited for the design of circularly polarized MTMinspired antennas. The use of modal approaches and more specifically EEM should prove to be useful to take into account the coupling between the chiral MTMs and the antenna.

ACKNOWLEDGMENT

The authors acknowledge funding from I-Site FUTURE in the framework of the Western project. One of the authors acknowledge partial funding by the regional project SMARTIES in the framework of the ELSAT 2020 program co-financed by the European Union with the European Regional development fund, the French state and Hauts de France Regional council. to the design of antennas for modern applications," IEEE Antennas Propagat. Mag., vol. 49, no. 5, pp. 52-68, 2007.

Fig. 1 .

 1 Fig. 1. The chiral MTM inclusion.

Fig. 2 .

 2 Fig. 2. Real-part of the net stored energy against frequency for the modes 1 and 2 computed by CMA and EEM.

Fig. 3 .

 3 Fig. 3. Modal significance of the first three modes using CMA and EEM against frequency.

Fig. 4 .

 4 Fig. 4. Magnitude of the surface Current for the first two modes for CMA and EEM at 2.8 GHz (isometric view) (a) Current distribution of mode 1 by CMA with maximum of 1.1 Am -2 (b) Current distribution of mode 2 by CMA with maximum of 1.05 Am -2 (c) Current distribution of mode 1 by EEM with maximum of 0.065 Am -2 (d) Current distribution of mode 2 by EEM with maximum of 0.063 Am -2 .

Fig. 5 .

 5 Fig. 5. TE and TM polarization with an incidence angle 45 • .

Fig. 6 .

 6 Fig. 6. Modal Weighting coefficient of Mode 1 under TE and TM with an incidence angle 45 • . Inset depicts a projection of the helix in the xy plane.

Fig. 7 .

 7 Fig. 7. Reflection coefficient of the chiral helix for the TE and TM polarization with an incidence angle of 45 • for different propagation directions.

Fig. 8 .

 8 Fig. 8. (a) Magnitude of the surface current density of mode 1 at 2.82GHz by CMA (b) Magnitude of the surface current density of mode 1 at 2.82GHz using EEM (c) Magnitude of the total current density evaluated by full-wave analysis at 2.82 GHz (isometric view).

TABLE I COMPARISON

 I OF PROPERTIES BETWEEN CMA AND EEM.

	CMA	EEM
	Based on the gen-	Based	on	the
	eralized eigenvalues X( I n cha (r, ω)) = λ cha n R( I n cha (r, ω))	standard eigenvalues Z( I n eem (r, ω)) = Υ eem n I n eem
	Approximate	Absolute approach
	approach
	Easy to manipulate	Difficult to manipu-
	(Real quantities)	late (Complex quan-
		tities)
	The stored and the
	net stored energies
	are equal and real
	quantities (real cur-
	rents)

TABLE II COMPARISON

 II OF PROPERTIES BETWEEN ISOTROPIC AND CHIRAL MEDIUM.

TABLE III COMPARISON

 III BETWEEN THE MAXIMUM VALUES OF THE SURFACE CURRENT DENSITY COMPUTED BY FULL-WAVE ANALYSIS, CMA AND EEM.

	Full-wave analy-	CMA (Mode 1)	EEM (Mode 1)
	sis
	0.0721 Am -2	1.1027 Am -2	0.0662 Am -2


Narendra Jussien
email: narendra.jussien@emn.fr

Olivier Lhomme
email: olhomme@ilog.fr

Local search with constraint propagation and conflict-based heuristics

In this paper, we introduce a new solving algorithm for Constraint Satisfaction Problems (CSP). It performs an overall local search helped with a domain filtering technique to prune the search space. Conflicts detected during filtering are used to guide the search. First experiments with a tabu version of the algorithm have shown good results on hard instances of open shop scheduling problems. It competes well with the best highly specialized algorithms.

Introduction

Many industrial and engineering problems can be modeled as constraint satisfaction problems (CSP). A CSP is defined as a set of variables each with an associated domain of possible values and a set of constraints over those variables.

Most of constraint solving algorithms are built upon backtracking mechanisms. Those algorithms usually explore the search space systematically, and thus guarantee to find a solution if one exists. Backtracking-based search algorithms are usually improved by using some relaxation techniques (usually called filtering techniques in the CSP world) which aim at pruning the search space in order to decrease the overall duration of the search.

Another series of constraint solving algorithms are local search based algorithms (eg. min-conflict [START_REF] Minton | Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems[END_REF], GSAT [START_REF] Selman | A new method for solving hard satisfiability problems[END_REF], tabu search [START_REF] Glover | Modern heuristic Techniques for Combinatorial Problems, chapter Tabu Search[END_REF]). They perform a probabilistic exploration of the search space and therefore cannot guarantee to find a solution, but may be far more efficient (wrt reponse time) than systematic ones to find a solution.

Several works have studied cooperation between local and systematic search [START_REF] Yokoo | Weak-commitment search for solving constraint satisfaction problems[END_REF][START_REF] Pesant | A view of local search in constraint programming[END_REF][START_REF] David | A constraint-based approach for examination timetabling using local repair techniques[END_REF][START_REF] Schaerf | Combining local search and look-ahead for scheduling and constraint satisfaction problems[END_REF][START_REF] Gervet | Large combinatorial optimization problem methodology for hybrid models and solutions[END_REF][START_REF] Richards | Non-systematic search and learning: An empirical study[END_REF]. Those hybrid approaches have led to good results on large scale problems. Three categories of hybrid approaches can be found in the literature:

1. performing a local search before or after a systematic search;

2. performing a systematic search improved with a local search at some points of the search (typically for optimisation problems, to try to improve the quality of a solution);

3. performing an overall local search, and using systematic search either to select a candidate neighbor or to prune the search space.

The hybrid approach presented in this paper falls in the third category. It uses filtering techniques to both prune the search space and help in choosing the neighbor in a local search. This leads to a generic search technique over CSP which is called path-repair. An implementation of path-repair which merges a tabu search together with a filtering technique and conflict-based heuristics to guide the search is described in this paper. That implementation has been used to solve open shop scheduling problems. It has given very good results on hard instances well competing with the best highly specialized algorithms. This was quite surprising since, unlike those specialized algorithms, our implementation is general and does not need any tuning of complex parameters.

The paper is organized as follows. The following section presents the notation used. Next we introduce the pathrepair algorithm. Then related works are discussed. Finally first results obtained in the field of open shop scheduling problems are presented.

Preliminaries

A CSP is a pair < V C > where V is a set of variables and C = fc 1 : : : c m g a set of constraints. The domains of the variables are handled as unary constraints.

For a given constraints set S = fc 1 : : : c k g, Ŝ will be the logical conjunction of the constraints in S: Ŝ = ( c 1 : : : ^ck ). By convention: ? = true.

Classical CSP solving simultaneously involves a filtering algorithm, to a priori prune the search tree, and an enumeration mechanism, to overcome the incompleteness of that filtering algorithm. For example, for binary CSP over finite domains, arc-consistency can be used as filtering technique. After a filtering step, three situations may arise:

1. the domain of a variable becomes empty: there is no feasible solution;

2. all the domains are reduced to a singleton: those values assigned to their respective variables provide a feasible solution for the considered problem;

3. there exists at least one domain which contains two values or more: the search has not yet been successful. In a classical approach, it would be time for enumeration through a backtracking-based mechanism.

In a more general way, a filtering algorithm applied on a set C of constraints returns a new set C 0 = ( C) such that C C 0 (Note that we consider domain reductions as ad- dition of redundant constraints). Moreover, for any filtering algorithm applied on the set C of constraints of a given CSP, there exists a function obviousInference which, when applied on C 0 = ( C), answers:

noSolution iff it is immediate to infer that no solution can be find for C 0 (as in situation 1 above).

solution iff the current constraint system can immediately provide a solution that verifies all the constraints in C 0 (as in situation 2 above).

flounder in all other situations (as in situation 3 above).

The function obviousInference has typically a low computational cost. Its aim is to make explicit the use of some properties that depends on the filtering algorithm that is used. The example of arc-consistency filtering with an empty domain or with only singleton domains has already been given, but a function obviousInference can be made explicit in many other filtering or pruning algorithms. For example, in integer linear programming, the aim is to find an optimal integer solution. This can be done by using the simplex algorithm over the reals. If there is no real solution or if the real optimum has only integer values, then an obviousInference function would respectively return noSolution or solution.

Enumerating discrete binary CSP is assigning a value a to a variable v i.e. adding a new constraint v = a. For other kinds of problems, enumerating may be different: for example, when dealing with scheduling problems, enumerating is often adding a precedence constraint between two tasks of the problem. We will call those constraints decision constraints.

In the next section, the path-repair algorithm is presented through an abstraction of the solved problems: they may be discrete binary CSP, numeric CSP as well as scheduling problems. This will be possible thanks to:

1. the parameter which represents the filtering algorithm used;

2. the function obviousInference, tightly related to the used filtering algorithm, that is able to examine a set of constraints in order to continue the computation or not;

3. the concept of decision constraint.

The path-repair algorithm

The idea of the path-repair algorithm is very simple. First observe that:

procedure path-repair(C)

(1) begin

(2)

repeat (3) if conditions of failure verified then (4) return failure (5) else (6) C 0 (C CP ) (7) switch obviousInference(C') (8)
case noSolution :

(9)
k nogood explaining the failure (10) P neighbor(P ,k,;)

case solution :

(12)

return C 0 (13) default :

(

P extend(P ,;) The ability of backtracking-based search algorithms to be combined with filtering techniques only comes from the fact that they work upon a partial instantiation of the variables. Thus, a local search algorithm working upon a partial instantiation of the variables would have the same ability. Indeed, the path-repair algorithm is such an algorithm. The considered partial instantiation is defined by a set of decision constraints (as described above) on the variables of the problem. Such a constraint set defines a path in the search tree.

(15) endswitch (16) endif (17) until false (18)end

Principles of path-repair

The principles of the path-repair algorithm as shown in figure 1 are the following: let P be a path in the search tree. At each node of that path, a decision constraint has been added. Let C P be the set of added decision constraints while moving along P.

The path-repair algorithm starts with an initial path (it may range from the empty path to a path that defines a complete assignment). The main loop first checks the conditions of failure1 . A filtering algorithm is then applied on

C C P giving a new set of constraints C 0 = ( C C P ).
The function obviousInference is then called over C 0 . Three cases may occur: obviousInference(C 0 ) = solution: a solution has been found. The algorithm terminates and returns C 0 . obviousInference(C 0 ) = flounder: the path- repair algorithm tries to extend the current path P by adding a decision constraint. That behavior is similar to that of backtracking-based search algorithms. For that purpose, a function extend(P ,;) is assumed to exists that chooses a decision constraint to be added and adds it to P . Parameter ; can be used to store a context that varies according to the chosen version of the algorithm. Its meaning will be made clear later.

obviousInference(C 0 ) = noSolution: C C P is inconsistent. We will say that P is a dead-end, or P is inconsistent: P cannot be extended. The path-repair algorithm will thus try to repair the current path by choosing a new path through the function neighbor(P ,k,;). Parameter k as ; will be explained later.

The path-repair algorithm appears here as a search method that handles partial instantiations and uses filtering techniques to prune the search space. The key components of this algorithm are the neighboring computation functions (neighbor) and the extension functions (extend).

Nogoods in path-repair

In a local search algorithm such as GSAT (on boolean CSP), an inconsistent instantiation is replaced by a new one built by negating the value of one of its variables. That variable is heuristically chosen (eg. selecting the one whose negation will allow the greatest number of clauses to become satisfied). More generally, a local search algorithm uses complete instantiations (called states) and replaces an inconsistent state with another state chosen among its neighbors.

The path-repair algorithm works in the same way except that it uses partial instantiations (paths): as soon as a path becomes inconsistent, one of its neighbors needs to be chosen. A path (partial instantiation) synthetizes all the included complete instantiations. Switching paths is like setting aside many irrelevant complete instantiations in one movement.

Like any local search algorithm, path-repair may use a heuristic way to select an interesting neighbor. It seems to be a good idea to select a neighboring path P 0 which does not have the drawbacks of the current path P (recall that in path-repair, neighbors of path P are computed iff P is inconsistent). Ideally, we would like to get to a consistent neighbor P 0 i.e. such that obviousInference( (C C 0 P 0 )) = solution. However, that is equivalent to solve the whole problem.

Instead, we may try to get to a partially consistent neighbor P 0 i.e. such that obviousInference( (C C 0 P 0 ))6 = noSolution. Unfortunately, the only way to get there (without using computing resources) is to get back to an already explored node but, doing so, we would achieve a kind of backtracking mechanism, what is not wanted in the path-repair algorithm.

Nevertheless, what can be done is to avoid the neighbors that can already be known as inconsistent. Such an information can be extracted from an inconsistent path P . Indeed, inconsistency means that Ĉ ^Ĉ P =) false. It is possible to compute a subset of C P that is alone inconsistent with C. Such a subset is called a conflict set or nogood.

Definition 1 (Nogood) A nogood k for a set of constraints C and a path P, is a set of constraints such that: k C P and Ĉ ^k =) false. Now, we can define a neighbor P 0 of a path P according to a single nogood k. As long as constraints in the computed nogood k remain altogether in a given path P 0 , that path will remain inconsistent. Therefore, in order to get a path with some hope to be consistent, we need to remove from the current path P at least one of the constraints in k.

Indeed, a more precise neighborhood can be computed.

Let c 2 k be a constraint to be removed from C P . As long as all the constraints in k n c remain in the active path, c will never be satisfiable. Thus, the negation of c can be added in the new path. A neighbor of a path P according to a nogood k is thus defined as follows: Definition 2 (Neighbor wrt one nogood) Let k be a nogood for a path P, a neighbor P 0 of P wrt k verifies 9c 2 k C P 0 = C P n c f : cg

Computing nogoods Note that if the current path P is inconsistent, C P is a valid nogood. Obviously, a strict subset will be much more interesting and will give a more precise neighborhood. A minimal (for the inclusion) nogood would be the best, but could be expensive to compute [START_REF] Verfaillie | Problèmes incohérents: expliquer l'incohérence, restaurer la cohérence[END_REF]. The current implementation does not try to find such a minimal nogood. Instead, it tries to find a good nogood in a fast way. Nogoods are provided by the filtering algorithm as soon as it can prove that no solution exists in the subsequent complete paths derived from the current partial path. In filtering based constraint solving algorithms, a contradiction is raised as soon as the domain of a variable v becomes empty. Suppose that, for each value (or set of values) a i removed from the domain of v, a set of decision constraints k i C P is given (k i is called a removal explanation for a i ) and is such that: Ĉ ^k i =) v 6 = a i . If so, k = S i k i is a nogood since no value for v is allowed by the union of the k i . Therefore, in order to compute nogoods, it is sufficient to be able to compute an explanation for each value (or set of values) removal from the domain of the failing variable.

Value removals are direct consequences of the filtering algorithms. Therefore, value removal explanations can be easily computed by using a trace mechanism embedded within the filtering algorithm and memorizing the reason why a removal is done (eg. see [START_REF] Jussien | Dynamic domain splitting for numeric csp[END_REF]).

For example, let us consider two variables v 1 and v 2 whose domains are both f1 2 3g. Let c 1 be the constraint: v 1 3 and let c 2 be the constraint: v 2 v 1 . Let us assume that the used filtering algorithm is arc-consistency filtering.

The constraint c 1 explains the fact that f1 2g should be removed from v 1 . Afterwards, c 2 leads to remove f1 2g from v 2 . An explanation of the removal of f1 2g from v 2 will be: c 1 ^c2 because c 2 makes that removal only because previous removals occured in v 1 due to c 1 .

Tabu path-repair

In a local search algorithm, the neighbor selection is very important. Many heuristics may be used. That is also the function neighbor(P , k, ;) % precondition: k CP , P covers ;

(1) begin (2)

add k to the list of nogoods ;

(3) The tabu version of path-repair uses a tabu list of a given size s. The s last computed nogoods are kept in a list ;. The following invariant is maintained by the algorithm: the current path P covers all the nogoods in ;, ie does not completely contain any of the nogoods in ;.

We have defined so far a neighbor wrt one single nogood, so we have to extend the definition when facing multiple nogoods.

Definition 3 (Neighbor wrt several nogoods) A valid neighbor is defined as a path that covers all the nogoods in ;.

In other words, at least one constraint in each nogood of ;

is not (or is negated) in the new neighbor. To compute such a neighbor in a reasonable time, a greedy algorithm can be used.

Figure 2 shows an implementation of the neighbor function for tabu path-repair that has been used for solving scheduling problems.

The neighbor function has to record in ; the new nogood k found by the filtering algorithm and to maintain the invariant. It tries to find one constraint in k such that negating this constraint makes the path cover all the nogoods. An integer (weight) is associated with each constraint counting the number of times that the constraint has appeared in any nogood. The neighbor function chooses to negate the constraint with the greatest weight that, when negated, makes the new path cover all the nogoods in ;. If such a constraint does not exist, the neighborhood can be extended. For example, we may try to negate two constraints. In our implementation for open shop problems (see last section), this case is handled as a stopping criterion, so there is no need for any neighborhood extension.

Note that, in the same way, the function extend(P ,;) has to use ; in order to extend the partially consistent current path while maintaining the invariant. A heuristically ordered list of constraints which performs an extension of the current path is dynamically generated and the first constraint that covers all the nogoods in ; is chosen.

As for now, our algorithm seems to need to call the filtering algorithm many times with little changes to handle in the constraint set. Of course, it would not be very efficient to each time recompute for example the arc-consistency closure from scratch. That problem has been adressed for dynamic CSP. The algorithms used in path-repair are similar to those of [START_REF] Bessière | Arc consistency in dynamic constraint satisfaction problems[END_REF][START_REF] Debruyne | Arc-consistency in dynamic CSPs is no more prohibitive[END_REF] or other works [START_REF] Jussien | Dynamic domain splitting for numeric csp[END_REF].

Related works

The path-repair algorithm takes its roots in many other works, among which [START_REF] Ginsberg | Gsat and dynamic backtracking[END_REF] has probably been the most influential by highlighting the relationships between local search and systematic search, and by the use of nogoods to guide the search and make it systematic. In the same spirit are [START_REF] Ginsberg | Dynamic backtracking[END_REF], [START_REF] Frost | Dead-end driven learning[END_REF], (Schiex & Verfaillie 1994) and [START_REF] Bliek | Generalizing partial order and dynamic backtracking[END_REF].

Two algorithms have been designed that have similarities with the path-repair algorithm:

The algorithm proposed in [START_REF] Schaerf | Combining local search and look-ahead for scheduling and constraint satisfaction problems[END_REF]) can be seen as an instance of the path-repair algorithm where: the decision contraints are instantiations; there is no propagation and no pruning (the filtering algorithm only consists in checking if the constraints containing only instantiated variables are not violated) and it does not make use of nogoods neither in the the neighbor function nor in the extend function. The common idea, which already exists in previous works [START_REF] Jackson | Introduction to Expert Systems[END_REF], is essentially to extend a partial instantiation when it is consistent, and to perform a local change when the partial solution appears to be a dead-end.

The idea to use a filtering algorithm during the running of a local search has been also used in [START_REF] Stuckey | Extending GENET with lazy arc consistency[END_REF], where an extension to GENET, a local search method based on an artificial neural network aiming at solving binary CSP, is introduced. This extension achieves what is called "lazy arc-consistency" during the search. The lazy arc-consistency filtering performs a filtering over the initial domains. The result is at most the one obtained by filtering the domains before any search. In path repair, the filtering is applied over the current domains at every step.

The heuristic we used to select the decision constraint to negate -choose the one that has appeared the greatest number of times in a nogood -is an adaptation of a similar approach for GSAT counting the number of times that a constraint has not been verified [START_REF] Selman | Domain-independent extensions to gsat: Solving large structured satisfiability problems[END_REF].

The way nogoods are computed by the filtering algorithm is a well-known technique that has already been used with slight variations for different combinations of filtering algorithms with systematic search algorithms (forward checking + intelligent backtracking [START_REF] Prosser | Hybrid algorithms for the constraint satisfaction problem[END_REF], forward checking + dynamic backtracking (Verfaillie & Schiex 1994), arcconsistency + intelligent backtracking [START_REF] Codognet | A metalevel compiler of CLP(FD) and its combination with intelligent backtracking[END_REF], arc-consistency + dynamic backtracking [START_REF] Jussien | Relaxation de Contraintes pour les problèmes dynamiques[END_REF]), 2B-consistency + dynamic backtracking [START_REF] Jussien | Dynamic domain splitting for numeric csp[END_REF]. Nevertheless, as far as we know, the tabu version of path-repair is the first time such a technique is used in combination with a local search algorithm.

Solving scheduling problems

Classical scheduling shop problems for which a set J of n jobs consisting each in m tasks (operations) must be scheduled on a set M of m machines can be considered as CSP upon intervals 2 . One of those problems is called the Open Shop problem [START_REF] Gonzales | Open-shop scheduling to minimize finish time[END_REF]. For that problem, operations for a given job may be sequenced as wanted but only one at a time. We will consider here the building of non preemptive schedules of minimal makespan 3 . That problem is NP-hard as soon as min(n m) 3.

Constraints on resources (machines and jobs) are propagated thanks to immediate selections from [START_REF] Carlier | Adjustment of heads and tails for the job-shop problem[END_REF]. The consistency level achieved by that technique does not ensure the computation of a feasible solution. An enumeration step is therefore needed. For shop problems, enumeration is classically performed on the relative order on which tasks are scheduled on the resources. When every possible precedence has been posted, setting the starting date of the variable to their smallest value provides a feasible solution. Such a precedence constraint is therefore a decision constraint as described above.

One of the best systematic search algorithms developed for the Open Shop problem is the branch and bound algorithm presented in [START_REF] Brucker | A branch and bound algorithm for the open-shop problem[END_REF]. It consists in adding precedence constraints along the critical path of a heuristic solution in each node. As far as we know, although this is one of the best methods ever, some problems of size 7 7 remain unsolved.

We tested a tabu version of path-repair. That version is fully systematic due to the used heuristics. Table 1 presents the results obtained on a series of 30 problems from [START_REF] Taillard | Benchmarks for basic scheduling problems[END_REF]. In order to put in perspective our results, we recall results presented in [START_REF] Alcaide | A tabu search algorithm for the open shop problem[END_REF] and [START_REF] Liaw | A tabu search algorithm for the open shop scheduling problem[END_REF]. Those papers present tabu searches specifically developed for the Open Shop problem. Those methods both use carefully chosen complex parameter values. Results presented in table 1 show that our simple approach which merely applies principles presented in this paper already gives very good results. More precisely, the time required to solve those problems is similar to those reported by [START_REF] Alcaide | A tabu search algorithm for the open shop problem[END_REF] and [START_REF] Liaw | A tabu search algorithm for the open shop scheduling problem[END_REF]). Moreover, for the problems of size 4 4, the obtained results are the same as those of [START_REF] Liaw | A tabu search algorithm for the open shop scheduling problem[END_REF]; for 5 5 problems, if our algorithm gives bad results, they are not very far from the results of [START_REF] Liaw | A tabu search algorithm for the open shop scheduling problem[END_REF] but it often gives the same results and even a better one for the 5x5-3 problem; for 7 7 problems, our algorithms gives the same results as the best of the two others except for four problems among which three 2 Variables are the starting date of the tasks. Bounds thus represent the least feasible starting time and the least feasible ending time of the associated task.

3 Ending time of the last task. Taillard's problems are optimization problems. This requires a main loop that calls the function path-repair until improvement is no longer possible (see figure 3). Improvements are generated by adding a constraint that specifies that the makespan is less than the current best solution found. The initial path for each call of the function pathrepair is the latest path (which describes the last solution found).

Conclusion and future works

In this paper, we introduced a new solving algorithm for CSP: the path-repair algorithm. The two main points of that algorithm are: it makes use of a repair algorithm (local search) as a basis and it works on a partial instantiation in order to be able to use filtering techniques. The most useful tool to implement that algorithm was the use of nogoods: nogoods allow relevant neighborhoods to be considered and nogoods can be used to derive efficient neighbor selecting heuristics for a path-repair algorithm.

First experiments with a tabu version of path-repair has shown good results over open shops scheduling problems. It competes well with the best highly specialized algorithms. This was quite surprising since, unlike those specialized algorithms, our implementation is general and does not need any tuning of complex parameters. Experiments over other problems are currently being done.

Figure 1 :

 1 Figure 1: The path-repair algorithm

Figure 2 :

 2 Figure 2: The neighbor function for tabu pathrepair

Figure 3 :

 3 Figure 3: Algorithm used to solve Taillard's problems

These conditions depend on the instance of the algorithm; examples are given in the following sections.

Acknowledgements

We would like to thank Christian Bliek for his useful suggestions.