P Benigni

A Berche

G Mikaelian

J Rogez

Transformation of a Double Focusing B-E Mass Spectrometer for Multiple-Cell Knudsen Effusion -Part I: Scientific Concepts

Knudsen Effusion Mass Spectrometry (KEMS) is a powerful method in the field of experimental thermodynamics at high temperatures. Since 2005, the long term project of transforming and upgrading a double-focusing VG Micromass 54-38K mass spectrometer for multiple-cell effusion has started at the IM2NP in Marseille/France. The scientific concepts underlying the transformation are presented in this first paper. The molecular beam effusing from the Knudsen cells must be sampled under restricted collimation conditions. The resulting geometric constraints are taken into account in the design of the large main vacuum chamber necessary to house a multiple-cell effusion furnace. Decrease of the molecular transmission between the cell and the ionization source needs to be counterbalanced by an increase in the sensitivity of the ionization source. Other modifications of the instrument are reviewed. The first tests and results will be the subject of a second paper to be published.

Overview of the project

The mass spectrometer, given to us by J. Drowart after he retired from the Université Libre de Bruxelles, is a double focusing 54-38K model manufactured by VG micromass. The analyzer has a B-E geometry in which a magnetic sector, with a radius of 27 cm and 95°, precedes an electrostatic sector of 38.1 cm (15") radius, 81.5°. The ionizer is an electron impact source. The spectrometer is not equipped with any effusion device.

The project is to adapt this spectrometer for activity measurements up to 2500 K by the multiple-cell technique according to the concepts developed by C. Chatillon and his coworkers (1,2,3) at the CNRS-SIMAP laboratory in Grenoble, France.

Concretely, it implies that the molecular beams effusing from the Knudsen cells must be sampled under restricted collimation conditions. The resulting geometric constraints are taken into account in the design of the large main vacuum chamber necessary to house a four-cell effusion furnace. Moreover, decrease in the molecular transmission between the cell and the ionization source needs to be counterbalanced by an increase in the sensitivity of the ionization source.

The ion optics between the entrance and the exit slits of the analyzer is not modified.

Interest of a high resolution instrument

Quadrupole and single focusing magnetic sector are the mass analyzers which are the most frequently used in Knudsen Effusion Mass Spectrometry (KEMS) [START_REF] Hilpert | Structure & Bonding, Noble Gas and High Temperature Chemistry[END_REF][START_REF] Komarek | [END_REF]. Double focusing instruments, allowing high resolution, have been seldom used (6,7).

For a given peak at mass M having a peak width M, the resolution R is defined according to equation 1 [START_REF] Roboz | Introduction to mass spectrometry: Instrumentation and Techniques[END_REF]:

M M R   [1]
There are different ways of defining M [START_REF] Roboz | Introduction to mass spectrometry: Instrumentation and Techniques[END_REF] and it is interesting to look at these alternatives before comparing the ability of different instruments to separate masses.

For an isolated peak, M is the peak width at a certain percentage X, frequently 5, 10 or 50%, of the height of the peak (figure 1a).

For two adjacent overlapping peaks, the peak width cannot be defined unambiguously below the level of the valley hence M is generally defined in relation to the valley level Y%, frequently at 2 or 10% (figure 1b). In the cross talk definition (figure 1c), M is based on the intensity Z% with which one peak contributes to the intensity of the other at its highest value.

If we assume a linear intensity scale on the vertical axis, the qualitative figure 1c is quite misleading because the summation of the two dotted lines will not give a marked valley between the two peaks. For Gaussian peaks of equal height unit resolutions are compared for a 10% valley definition and a 5% cross-talk definition in the quantitative figures 2a and 2b. In figure2a, the summation of the peaks intersecting at 5% forms a 10% valley. The peaks are clearly not separated in figure 2b so it is pointed out that when comparing numerical values for assessing the ability of a given spectrometer to perform quantitative analysis the %valley definition is recommended. Another case of overlapping peaks, is the one in which a main peak contributes to the height of a side peak (figure 3). If the main peak is from a residual background species and the side peak is from an effusing species, the actual intensity of the peak of the effusing species can be obtained by the difference between measurements performed with and without shuttering the molecular beam. If both peaks are from effusing species a shutter has no effect and the shape of the peaks has to be known for quantitative analysis. Real performance of commercial instruments is difficult to assess on the sole basis of manufacturer figures. Moreover while quadrupole manufacturers use peak width definitions at various heights 5%, 10% or 50%, magnetic sectors manufacturers generally refer to the 10% valley definition. Typically, the order of magnitude of the 10% valley resolution is around several hundreds for quadrupoles, up to 3000 for single focusing magnetic sectors, and greater than several thousands for double focusing instruments up to 100000.

M

The mass of the gaseous species in high temperature inorganic chemistry is generally lower than 500 amu. The resolution of quadrupoles is suitable for quantitative analysis of masses lower than 50 amu. In the range 100-500 amu, qualitative identification of species remains possible but adjacent peaks will not be fully separated and the most intense peaks will significantly contribute to the intensity of neighboring peaks [START_REF] Ronchi | [END_REF].

As mentioned by Roboz (8) "resolution requirements fall broadly into two classes". To differentiate between adjacent peaks differing by 1 amu, a low or medium resolution is required. For example, mechanical pump oil, DC 705 diffusion pump oil and turbo-molecular pump oil all give an important hydro-carbon peak at mass 43. Acetone and ethanol frequently used in preparing vacuum parts have their main peak at masses 43 and 45 respectively. This is the reason why residual gas analyzers have a resolution in the range 50-80, sufficient to distinguish 12 Considerably higher resolution is required for doublet resolution, for example within the framework of studies involving light elements like Si, C, O, gaseous species like Si + , SiO + , CO + will have to be separated from each other and also from background species such as N 2 + . A resolution of 1550 is required to separate 12 C 16 O + from 28 Si + and of 2500 to separate 12 C 16 O + from 14 N 2 + . In this complex case, a double focusing instrument will always provide a sufficiently high resolution for full separation of all the masses, allowing accurate quantitative analysis.

Single vs. multiple-cell effusion

With a single effusion cell, the partial pressure p i of the gaseous species i in the cell is linked to the ionic intensity I + i according to equation 2 (10), where S i is the sensitivity factor of the spectrometer to the species i, and T the temperature of the cell.

T I S p i i i   [2]
As S i is not a priori known, successive runs are necessary for the experiment(s) then for calibrating the sensitivity factor towards a reference sample. However, S i may vary between successive runs because of default of reproducibility a) in the mechanical positioning of the cell, impacting the efficiency of molecular beam sampling, and b) in the stability of the ionization parameters of the ion source.

Several methods have been employed to overcome these drawbacks (11) like the estimation of S i using a known internal equilibrium when possible (e.g. monomer/dimer method), manipulation of the Gibbs-Duhem relation to cancel the calibration constant, or addition of an isolation valve to keep the source running when a sample is changed.

An alternative method is the multiple-cell effusion technique following the example of Chatillon and its coworkers with a 4-cell device (1, 2, 3).

The advantages are that, as a permanent standard is always available in one cell, and because the effusion device is carefully designed to obtain the same S i and T for all cells, then in a single run the activity a i is directly obtained from the ratio of ionic intensities I + i above an alloy and I°+ i above the reference sample (equation 3) with no need to measure S i .

      i i i i i I I p p a [3]
For absolute pressure determination, S i is obtained from the measurements of T and I°+ i and the prior knowledge of p°i.

In chemical systems where evaporation coefficients are low, various dimensions and shape of the effusion orifice can be simultaneous used to estimate the equilibrium pressure. Also several chemical compositions can be studied in a single run, reducing the overall duration of the experiments.

The price to pay for these increased abilities is that part of the spectrometer has to be rebuilt because, in general, vacuum chambers are not large enough to house a multiplecell effusion furnace. It is worth noting that isothermicity of the multiple-cell holder is harder to achieve and can be an issue at temperatures lower than 1100°C. Practically, the diameter of the furnace chamber has to be increased to a minimum value of 160 mm with a corresponding increase in the pumping capacities because of the higher steady flow of molecules effusing from the 4-cell device. Moreover, a special furnace positioning mechanism is required for switching the cells. As no instrument of this type is available on a commercial basis, the system has to be homemade in the laboratory.

Conventional beam sampling vs. restricted collimation

In conventional molecular beam sampling, there is a high transmission of molecules between the effusion cell and the ion source but the molecular flow entering the source is the sum of three contributions (figure 4). In addition to the direct flow from the cell (a), which is the only contribution of interest, two parasitic flows also enter the source: the flow of molecules re-vaporizing from the shields (b) and the flow of molecules vaporizing after creeping and surface diffusion along the wall of the effusion orifice (c). In this configuration, the ionic intensity of a given species entering the source continuously evolves as a function of a position coordinate and even a slight shift e.g. 50 µm of the cell modifies the ionic intensity (1). Due to the asymmetric nature of a single filament source, it is sometimes observed that the maximum intensity is offcentered and corresponds to the situation where the molecular beam gets closer to the electron entry slit in the source box (1).

Under restricted collimation (2) (figure 5), a fixed field aperture of diameter D 1 is added between the source and the effusion cell which, together with the source aperture of diameter D 2 , fully defines the molecular beam. D 1 and D 2 values are chosen to restrict the width of the molecular beam to molecules coming from the inner volume of the cell.

L = H 2 -H 1

Effusing sample

Electron beam By this way parasitic flows are suppressed and, around the collimation axis, the width of the molecular beam becomes independent of the cell position and the ionic intensity is not modified by a slight shift or tilt of the cell when sighting inside the effusion orifice.

H 1 Cell orifice D e
The study of CsOH vaporization by Roki et al. (12) gives a clear demonstration of the interest of restricted collimation. During the single cell effusion experiments between 570 and 770 K a flow out of the sample is observed around the effusion orifice. The total mass loss, which is used to calibrate the spectrometer, is the sum of the genuine effusion process from the inner volume of the cell and of a parasitic contribution from molecules vaporizing after radial diffusion around the effusion orifice. Using restricted collimation in conjunction with a high accuracy positioning system, these flows are separately measured. The authors have been able to show that the parasitic contribution, which represents 53% of the genuine effusion process at 563K, decreases to 25% at 676K because the vaporization process becomes predominant compared to surface diffusion as the temperature rises.

However, when restricted collimation is used, the proportion of effusing molecules reaching the source is diminished and an optimization of the geometric parameters, the diameters of the orifices and the distances between them, is required to maximize molecular transmission between the cell and the ion source.

Transmission maximization under restricted collimation

As shown by Morland et al. (2), the value of the field aperture for maximum transmission is a function of the other geometric parameters according to equation 4:

2 1 2 2 1 2 1 ) ( H H D H H H D D p    [4]
Practically, the source aperture diameter D 2 is allowed to vary between 2.5 and 4.5 mm. The cell orifice has a diameter D e in the range 0.5 to 3 mm and the external diameter of the penumbra zone D p is defined from D e taking into account a convenient mechanical clearance  of 0.1 mm larger than the positioning accuracy of the effusion cells. H 1 , the distance between the effusion and field apertures, has to be minimized for maximum transmission. Concretely, H 1 is greater than 14 mm because thermal shields have to be inserted between the cell and the water jacket supporting the field aperture. The last distance L = H 2 -H 1 , where H 2 is the distance between the effusion orifice and the source aperture, is fixed in an existing experimental device, must be optimized in the design of a new one.

Transmission calculations are required and the formula for molecular transmission between 2 coaxial disks is given in the appendix.

The procedure for source aperture optimization with fixed L is illustrated by figure 6. For each D 2 value in the range 0 to 7 mm, a corresponding field diameter D 1 value is calculated according to the restricted collimation relation (equation 4 and dashed line, figure 6). The Equivalent Transmission Surface (ETS defined in the appendix) between the field and source apertures is calculated for each pair of diameters D 1 and D 2 and also plotted versus the source aperture diameter D 2 (solid line, figure 6). The ETS curve has a bell shape with a transmission maximum at D 2 = 3.2 mm. The corresponding D 1 value is read in figure 6 as indicated by the horizontal dotted arrow and is 0.7 mm. At the maximum, Morland et al. (2) have shown that the flow entering the source under restricted collimation is only a fourth of the flow which would enter the source under conventional sampling (i.e. the flow transmitted between two coaxial orifices of diameters D p and D 2 separated by the distance H 2 ). Figure 7 illustrates the procedure for L optimization. It is important to keep in mind that L is defined during the design of the Knudsen cell and source vacuum chamber and cannot be modified afterwards. The set of values of the geometric parameters is identical to figure 6, except that the ETS curve is calculated for L = 50, 70 and 82 mm. Figure 7 shows that first, the maximum ETS increases with L and second that the maximum shifts towards higher D 2 values. The practical implication is that the distance between the field and the source apertures can be increased without decreasing the transmission. However as the volume of the ion source is finite, D 2 has an upper bound (4.5 mm in our case) and there is also an upper bound for L. We have chosen a quite large value of L = 82 mm, because of the large diameter of our vacuum chamber, 200 mm, and of the fact that we wanted to have an access below the ion source from the front flange to simplify the source mounting and dismounting operations.

Ion source optimization

The original VG electron impact source has an orthogonal cross beam geometry (figure 8). The electrons emitted by the filament, and confined by two permanent magnets, travel in the direction of the vertical arrow. They intersect the effusing beam, represented by the grey circle, at right angle before being collected by the trap. The ions formed are extracted in the direction of the horizontal arrow. Then, the ions are accelerated between the exit of the source box and what is called the earth slit source location plate. Two half plates allows for beam deflection. The acceleration stage is followed by an ion beam shaping stage with 2 Z-focus plates between the adjustable and the alpha slits which define the angular divergence of the beam. This type of source has several drawbacks.

-First, the source box is heated up to 600 K by the filament radiation and very volatile species in the molecular beam condensing as deposits on the source walls can re-vaporize either as incident species or as new more volatile species as explained by Morland et al. (2). -Second, permanent magnets used to confine the electron beam can cause mass bias as pointed out by Drowart et al. (13). -Third, the source aperture is a hole of fixed diameter drilled in the stainless steel source box whereas a replaceable source aperture is required for transmission optimization under restricted collimation.

-Fourth, there is no extraction plate and a single acceleration plate.

Considering the above-mentioned drawbacks and the need to counterbalance the decrease of the beam transmission between the Knudsen cell and the ionization source under restricted collimation, the source box and the acceleration stage have been modified in order to increase the source sensitivity.

A picture of the new source box is seen in figure 9a. The new box, equipped with a replaceable source aperture, is made of -metal to provide magnetic shielding around the ionization volume. The box is also cooled by a liquid nitrogen Dewar vacuum vessel. Morland et al. (2) have shown that this cryogenic pumping suppress parasitic revaporizations and reduces the peak at M = 28 by a factor of 100. Figure 9b shows how the cooled source box is inserted in the new vacuum chamber.

The new emission block is seen in figure 9c. The permanent magnets are suppressed. The trap is replaced by a second independent filament to increase ionization efficiency, to homogenize the electron density in the source and finally to obtain a more symmetric ionization profile during a position scan of the effusion device. The new accelerating stage (figure 10a) is a three elements electrostatic zoom lens with one extracting plate, one accelerating plate and two half plates for beam deflection. This design is copied from the source of the 12-90HT Nuclide Corp. mass spectrometer used by Chatillon et al. (14) and by Copland and Jacobson (15). The original VG beam shaping stage is left unmodified (figure 10b). The requirements for the materials to use in the construction of ion optics lenses are reviewed in [START_REF] Moore | Charged-Particles Optics[END_REF].

Inconel 600 has been chosen for the lens metallic plates. Compared to standard austenitic stainless steel grades (AISI 304L or 316L) which exhibit weak magnetism because of their residual ferrite content, Inconel is non-magnetic. Its resistance to oxidation and corrosion, even at high temperatures, is also very good. This is important as the electrodes must withstand ion bombardment and periodic cleaning and polishing.

An electrical insulator material is needed for assembling the different plates. Choice of a ceramic material is mandatory due to the high temperature reached during the baking of the vacuum chambers. The Degussit AL23 dense alumina from the Umicore Company has been chosen because it combines a high dielectric strength (> 40 kV/mm) and a null open porosity (17) which minimizes degassing.

Other modifications and main subassemblies remaining to build

The new source and furnace chamber is seen in figure 10b with the front flange removed, its large diameter of 200 mm allows to house a 4 cell Knudsen effusion device. Complete revamping of the vacuum system has been performed to increase the pumping capacities and the conductance of the pipes in the primary and secondary circuits. A new pump control and safety system has been added.

The ion detection has been totally upgraded. The linear motion of the in-line retractable Faraday cup has been automated. The new secondary electron multiplier (22 dynodes Model 14150H from ETP) is protected against electromagnetic fields by a three layer (pure iron/copper/-metal) shielding. Ion counting electronics comprises an Ortec Model 9327 1-GHz amplifier/timing discriminator and a Signal Recovery Model 3820 125-MHz Universal Counter.

The two main subassemblies remaining to build are the furnace and its positioning system.

The tentative design of the high temperature multiple-cell furnace is shown in figure 11. It is adapted from the design of the furnace used by Chatillon and coworkers (18). The multiple-cell holder is supported by a water cooled stainless steel plate and heated by a tungsten foil resistor. The resistor is surrounded by a series of tungsten radiation shields and a tantalum box. All the necessary feedthroughs for electrical power, water cooling and thermocouples are mounted on the base flange. A two-color pyrometer, also attached to this flange, sights the axis of the multiple-cell holder. The furnace assembly presented in figure 11 is rigid and its positioning mechanism to be built is not shown in the figure. This mechanism, described in details by Heyrman et al.

(3), will move the base flange and the furnace as a whole, according to a double tilt principle in which the effusion orifices move on a spherical cap.

The main advantages are:

-first that the mechanism is fully independent of the furnace and a single system can be used for several different furnaces (e.g. monocell, multiple-cell, gas injection cell), -second that no complex mechanism and minimum degassing surfaces are under vacuum, -and third that the movement is software controlled, soft and fast with a high positioning accuracy (±0.025 mm).

Conclusions and future work

To our knowledge no multiple-cell KEMS based on these concepts is available on a commercial basis. It is required to start from an existing apparatus or to buy a new one before transforming it.

Major instrumentation and engineering work is necessary for the transformation. Molecular transmission calculations are needed to optimize the design and the future working of the spectrometer. Computer Aided Design is absolutely necessary for the mechanical engineering. This kind of project can only be carried out within a laboratory already having a strong experience in KEMS or with the technical and scientific support of an experienced team/researcher in the field.

The first tests and results of the apparatus will be presented in a second coming paper.

Figure 1 .

 1 Figure 1. Definitions of M for an isolated peak (a) and two overlapping peaks (b) or (c)

Figure 2 .

 2 Unit resolution for overlapping Gaussian peaks of equal height, arbitrary unit on the vertical axis a) 10% valley b) 5% cross-talk.

Figure 3 .

 3 Figure 3. Overlapping peaks of unequal heights, arbitrary unit on the vertical axis -The apparent intensity (solid line) at mass M results from the summation of a main peak (dashed line) and a side peak (dotted line).

Figure 4 .

 4 Figure 4. Conventional molecular beam samplinga, b, c see text.

Figure 5 .

 5 Figure 5. Restricted collimationdefinition of the geometric parameters.

Figure 6 .

 6 Figure 6. Optimization of the source aperture diameter D 2 with D e = 2 mm, D p = 1.8 mm, H 1 = 14 mm and L = 50 mm -ETS (solid line), D 1 equation 4 (dashed line).

Figure 7 .

 7 Figure 7. Optimization of L = H 2 -H 1 with D e = 2 mm, D p = 1.8 mm, H 1 = 14 mm and L = 50 mm (thick solid line), 70 mm (thin solid line), 82 mm (dotted line).

Figure 8 .

 8 Figure 8. Original VG ion source.

Figure 9 .

 9 Ion source modifications -a) cooled source box, b) inserted in the main vacuum chamber, c) two filaments ionization block.

Figure 10 .

 10 Ion guna) new accelerating stage, b) unmodified beam shaping stage.

Figure 11 .

 11 Figure 11. Multiple-cell effusion furnace.

  C16 O 2 + at mass 44 from the residual hydro-carbon peaks at mass 43 and 45[START_REF] Roboz | Introduction to mass spectrometry: Instrumentation and Techniques[END_REF]. Xenon and mercury, commonly used as calibration gases in mass spectrometry, have numerous isotopes of comparable relative abundances ( 128 Xe, 129 Xe, 130 Xe, 131 Xe, 132 Xe, 134 Xe, 136 Xe and 198 Hg, 199 Hg, 200 Hg, 201 Hg, 202 Hg, 204 Hg) requiring resolutions of 130 and 200 respectively.

Acknowledgments

The authors are very grateful to Jean Drowart for giving them the initial instrument, and to Christian Chatillon, Laurent Artaud, Hervé Collas and Ioana Nuta from the CNRS SIMAP laboratory in Grenoble for countless KEMS discussions and their invaluable help in the project. A financial support has been obtained from the PACA French region.

Appendix: molecular transmission between 2 coaxial disks

The number of molecules N transmitted between 2 coaxial disks of surfaces S 1 and S 2 (figure 12) per unit time (in mol.s -1 ) is given by Carlson [START_REF] Carlson | The Knudsen Effusion Method in The Characterization of High-Temperature Vapors[END_REF] as:

Where: 4 v n represents the total flux density of molecules emitted in the half space above S 1 in

is the number of molecules in the vapor per unit volume in mol.m -3 , P being the pressure, R the gas constant and T the temperature,

is the average velocity of molecules in m.s -1 , M being the mass of the molecules.

The term between square brackets in equation 5 has the dimension of a surface (m 2 ) and will hence be called the Equivalent Transmission Surface (ETS). The ratio between the ETS and S 1 represents the fraction of molecules emitted from S 1 in the half space above which hit S 2 .

Analytical derivation of equation 5 is not straightforward and the multiple integration methodology is explained in the appendix to the paper of Vassent et al. [START_REF] Vassent | [END_REF]. Detailed calculation is left to the reader. 12. Geometric parameters for molecular transmission calculation between two coaxial disks.


Judikaël Le Rouzo
email: judikael.le-rouzo@univ-amu.fr

David Duché

Carmen M Ruiz

François Thierry

Miriam Carlberg

Gérard Berginc

Marcel Pasquinelli

Jean Jacques Simon

Ludovic Escoubas

François Flory

J Le Rouzo

J-J Simon

Specific tools for studying the optical response of heterogeneous thin film layers

Keywords: Light management, thin films, optical properties, photonics

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

INTRODUCTION

The complexity of the interaction between light and heterogeneous matter highlights the importance of knowing the optical and electronical properties of the material, in order to be able to design the optical responses [START_REF] Locharoenrat | Optical Properties of Solids: An Introductory Textbook[END_REF]. We would like to be able to do this, however it is not so easy. The understanding of the links between the macroscopic optical properties (refractive index and extinction coefficient), opto-geometrical parameters of the heterogeneous layers and their optical responses concerns various applications in the optical range of wavelengths (control of the emissivity of the surfaces, modeling of active imaging techniques, the realization of new types of absorbers in thin film form working in the visible and infrared bands, refractive index gradient nano-films). Areas of interest are numerous such as thermal solar and photovoltaic (selective absorbers, anti-reflective, rough transparent conductive oxides, etc...) and more generally optoelectronics (special optical coatings, more sensitive photodetectors, etc...). And the possibility of realizing thin films in the form of complex structure, comprising for example nanoparticles, or offering photonic patterns, allow to design new optical behavior of a material.

The investigations for mastering the light behavior in a layer not only led researchers to use different photonic concepts but also to look for new materials with specific properties such as the mechanical flexibility, the low specific weight, the color or transparency.

The architecture of thin films can be relatively complex and requires a thorough understanding of the materials' behavior, involving accurate knowledge of the electrical, optical, and structural properties of the materials that compose the layers. The use of both experimental and simulation optical tools are then required in order to improve the optical design of the thin-film. This approach of coupling characterization and modeling provides a correct prediction and validation of device performance. This work, which is directly related to the fields of photonics, also involves knowledge in other parts of the Physics (e.g. Solid State, Electronic).

In this paper, we will first describe briefly the phenomena of light-matter interaction which can occurs in thin films. Then, we will present different devices which are under study in our laboratory, i.e. thin film solar cells, and heterogeneous thin films made of nanoparticles embedded in a polymer host matrix. After giving some details about both these structures and their basics properties we will focus our attention to the means used to measure and to model the optical properties of these thin films. The optical properties of each material are of great importance on the final performance of the device, and are based on a comprehensive set of very precise measurements. However, this is not enough, and models are needed to define the final optical parameters of new materials.

LIGHT-MATTER INTERACTION

Materials, Thin film layers

First, we mention that in this paper, we focus our study to wavelengths between 200 nm and 5 μm, which is the range of the electromagnetic spectrum of interest. We consider either metallic, semiconductor or even dielectric material in thin film form, at micrometric or nanometric scale.

The interaction between light and matter is strongly linked to both the structure of the matter, and of the light wavelength. The composition of the matter greatly influences the propagation of electromagnetic waves, and especially the optical constants (refractive index n and extinction coefficient k). When an electromagnetic radiation reaches the surface of a layer, different physical mechanisms are involved (see figure 1). A portion of the light may optionally pass through the medium if it is sufficiently transparent. Another part will be reflected back in the incident medium, and finally a part of the light may propagate within the material. In this latter case the light may be either scattered or absorbed, depending on both the structure and the optical properties of the material. Typically, a conductive medium (metal) exhibits absorption and also leads to a strong reflection. A dielectric medium on the other hand will, in its transparency region, allow the propagation of the light wave over long distances. And in the case of a semiconductor, depending on its energy bandgap, the light will be absorbed or not. We also have to mention the possibility of emission of photons, phenomena of luminescence of matter due to radiative relaxation.

We also have to point out that the ratio between the wavelength and the dimension of the layer influences the Physics used for explaining the optical waves behavior [START_REF] Escoubas | Low-dimensional optics[END_REF]. In optics, we are use to compare the critical dimension with the diffraction limit in free space propagation, i.e. when it is smaller than the wavelength of light. Indeed, in the case of quantum structures with typically sizes of a few nanometers, classical physics is in default. In this paper, we still consider in most cases material dimension close to the wavelength or smaller than /10. For the study of nanoparticles, we will use the effective medium approximation. Figure 1. Optical phenomena which may occur in an optical thin film with optical constants n and k.

Photonic structures, nanoparticles and light management

Several approaches or new structures can be used in optoelectronic devices in order to improve their performances. Different routes are possible: the first is to minimize reflection at the air-material interface with anti-reflective coatings such as thin film layers or structured surfaces (see figure 2, [START_REF] Rouzo | Optical properties of antireflective flat or rough patterned topped silicon cones gratings[END_REF]). The second is based on the engineering of the electromagnetic field to control its distribution in the thickness of a stack of thin films [START_REF] Monestier | Optical properties of antireflective flat or rough patterned topped silicon cones gratings[END_REF]. To go further, we can appeal to more innovative optical concepts, based on photonic crystals, which are structures whose refractive index varies periodically in one or more dimensions of space in order to control and modify the propagation characteristics of a light wave. Photonic crystals are used to increase light absorption in thin film solar cells [START_REF] Duché | Photonic crystals for improving light absorption in organic solar cells[END_REF]. Another alternative to increase the absorption of the photons in an active layer is to use plasma resonance of electrons at a metal / dielectric interface, which can be excited by the incident light beam. This field is known as plasmonics. The inclusion of metal nanoparticles in a layer allows to couple localized plasmons resonances and thus to change the optical response of the thin film [START_REF] Scholl | Quantum plasmon resonances of individual metallic nanoparticles[END_REF].

In this context, new concepts or new architectures for solar cells are more and more in use nowadays, due to the aim of the photovoltaic technology which promotes good efficiency at low-cost. Associated to low cost fabrication process thin film solar cells are good candidates to respond to this objective. However, to reach good efficiency we need to use together different photonic concepts.

We will show that the control of the light inside the cell is of great interest for the development of 3 rd generation solar cells made of thin film layers. And not only for the efficiency but also to design a new kind of solar cells like "Transparent and colored solar cells", interesting for the Building Integrating PhotoVoltaic (BIPV). In thin film solar cells, the apparent color and transparency is given by its reflected and transmitted spectra. We discuss on light management such as the use of Bragg mirrors, of diffraction gratings, of surface plasmonic effect or of photonic crystal to optimize the cell performances while controlling their reflected and transmitted spectra and by taking into account the human eye sensitivity.

We also work on organic thin films containing metallic nanoparticles which are interesting for different applications, including thin film solar cells [START_REF] Vedraine | Intrinsic absorption of plasmonic structures for organic solar cells[END_REF]. Our aim in this study is to precisely define the influence of these nano-objects, embedded in an organic matrix, on the optical response of a thin film.

THIN FILM LAYERS

Thin film solar cells

Nowadays, it exists various photovoltaic solar cell technologies, which are usually sorted in three generations [START_REF] Green | Third Generation Photovoltaics[END_REF]. The first one is based on silicon material and relies on the PN junction made with this semiconductor. The maturity of this technology and the good module efficiency (over 20%) make the silicon PV market leader (90%). However, PV specifications involve thinking about other technologies. Indeed, the reduction of the raw material, improving performance, adaptation to a specific market (flexible, color...), are parameters that are difficult to reach with silicon technology.

The second and the third generation of photovoltaic try to overcome certain limitations of the first generation. Among all the technologies of these generations we focus our work on thin film solar cells, using inorganic or organic semiconductor materials with high absorption coefficients. The inorganic materials used are named CIGS, CZTS, perovskite.. CIGS, and CZTS photovoltaic devices are polycrystalline thin films. These cells consist of stacks of thin layers of different materials. Depending on the stoichiometry of the chalcopyrite, the bandgap ranges from 1.04 and 1.68 eV for CIGS solar cells and from 1.0 to 1.5 eV for kesterite solar cells. These values are in the range of energy that allows high solar-energy conversion [START_REF] Shockley | Detailed balance limit of efficiency of pn junction solar cells[END_REF].

The organic semiconductor materials present significant opportunities for the production of organic solar cells (OSCs) for various reasons: their easy manufacturing process enables large scale production at low cost (roll-to-roll and ink jet techniques); they are easy to integrate (flexible substrate); the organic aspect offers a variety of structures (polymers, small molecules) and functionality (separate adjustment of the bandgap ...). If the organic materials have the advantage of having strong absorption coefficients (more than 10 5 cm -1 ), the low mobility of the charge carriers (10 -6 to 100 cm 2 .V - 1 .s -1 ) limits the thicknesses of the films to 100-200 nm, that is to say at much lower values than 400 or 500 nanometers required to absorb a major portion of the solar spectrum. It is therefore necessary to increase the interaction between the incident light and the photoactive layer. Moreover, the exciton diffusion lengths do not exceed 10 or 20 nm in the majority of organic materials; so this is the maximum distance that can be tolerated between two donor-acceptor material interfaces. In summary, all these dimensional constraints require that the optimal structure of the active layer of an organic solar cell has to be an interpenetrated structure type (named bulk heterojunction (BHJ)) [START_REF] Hoppe | Organic solar cells: An overview[END_REF].

In the last years, the perovskite solar cell technology has attracted a lot of attention. The structure of the organometal halide perovskites is of ABX3 (A = alkyl-NH3, B = Pb or Sn, X = I,Cl, or Br). Due to these special properties, such as very strong absorption and a tunable bandgap (from 1.57 eV up to 2.3 eV covering the visible spectrum up to the nearinfrared) by modifying the chemical composition (e.g., alloying iodine with bromine for the X-site composition), this hybrid material is very promising for the field of photovoltaics [START_REF] Sessolo | Perovskite solar cells join the major league[END_REF].

The figure 3 presents the typical structure of the thin film solar cells described above and which are under study in this work. We have to notice that the whole thickness of each stack is ranging from hundred nanometers (organic and perovskite) to a few micrometers (CIGS and CZTS). All of these cells have also the possibility to be made on flexible substrate.

Organic thin films with nanoparticles

The rapid progress in nanotechnology in the last years allowed the realization of well controlled nanostructures with specific properties more varied than those of bulk materials. Structured materials at the nanometer scale are used in optoelectronic applications because their optical and electrical properties can be controled by changing their nature, composition or their geometry. At such a scale of a few nanometers the electron confinement effects change with the spatial dimensions. Technological applications based on nanostructures are numerous. The most affected areas are optoand nanoelectronics, biotechnology and aerospace for which the mechanical properties of nanocomposites are interesting. Here, we present some work done on metallic nanoparticles for optoelectronic applications. These nanostructures are enclosed in a polymer host matrix. The nanoparticles in polymer thin films are assumed to result in layers with tunable optical properties.

Silver nanoparticles of different shapes and sizes are chemically synthesized to be deposited in thin layers with a view to obtain transparent layers which absorb light over a wide spectral range. The nanoparticles are deposited in thin layers into the polymer, soluble in water, non-absorbing in the visible and compatible with silver nanoparticles (see figure [START_REF] Monestier | Optical properties of antireflective flat or rough patterned topped silicon cones gratings[END_REF]).

SET OF OPTICAL MEASUREMENTS 4.1 Objectives

In this section, we briefly describe the different optical characterization techniques which can be used together in order to define entirely the optical properties of thin film layers. If we want to develop accurate models to confirm or to predict our measurements, we need to know the basic optical parameters such as the optical index or the dielectric permittivity. These parameters can be linked to the absorption processes, and as we know from thin-film solar cells, they can vary strongly with the deposition method. Also, the range of optical response of the material (reflection, absorption, transmission) will be an important parameter for the design of the layer. All of these values can be obtained with a combination of spectroscopic ellipsometry (SE) measurements of the optical indices and spectrophotometric measurements of the R, T, and A (reflectance, transmittance, and absorption) spectra.

Obviously, to be quite precise, a complete study of a thin film layer should include at least structural techniques (e.g., electronic microscopy, x-ray scattering, ultraviolet photoelectron spectroscopy, and atomic force microscopy) and for thin film solar cells, electrical techniques (e.g., conductance measurements, Hall effect, and deep-level transient spectroscopy), which also contribute to improve the elaboration of the layers. For instance, a conductive-Atomic Force Microscopy with possibility of realizing Kelvin Probe-AFM measurements in dark and under light bias of different wavelengths could help to understand the impact of the structure on both optical and electrical behavior at the microscopic level.

In this paper we focus our attention on optical measurements but we should keep in mind to consider electrical measurements to have a better understanding of the whole behavior of a material or a device.

Ellipsometry

The spectroscopic ellipsometry (SE) is an optical technique used for surface and thin film analysis. SE is a very efficient tool to determine the optical indices of bulk materials and materials in thin-film form (n and k). The ellipsometric measurements consist in measuring the change in polarization after reflection on a flat surface, and what we get are the two ellipsometric parameters (tanΨ and cosΔ). These latter are thus extracted from the ratio between the Fresnel coefficients in p-polarization (rp) and in s-polarization (rs), which can be formulated as follows:

r p r p = tan Ye iD (1)
where tan(Ψ) = |rp|/|rs| represents the relative amplitude attenuation and Δ = arg(rp) -arg(rs) is the phase shift between the p-and s-polarizations. A dispersion model is then elaborated to determine the dielectric constant of the materials (ε = ε1 + i*ε2). The absorption (A) of the layer is thus predicted thanks to a transfer matrix method (TMM) and using optical indices (n and k) extracted from variable angles SE. Finally A is compared to the A deduced from reflectance (R) and transmittance (T) measurements. For thin films of new materials, or thin films with nanoparticles, this study is very challenging because of the anisotropy of the layer and/or the surface roughness. To be sure of getting the correct indices, it is possible to use a two-layer model with a surface roughness correction using a Bruggeman effective medium approximation (EMA).

In addition, such method is generally limited by the accurate calibration of the optical instruments. This could lead to important discrepancies between the measured absorption spectra and the predicted ones from the ellipsometric results assuming an isotropic model. The optical indices can thus serve as input parameters to model the optical performances of thin-film, but they are also of high interest for the extraction of information on the electronic properties of the materials. Indeed SE is of high interest not only for nondestructive measurements of thicknesses and optical indices but also for nondestructive measurements of the electronic transitions in materials within thin-film stacks [START_REF] Bencheikh | Ellipsometric study of the optical transitions of PC60BM and PC70BM thin films[END_REF].

Photoluminescence and Photoreflectance

Photoluminescence (PL) and/or photoreflectance (PR) measurements are useful for studying the electronic levels inside the layers. More, the combination of photoluminescence technique with photoreflectance technique can be employed for the analysis of the different layers of ultrathin devices and, in particular, the simultaneous determination of their fundamental transitions and related default.

Photoluminescence spectroscopy provides information about the structure of each layer, e.g. analysis of optical transitions inside the band of the material. PL mapping also brings light into possible inhomogeneity related with the advanced structure of the devices. PL measurements can be performed at different temperature, especially at low temperature, and with different excitation wavelengths for the analysis of optical confinements and other optical phenomena related to the structure of the thin films. The PL technique investigates the emission of light from a solid due to the deviation of the system from the thermal equilibrium. It particularly relates to the deviation of the equilibrium via the absorption of light with energy higher than the bandgap of the material. The luminescence is due to both the relaxation of electrons to lower energy states and the simultaneous emission of photons. We have to notice that not all the possible relaxation processes will generate photons, since the transition should be dipole-allowed for a successful photon emission to occur. Among them, there is a set of different transitions that are possible to see in a semiconductor used in photovoltaics (these transitions are presented in Fig. 5) [START_REF] Unold | Advanced Characterization Techniques for Thin Film Solar Cells[END_REF]. For obtaining the bandgap of any semiconductor, the most precise technique is the photoreflectance. With this technique we can also see interband transitions in the range of measurements. Indeed, from photoreflectance measurements it is possible to analyze the band configuration at the interface, by measuring the fundamental optical transitions. As the band structure of any semiconductor is very sensitive to modifications such as diffusion or structural strains, this technique permits to detect possible interplaying of the cell structure with the basic properties of an absorber and thus, the performance of a solar cell. While PL is a technique used to study the interaction between the semiconductor and light, and needs a minimal amount of material to provide an interpretable signal, reflectance-based techniques exploit the sudden variation of the optical indices at an interface. This means that they are much more sensitive to small quantities of material and can bring information on what is really happening at the interface between two different materials. PR belongs to the family of modulated reflectance techniques such as electroreflectance or piezoreflectance. The main advantage of PR is that, as it uses an optical modulation, the whole setup is optics based, and does not require any previous preparation of the sample for analysis such as contact deposition [START_REF] Hamnett | Theory of electroreflectance and photoreflectance of semiconductors[END_REF][START_REF] Aspnes | Band nonparabolicities, broadening, and internal field distributions: the spectroscopy of Franz-Keldysh oscillations[END_REF].

OPTICAL STUDY OF HETEROGENEOUS THIN FILMS

In this last section, we propose to show some examples of optical studies made on our samples, which have been presented in section 3. Our objective is to highlight the accuracy of our measurements and the link with at first the optical behavior of the material but also with the structural properties of some of them and with the performances of the device. These results are not exhaustive, and the choice that we did for this paper could be extended to a large panel of other structures.

Photoluminescence and Photoreflectance of thin film solar cells

As discussed in section 3, the bandgap of the perovskite material is tunable between 1,57 eV and 2,3 eV, depending on the stoichiometry of the layer, which is of great interest for multijunctions solar cells. Regardless of the deposition method of the perovskite, we must validate the energy gap depending on the composition of the layer, including the ratio I / Br. The combination between photoluminescence and photoreflectance measurements, is a very powerful tool by providing a very accurate measurement of the fundamental optical band gap of the semiconductor.

The figure 6 presents a study both by PL and PR of organo-metallic perovskites, CH3NH3PbCl x (I y Br 1-y ) 3-x , with different I/Br ratios. The dotted lines of the same color as the PL peak indicate the band gap position calculated from PR spectra. On the right, a summary table with the PL peak positions, the PR bandgaps calculated from measurements and the k values from the PL power dependence study for all the compositions [START_REF] Ruiz | Using combined photoreflectance and photoluminescence for understanding optical transitions in perovskites[END_REF].

While the PL peaks are all red shifted and very near to the pure iodine peak, the PR bandgap position follow the expected distribution. The values in the table, show the differences between the PL maximum position and the PR bandgap. The reason for the shifting of the PL spectra is not yet clear. A discussion must be held on the PL measurements and on the transitions, which occur in these samples. Some Raman spectra measurements could help us on this study and for the simultaneous analysis of their fundamental and defect related transitions.

Figure 6. PL peaks for different I/Br ratios in CH3NH3PbCl x (I y Br 1-y ) 3-x [START_REF] Ruiz | Experimental and Simulation Tools for Thin-Film Solar Cells[END_REF] and PR results [START_REF] Ruiz | Using combined photoreflectance and photoluminescence for understanding optical transitions in perovskites[END_REF].

A PR study on CIS solar cells is presented in the figure 7. These PR measurements can be performed to analyze the origin of the current density (J SC ) deviations in a set of CuInS2/CdS solar cells fabricated in the same nominal conditions, and can be compared with structural and electrical characterizations [START_REF] Moreau | Impact of Cu-Au type domains in high current density CuInS2 solar cells[END_REF]. When PR spectra are obtained for a low and a high J SC device, the resulting transitions are different, as it can be seen in Figure 6. By studying also the Raman scattering of these layers we observe that small fractions of the CIS Cu-Au phase (CA) appears for the samples with better J SC , leading to the conclusion that having small amounts of this defective phase helps to minimize the strain in the chalcopyrite phase CIS (CH), improving their transport properties.

Ellipsometric study of thin film

Here, we present different ellipsometric studies on different thin films. As presented before, this technique is an interesting tool to determine the thickness and the optical indices (n and k) of a layer. However, although the measurement is not so complicated, the model that is used for fitting the values can become quickly difficult in the case of particular materials or surfaces (rough or anisotropic).

The first example concerns a hybrid layer made of a blend between an inorganic semiconductor material and an organic material. In our case, we work on a bulk heterojunction in ZnO and P3HT (poly(3-hexylthiophene-2,5-diyl)) (ratio 2:1), which propose bandgaps within the spectral range of the ellipsometer. The optical indices n and k, presented on top of the figure 8, are obtained using Tauc-Lorentz models [START_REF] Duché | Optical performance and color investigations of hybrid solar cells based on P3HT:ZnO, PCPDTBT:ZnO, PTB7:ZnO and DTS(PTTh2)2:ZnO[END_REF]. The values of the correlation coefficients of these fits indicate appropriate fits to the data. On this figure, the reflection [R(λ)] and the transmission [T(λ)] spectra for P3HT:ZnO (1:2) is also represented (on bottom of the figure). A comparison is made between these measurements and the optical simulations done by TMM using the optical indices presented before and the film thicknesse measured with a mechanical profilometer, as input parameters. We can see a good agreement between the calculated and the measured spectra which demonstrates the reliability of these optical indices n and k to predict the real optical properties of the films. Recently, a study has shown that a sum of Gaussian oscillators can be used to model the imaginary part of the dielectric function of organic semiconductors such as PC70BM ( [START_REF] Scholl | Quantum plasmon resonances of individual metallic nanoparticles[END_REF][START_REF] Scholl | Quantum plasmon resonances of individual metallic nanoparticles[END_REF]-phenyl-C71-butyric acid methyl ester) [START_REF] Bencheikh | Ellipsometric study of the optical transitions of PC60BM and PC70BM thin films[END_REF]. In ellipsometric study, Gaussian oscillators set from absorbance measurements, are used for the dispersion model elaboration, and specifically to model the absorption line shape for organic semiconductors. Thanks to its suitability to describe strong electron-phonon coupling in π-conjugated molecules, electronic transitions can be extracted from ellipsometric measurements for PC70BM in the UV-visible range. The figure 8 shows the imaginary part of the dielectric constant of PC70BM, and some electronic transitions. We found a very good agreement between electronic transition values obtained from SE measurements and literature data. It demonstrates the reliability of the dispersion model and shows the potential of SE measurements for the determination of the optoelectronic properties of materials.

Figure 9. Imaginary part of the PC70BM organic material and Gaussian oscillators which have been used for the dispersion model elaboration [START_REF] Bencheikh | Ellipsometric study of the optical transitions of PC60BM and PC70BM thin films[END_REF].

The last example we present in this section, is related to an optical study performed on a thin film of metallic nanoparticles embedded in PVP polymer (thickness of hundred nanometers). The nanoparticles are in the shape of nanoprisms. The ellipsometric measurements on this kind of heterogeneous layer are not so easy, due to the dispersion of nanoparticles inside the polymer and also due to a possible roughness of the layer surface. Both the refractive index and the extinction coefficient are shown on the figure 10 (on the left). The k coefficient presents a large peak at 700 nm with a broadening of 150 nm at width-half, which corresponds to the plasmonic resonance of the nanoprisms inside the polymer matrix. The TMM method is used to calculate the reflection of the layer from ellipsometric results. The figure 10, at the right, showing the comparison between this calculation and our spectrophotometric measurement, allows us to be more confident on the optical indices found with our dispersion model.

Figure 10. Left : Ellipsometric measurements on heterogeneous layer made of metallic nanoparticles embedded in PVP polymer. Right : Reflection spectrum measured and calculated by TMM thanks to ellipsometric measurements.

Photonic crystals for light trapping in Organic Solar Cells

In order to control the light inside a solar cell, some photonic structures can be added to the device. Here, we present the possibility to introduce photonic crystals inside an Organic Solar Cell (OSC), to improve the absorption of cell. This work is based on the modeling of the active layer under the shape of a photonic crystal slab. The structure modeled is presented on the figure 11, and consists of a stack of thin film layers, plus a double patterning of the active layer. Finite Difference Time Domain (FDTD) modeling have been used to calculate the photonic absorption spectra of two different structures, one planar and the other one with the photonic crystal slab. The figure 11 shows that the PC patterning boosts the absorption of the OSC, due to a Bloch mode coupling with a peak at λ = 704 nm.

Several modeling at different angles were also done, showing that it is possible to obtain multiple Bloch resonances in the case of a large incidence cone. And finally, an absorption gain of around 15 %, with an 8° incident angle cone, using a PC was obtained [START_REF] Duché | Photonic crystals for improving light absorption in organic solar cells[END_REF].

Figure 11. Left : Organic solar cell with a double photonic crystal patterning. Right : Absorption spectra for two different OSC structures (extracted from [START_REF] Duché | Photonic crystals for improving light absorption in organic solar cells[END_REF]).

Color predicting in Organic Solar Cells

The results presented in this part concern color and performance investigations of an organic solar cell, with PTB7:PC70BM as the active layer. The objective is to design solar cell with color specifications, still maintaining good performances, i.e. efficiency at the state of the art.

This study is based on a classical architecture of an OSC (see figure 12, on the left), which is a stack of thin film layers. The whole structure is optimized in terms of thickness of each layer, in order to control the interferential phenomena occurring in the multilayer stack. An ellipsometric study was done previously to obtain the optical indices of all the layers. First, we calculate the total number of photons absorbed inside the active layer under an AM1.5 illumination as functions of the ZnO layer thickness and of the active layer thickness. By taking into account the sensitivity of the human eye which is directly linked to the color perception process based on the CIE xyY.

CONCLUSION

Nowadays, the materials used in optoelectronic devices are quite complex providing some difficulties to predict the optoelectronic behavior. In a first step, the knowledge of the optical properties of materials is necessary to design an optimized layer according specific properties.

Through this paper, we tried to present the optical behavior of thin film layers, studied through a set of tools, both experimental and modeling. We choose different examples of optical studies, mixing measurement and modeling, to show the complementarity of different set-up to obtain information on our structures. We also point out that these works can be performed on different layers, either organic or inorganic, on photonic structures or even on layers including metallic nanoparticles. This is possible thanks to both precise modeling and precise measurements.

Ellipsometry, spectrophotometry, PL, and PR characterizations are powerful tools to get some important parameters of a material. The combination of these techniques can also bring more information. Obviously, the use of other techniques, not described here, allows going more in details about the complete behavior of a thin film. However, this is not sufficient if we want to be confident in our measurements, and if we want to predict the optical behavior of our device. A complete modeling of the thin film layers, including the Physics of the material, allows concluding or predicting their performances. A better knowledge on the light management in the "new thin films layers" is now possible by combining accurate measurements and precise modeling. The efficiency of solar cells made of CIGS, perovskite, P3HT:ZnO, PC70BM can then be maximize; the color of solar cells can be designed; the optimal properties of PPV thin films containing metallic nanoparticles can be mastered.

Figure 2 .

 2 Figure 2. SEM pictures of antireflective pyramidal structures made of silicon, working in the visible and infrared spectral range. a) flat-topped b) patterned top c) rough-topped silicon cones grating. Images extracted from reference [3].

Figure 3 .

 3 Figure 3. Typical structures of thin film solar cells. From left to right, organic solar cell, CIGS/CZTS solar cells and Perovskite solar cell.

Figure 4 .

 4 Figure 4. Heterogeneous thin film layer under study.

Figure 5 .

 5 Figure 5. Schematic representation of the different origins of transitions that can be observed by photoluminescence measurements. From left to right the free (FX) and bound (FB) excitonic transitions, the free-bound transitions (p-D0 and e-A0), the Donor-Acceptor Pair and the Bound to Bound transitions) [14].

Figure 7 .

 7 Figure 7. PR spectra of a high Jsc and low Jsc CIS solar cell, showing the splitting of the valence band for the low Jsc values (right, top) that originates from strain in the material related with the presence of Cu-Au regions.[START_REF] Moreau | Impact of Cu-Au type domains in high current density CuInS2 solar cells[END_REF]

Figure 8 .

 8 Figure 8. Top : Optical indices n (continuous lines) and k (dotted lines) as a function of the wavelength λ for P3HT:ZnO (1:2) (Inset is a picture of the sample.) Down : Comparisons between experimental measurements of T (-) and R (. . . ) and optical simulations of T (Δ) and R (O) for layers coated on glass substrates [20].

  Curves are drawn to present the different colors that can be obtained by varying the thicknesses of the ZnO layer and the PTB7:PC70BM layer. The different shapes (lines or curves) of the diagram correspond to different ZnO thicknesses (from 50 to 90nm, by 10 nm step). At the end of these modeling results, three solar cells ("Green G, Yellow Y, and Blue B) were experimentally realized with power conversion efficiencies of 6.73 %, 7.10% and 7.59%, respectively. The photograph images of the three solar cells, G, Y and B under different observation angles are presented near the chromaticity diagram. Finally, this work has shown the ability to control the color of the organic solar cells, while keeping a good efficiency.

Figure 12 .

 12 Figure 12. Left : Organic solar cell in a classical architecture. Right : Predicted color as a function of active layer and ZnO thicknesses (An arrow indicates the increase of the active layer thickness) and photograph images of the Green (G), Blue (B) and Yellow (Y) solar cells at 8° and 45° (right) [21].


D Quadri

E Soutif

P Tolla

Exact solution method to solve large scale integer quadratic multidimensional knapsack problems 1

Keywords: Integer programming, separable quadratic function, linearization, surrogate relaxation, branch-and-bound

In this paper we develop a branch-and-bound algorithm for solving a particular integer quadratic multi-knapsack problem. The problem we study is defined as the maximization of a concave separable quadratic objective function over a convex set of linear constraints and bounded integer variables. Our exact solution method is based on the computation of an upper bound and also includes pre-procedure techniques in order to reduce the problem size before starting the branch-and-bound process. We lead a numerical comparison between our method and three other existing algorithms. The approach we propose outperforms other procedures for large-scaled instances (up to 2000 variables and constraints).

Introduction

We develop in this paper an exact solution method for solving a particular class of nonlinear knapsack problems. The integer quadratic multidimensional knapsack problem (QMKP ), which is known to be NP-hard [START_REF] Lueker | Two np-complete problems in nonnegative integer programming[END_REF] [START_REF] Lueker | Two np-complete problems in nonnegative integer programming[END_REF], involves the maximization of a concave quadratic and separable function over a convex set of linear constraints 1 A extended abstract of this paper appeared in LNCS 4362 pp. 456-464, 2007 † LAMSADE, Université Paris-Dauphine, 75775 Paris cedex 16, France.

{quadri, tolla}@lamsade.dauphine.fr ¶ CEDRIC, Conservatoire des Arts et Métiers, 292 rue Saint Martin, 75003 Paris, France. soutif @cnam.fr (called knapsack constraints) and bounded (pure) integer variables. It can be written as:

(QMKP )        max f (x) = n j=1 f j (x j ) = n j=1 c j x j -d j x 2 j s.t.
n j=1 a ij x j ≤ b i , i = 1, ..., m 0 ≤ x j ≤ u j , j = 1, ..., n x j ∈ N, j = 1, ..., n where the coefficients c j , d j , a ij , b i are nonnegative. The bounds u j of variables x j are integers such that u j ≤ ( c j 2d j ) because of the concavity of each f j , x * j ≤ ( c j 2d j ), where x * j is the optimal solution of the program max x j ≥0 f j (x j ). Problem (QMKP ) has wide applications, including financial models [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF] [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF], [START_REF] Faaland | An integer programming algorithm for portfolio selection[END_REF] [START_REF] Faaland | An integer programming algorithm for portfolio selection[END_REF] production and inventory management [START_REF] Bretthauer | The nonlinear knpasack problem -algorithms and applications[END_REF] [START_REF] Bretthauer | The nonlinear knpasack problem -algorithms and applications[END_REF]. However, most of the knapsack problems literature has addressed attention to specialized versions. For instance, there are large bodies of literature focusing on knapsack problems with linear objective function and a single constraint or m contraints (see [START_REF] Fayard | Reduction algorithms for single and multiple constraints 0-1 linear programming problems[END_REF] (Fayard and Plateau, 1974), [START_REF] Martello | Knapsack problems: algorithms and computer implementations[END_REF] [START_REF] Martello | Knapsack problems: algorithms and computer implementations[END_REF]), [START_REF] Fréville | The multidimensionnal 0-1 knapsack problems -bounds and computational aspects[END_REF] ( [START_REF] Fréville | The multidimensionnal 0-1 knapsack problems -bounds and computational aspects[END_REF], on knapsack problem with the quadratic objective function of (QMKP ) over a single linear constraint and 0-1 or pure integer variables (see [START_REF] Billionnet | An exact method based on lagrangian decomposition for the 0-1 quadratic knapsack problem[END_REF] ( [START_REF] Billionnet | An exact method based on lagrangian decomposition for the 0-1 quadratic knapsack problem[END_REF]), [START_REF] Pisinger | Solution of large quadratic knapsack problems through agressive reduction[END_REF] [START_REF] Pisinger | Solution of large quadratic knapsack problems through agressive reduction[END_REF], [START_REF] Bretthauer | The nonlinear knpasack problem -algorithms and applications[END_REF], [START_REF] Mathur | A branch and bound algorithm for a class of nonlinear knapsack problems[END_REF] [START_REF] Mathur | A branch and bound algorithm for a class of nonlinear knapsack problems[END_REF]). Nevertheless several applications require the use of pure integer variables and m capacity constraints, such as capital budgeting.

Even if many theoretical approaches have been proposed to solve integer quadratic problems (see for instance [START_REF] Cooper | A survey of methods for pure nonlinear integer programming[END_REF] [START_REF] Cooper | A survey of methods for pure nonlinear integer programming[END_REF], [START_REF] Körner | Integer quadratic progarmming[END_REF][START_REF] Körner | On the numerical realization of the exact penalty method for quadratic programming algorithms[END_REF] (Korner 1985 and 1990), only few of these methods have been implemented in practice so few experimental results can be found. There have been a limited number of papers studying (QMKP ). [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF] [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF] proposed a branch-and-bound algorithm specifically designed to solve (QMKP ), unfortunately the computational results were limited to instances up to 20 variables and constraints. However, the real-world applications require effective methods which are able to solve large scale instances of the problems. Since, (QMKP ) is NPhard, one should not expect to find a polynomial time algorithm for solving it exactly. Hence, we are usually interested in developing branch-and-bound algorithm. A key step in designing an effective exact solution method for such a maximization problem is to establish a tight upper bound on the optimal value. In a previous study [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF], we present an effective upper bound method based on a linearization and surrogate relaxation. We have compared analytically and computationally our upper bound to the bound suggested by [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF] [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF], the basic LP-relaxation of (QMKP ), and the LP-relaxation of the equivalent linearized formulation (MKP ). Simulation results, over a set of large instances (up to 2000 variables and constraints), showed that our upper bound is of good quality and closer to the optimum than the three other. Finally, the proposed upper bound can be computed in a very quick CPU time.

We propose in this present study, using our tight upper bound [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] to develop an exact solution method to solve (QMKP ). Our algorithm also incorporate preprocessing procedures in order to reduce the size of the initial problem before starting the branch-and-bound and a heuristic to find a good feasible solution given in [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] ( [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF]. We then compare the computational time of our method with three other existing methods which include the three upper bounds previously mentioned. Our computational testing, presented latter in this paper, over a set of large instances (up to 2000 variables and constraints) evidences the computational performance of our branchand-bound and its ability to solve real-sized instances.

The paper is organized as follows. The next section is dedicated to a description of the existing exact solution methods to (QMKP ). Section 3 summarizes the upper and lower bounds algorithms we proposed in a previous work and we use in the proposed branchand-bound to solve (QMKP ). Our branch-and-bound also incorporates pre-processing procedures which are details in Section 3. The computational results are reported in Section 4. We finally conclude in Section 5.

In the remainder of this paper, we adopt the following notations: letting (P ) be an integer or a 0-1 program, we will denote by (P ) the continuous relaxation problem of (P ). We let Z[P ] be the optimal value of the problem (P ) and Z[P ] the optimal value of (P ).

Existing exact solution methods

In this section we describe three existing exact solution methods to tackle (QMKP ). Each of them include an upper bound whose quality has been established in a previous work in [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF]. We will compare the computational performance of the exact solution method we proposed with these three other branch-and-bound algorithms in Section 4.

The Djerdjour, Mathur and Salkin exact solution method (DMS) [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF]. These authors develop a branch-and-bound algorithm based on the computation of an upper bound of better quality than the one provided by solving the LP-relaxation of (QMKP ). This upper bound is computed solving a polynomial problem derived from a linearization of the initial problem and a surrogate relaxation. The authors first use a direct expansion originally proposed by Glover [START_REF] Glover | Improved linear integer progamming formulations of nonlinear integer problems[END_REF] (Glover, 1975) of the integer variables and apply a piecewise linear interpolation to the initial objective function initially used by [START_REF] Mathur | A branch and bound algorithm for a class of nonlinear knapsack problems[END_REF] [START_REF] Mathur | A branch and bound algorithm for a class of nonlinear knapsack problems[END_REF]. [START_REF] Mathur | A branch and bound algorithm for a class of nonlinear knapsack problems[END_REF] ( [START_REF] Mathur | A branch and bound algorithm for a class of nonlinear knapsack problems[END_REF] an exact solution method for the single constraint integer Cahiers du LAMSADE quadratic knapsack problem. These authors transform the initial quadratic problem into a 0-1 linear equivalent formulation by applying a direct expansion on the integer variables and a linear interpolation on each quadratic function f j . They simply solve the equivalent problem using a solver so as to obtain the optimal value of the original problem. The 0-1 linearization branch-and-bound we suggest to test to solve to optimality (QMKP ) is a straightforward application of [START_REF] Mathur | A branch and bound algorithm for a class of nonlinear knapsack problems[END_REF] [START_REF] Mathur | A branch and bound algorithm for a class of nonlinear knapsack problems[END_REF] to the case of m capacity constraints. Following the approach of these authors we convert (QMKP ) to a 0-1 multidimensional knapsack problem (MKP ) which optimal value is equal to the one of (QMKP ) (the formulation of (MKP ) is given in Section 3.1). The corresponding branch-and-bound algorithm computes at each node of the search tree the LP-relaxation of (MKP ) which provides an upper bound of the optimal value of (MKP ). This approach has never been used to solve directly (QMKP ).

A zero-one linearization branch-and bound (LBB). Mathur and Salkin develop in

A standard branch-and-bound algorithm (SBB). Since the objective function of (QMKP ) is concave and the feasible set is convex the LP-relaxation of this problem can be found and thus provides an upper bound for (QMKP ). Consequently, a classical branch-andbound consists of computed this bound at each node of the search tree.

The proposed branch-and-bound algorithm

In this section we develop a branch-and-bound algorithm which key step is the computation of a tight upper bound [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF]. This upper bound method involves two improvements of the algorithm proposed by [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF] [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF] summarized in Section 2. We also develop a heuristic which provides a good feasible solution we use as a starting point of the process. Before starting the solution procedure we implement three pre-processing procedures to reduce the problem size. We implemented the proposed branch-and-bound algorithm using a best bound strategy which chooses the node with the best (the lowest) upper bound.

Upper bound computation

The proposed upper bound is computed by applying a linearization and a surrogate relaxation presented in [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF], which is derived from two improvements of the bound suggested by [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF] [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF]. The first one speeds up the computational time of the bound. The second improvement increase the quality of the bound. We now summarize the main steps of our method to get a tight upper bound for (QMKP ).

First an equivalent formulation of (QMKP ) is obtained by using a direct expansion of the integer variables x j and by applying a piecewise linear approximation to the ini-4

Cahiers du LAMSADE tial problem as employed in [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF] [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF]. Consequently, (QMKP ) is converted into a 0 -1 multidimensional knapsack problem (MKP ):

(MKP )    max n j=1 ( u j k=1 s jk y jk ) s.t. n j=1 (a ij u j k=1 y jk ) ≤ b i , i = 1, ..., m y jk ∈ {0, 1}
where

u j k=1 y jk = x j , s jk = f jk -f j,k-1 and f jk = c j k -d j k 2 .
The second step consists in getting the surrogate problem associated to the LP-relaxation of (MKP ) as also discussed in [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF] [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF]. The resultant problem (KP, w) can be written as

(KP, w)    max n j=1 ( u j k=1 s jk y jk ) s.t. n j=1 [ m i=1 w i a ij ] u j k=1 y jk ≤ m i=1 w i b i y jk ∈ {0, 1}
The LP-relaxation of (KP, w) provides an upper bound for (QMKP ) (a proof is given in [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF]). Nevertheless the quality of this bound depends on the surrogate vector employed to establish the surrogate problem.

The optimal surrogate multiplier, denoted by w * , corresponds to the optimal solution of the dual surrogate problem (SD) (see [START_REF] Glover | Surrogate constraint duality in mathematical programming[END_REF] (Glover, 1975)). The problem (SD) can be expressed as min w≥0 Z[KP, w]. Since the objective function of (SD) is quasi-convex [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF] [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF] solve (SD) via a local descent method which is shown in [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] ( [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] to be very time consuming. We then suggest, in [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] , an alternative way to compute w * which is assessed to be quicker than the local descent method, using the result that the optimal solution of dual of (MKP ) provides an optimal solution of (SD).

Experiment results assess the computational efficiency of this alternative way for computing w * (see [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] ).

The second improvement proceeds from an additional stage in which we solve (KP, w * ) in 0-1 variables rather than in continuous variables as it is done by [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF] in [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF]. Analytically the quality of the bound is increased. The experiments quantify the gap provides by this additional step.

Lower bound computation

In this section we sum up the main steps to get a feasible solution for (QMKP ). This lower bound is used in [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] to assess the quality of our upper bound.

In this present work it will be used as a good starting solution. The main idea of the proposed heuristic is the following. Since it is proved in [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] that the optimal value of (MKP ) is closer to the optimum of (QMKP ) than the optimal value of (QMKP ), we start from the optimal solution, y * , of (MKP ), to tackle a feasible solution for (QMKP ). Letting k y * jk = α j , for each variable x j of (QMKP ), we add to (QMKP ) the constraint ⌊α j ⌋ ≤ x j ≤ ⌊α j ⌋+1, where ⌊α j ⌋ denotes the greatest integer smaller or equal to α j . Thus, each variable becomes bivalent, and since the objective function is separable, it can straightforwardly be shown that the resulting problem is a 0-1 linear multidimensional knapsack problem. Obviously, solving this knapsack problem yields a feasible solution for (QMKP ) which is not necessarily optimal for (QMKP ).

Pre-processing techniques

Most commercial integer programming solvers propose a pre-processing phase which simplifies the problem being solved before starting a branch-and-bound procedure. This pre-processing phase consists of reducing the number of variables and constraints of the initial problem, using logical issues and variable fixation techniques. In this section we describe the pre-processing procedures we implemented in order to speed up the solution of (QMKP ) and discuss the utility of such procedures.

We use three pre-processing procedures: the first one detects and discards some redundant constraints, the second one reduces the bound of the integer variables (using [START_REF] Hammer | Constraints pairing in integer programming[END_REF] (Hammer et al., 1975) ), and the third and last one fixes some 0-1 variables to their optimal values.

Eliminating redundant constraints

We first discard constraints which are trivially implied by a strong one. Since (QMKP ) only includes knapsack constraints, this strong constraint is simply found by considering the constraint with the smallest right-hand-side, say b i 0 . Then we set α i = max 1≤j≤n

a ij a i 0 j . Suppose that a constraint i verifies α i ≤ b i b i 0 , we have: ∀j ∈ {1, . . . , n}, a ij a i 0 j ≤ α i ,
and since for all i and j a ij ≥ 0:

∀x verifying constraint i 0 , n j=1 a ij x j ≤ n j=1 α i a i 0 j x j ≤ α i n j=1 a i 0 j x j ≤ α i b i 0 ≤ b i 6 Cahiers du LAMSADE Consequently, when a constraint i satisfies α i ≤ b i b i 0
, this constraint is immediately satisfied when constraint i 0 is verified. This criterion allows us to detect the constraints obviously dominated by constraint i 0 .

We could iterate this technique using not only the constraint included the smallest right-hand-side but also the one with the second smallest right-hand-side (and so on). However, this idea does not appear experimentally efficient. This simple technique, whose complexity is O(mn), allowed us to significantly reduce the number of constraints of all the considered instances. As discussed in Section 4. its efficiency strongly depends of the structure of the considered instance. Indeed, we randomly generate three kinds of instances: squared instances (n = m), rectangular instances (m = 5%n) and correlated instances. The reductions obtained are of good quality (between 52% and 56% of the constraints can be removed) concerning the squared and correlated instances.

Reducing the bounds of the integer variables

Since the objective function f of problem (QMKP ) is separable into n concave subfunctions f j , each integer variable x j is naturally bounded by c j 2d j . Consequently, the bound u j of variable x j is always chosen between 1 and max 1, c j 2d j when instances are randomly generated. However a high value of parameter u j may considerably increase the difficulty to solve the problem (for example the most difficult instances generated in Section 4 involve integer bounds up to 70). [START_REF] Hammer | Constraints pairing in integer programming[END_REF] propose in [START_REF] Hammer | Constraints pairing in integer programming[END_REF] a technique called constraint pairing to reduce the bounds of some integer variables verifying a set of linear inequalities. The idea of this method is to arbitrarily choose two inequalities from the set, say n j=1 a j x j ≤ a 0 and n j=1 b j x j ≤ b 0 , and to establish a third surrogate one obtained by multiplying the second constraint by a positive parameter t and by summing it with the first constraint. The surrogate constraint is: n j=1 (a j + tb j )x j ≤ (a 0 + tb 0 ). When t is judiciously chosen, the surrogate constraint may allow us to tighten the bounding interval of variable x j , [0, u j ], for instance by noting that variable x j may no more take the value 0 or u j without violating the surrogate constraint. The authors show it suffices to successively affect only n + 2 values to t in order to get as many conclusions as possible about the bounds of all the variables from the two constraints initially chosen. The complexity of the whole procedure is O(n 2 ) for each couple of pairing inequalities. This technique seems relatively useful if we consider the experimental results in Section 4. These experiments show for instance that the number of pure integer variables (those having u i > 1) decrease on average from 70% to 40% for the correlated instances and from 38% to 21% for the squared instances.

Fixing some 0-1 variables to their optimal value

When applying the last pre-processing technique, the number of 0-1 variables has probably increased. Thus, it is natural to try to fix some of the 0-1 variables to their optimal value in order to decrease the problem size. Let a 0-1 variable, say x i , we first need to guess its value in the optimal solution. We use the value of x i in the best known feasible solution and try to prove that x i cannot have a different value in any optimal solution. Considering a set I of variables indices that all are supposed to be equal to 0 in an optimal solution, we add the following constraint to the problem:

i∈I x i ≥ 1
then we compute an upper bound UB of the modified problem using the method presented in [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF]. If the computed upper bound is strictly lower than the value of the best known feasible solution then we can conclude that all the variables indexed in I can definitively be fixed to 0. A similar constraint can be added for fixing variables to 1 instead of 0 as explained in [START_REF] Billionnet | An exact method based on lagrangian decomposition for the 0-1 quadratic knapsack problem[END_REF] [START_REF] Billionnet | An exact method based on lagrangian decomposition for the 0-1 quadratic knapsack problem[END_REF].

The size of the set I is an important parameter for the success of such a fixation method. Choosing |I| = 1 comes down to fix variables one by one, and choosing |I| too large generally fails since no fixation can be done (the quality of the upper bound does not allow us to simultaneously fix all the variables indexed in I when I is too large). Experiments show that for (QMKP ) and the bound used to solve it, a good compromise consists in choosing |I| = 2.

This procedure allows us to fix on average 51% of the 0 -1 variables. However it appears much more time-consuming than the two previous ones. It can sometimes constitute more than 10% of the whole CPU-time necessary to find the exact solution using the branch-and-bound procedure.

Computational results

The computational performance of the four branch-and-bound procedures was tested through a set of 100 randomly generated squared problems (i.e. n = m) and correlated problems (i.e. c j = m i=1 a ij and d j = c min /2, where c min is the minimum of all c j values). The correlated problems are well-known to be more difficult to solve in practice for 0 -1 linear multidimensional knapsack problem (MKP ), which is a special case of (QMKP ), than squared instances. The number of variables take their values in the set {100, 500, 1000, 1500, 2000}, with 10 replications per n-value. As in [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF] ( [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF] The percentage of pure integer variables (with u j > 1) rises 38.6% on average for squared instances rather than it is equal to 70% on average for correlated problems. The average value of the bound u j for the pure integer variables reaches 21.2 with a standard deviation 2.24 over 50 instances for squared problems and rises 54.1 on average with a standard deviation 6 over 50 for correlated problems.

Our branch-and-bound as well as DMS were coded in C language whereas the optimal solution provided by SBB and LBB were got using a commercial solver ILOG-Cplex9.0. Simulations were run on a bi-xeon 3.4 Ghz with 4Go of main memory.

General comments on the comparison of the computational time of the four methods

Table 1 displays, for the four exact solution methods mentioned in this paper, the average computational time in CPU seconds over 10 replications for each problem type and size. We limited to 10800 seconds (3 hours) the solution time.

The results in Table 1 indicate clearly the poor performance of DMS which was not

Cahiers du LAMSADE able to reach the optimum in the chosen limit time for all problems types with 500 variables and more. It is proved in [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] (Quadri et al.) that is due to the fact that DMS employs a very time consuming local descent search method to obtain the optimal surrogate multiplier w * (see Sections 2 and 3).

Squared instances. Our branch-and-bound clearly outperforms the three other procedures. For large scaled instances (n ≥ 1000) our exact solution method is approximately 4 times quicker than the second best approach LBB and it is almost 7 times faster than SBB. This conforts the ability of our method to solve large sized problems in a very competitive time with an average of 5 ′′ 05 minutes (305 seconds) for the 2000-variables instances.

Correlated instances. As expected the correlated problems are difficult to be solved by the four exact methods. The size of the instances only up to 1000 variables and constraints. Nevertheless, concerning 500-variable problems LBB is the most appropriate algorithm taking 10 ′′ 00 minutes on average to find the optimum. Our branch-and-bound still solves the same instances in a competitive CPU time (2 times slower than LBB).

Analysis of the experiments results

The improvement capability of our branch-and-bound can be explained by three features, namely: (i) the feasible solution, (ii) the upper bound and (iii) the pre-processing procedures.

Our feasible solution (see [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF]. Actually, providing to our branch-and-bound algorithm another feasible solution (of poorer quality) did not significantly debase its solution time. Consequently, the good quality of the initial feasible solution does not clearly explain the performance of our exact solution method.

Our upper bound and pre-processing procedures: squared instances. The impact of both the upper bound we proposed in [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] and the pre-procedures used clearly appear. Indeed, our upper bound is always closer to the optimum than the three other utilized in DMS, LBB and SBB. Moreover, this bound takes about 10 seconds on average to be computed. On the other hand, our method includes part of the procedure of [START_REF] Hammer | Constraints pairing in integer programming[END_REF] [START_REF] Hammer | Constraints pairing in integer programming[END_REF] to reduce the bounds u j of the pure variables. This actually leads to convert many pure integer variables into 0-1 variables. The average proportion of pure integer variables decreases from 38% to 21.02%. The fixation technique eliminates 50.25% of variables which value is fixed to 1. Finally, the search of redundant constraints allows to keep 48% of the initial constraints. Consequently, both the upper bound method and the pre-procedure techniques are very effective for squared instances.

Our upper bound and pre-processing procedures: correlated instances. The upper bound is of poor quality in comparison with the result obtain for the squared problems.

10

Cahiers du LAMSADE Nevertheless, the relative gap is on average 20% and the bound is computed in 1 ′′ 30 on average (see [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF]). On the other hand, the pre-procedure techniques are quite well effective. Indeed, 56.6% of constraints can be removed on average, 27% of variables are fixed to their bound. Before starting the pre-procedure process, only 30% of variables are binaries. The impact clearly appears: 60% of variables are 0 -1 after applying the techniques. In spite of the fact that these results are of good quality, our branch-and-bound does not solve 1000-variable problems faster than LBB.

Conclusion

We develop in this paper a branch-and-bound algorithm to solve the integer quadratic multidimensional knapsack problem. The upper bound and the pre-procedure techniques that we incorporate allow us to solve large-sized squared instances, up to 2000 variables and constraints. The classical branch-and-bound, which is usually used to solve such convex problems is of poor quality as well as the method proposed by Djerdjour et al. (1988) [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF]. Moreover, the method suggested by [START_REF] Mathur | A branch and bound algorithm for a class of nonlinear knapsack problems[END_REF] (Mathur and Salkin, 1983) we extended to the case of (QMKP ), which has never been utilized to solve (QMKP ) directly, outperforms the three other branch-and-bound concerning the correlated problems.

Table 1 :

 1 integer coefficients a ij , c j , d j were uniformly drawn at random Average computational time of the four methods for each problem type Coefficients b i and u j are integers uniformly distributed such that 50 ≤ b i < n j=1 a ij u j and 1 ≤ u j ≤ ⌈ c j 2d j ⌉, where ⌈x⌉ denotes the smallest integer greater than or equal to x.

	8

Cahiers du LAMSADE

Cahiers du LAMSADE