Frederic Decremps

Simon Ayrinhac

Michel Gauthier

Daniele Antonangeli

Marc Morand

Yiuri Garino

Paraskevas Parisiades

Frédéric Decremps

Sound velocity and equation of state of liquid Cesium at high pressure and high temperature

Keywords: numbers: 62.50.+p, 62.60.+v, 47.35.Rs, 65.40.De, 61.10.Nz, 61.20.-p, 61.25.Mv

I. INTRODUCTION

Alkali metals are chemically considered as archetypal examples of simple liquids at ambient pressure [START_REF] Ingebrigtsen | [END_REF] . At higher densities, they however depart from their single free-electron behavior, showing a sequence of symmetrybreaking transitions which is well known to exhibit richness 2,3 (many phases), complexity [4][5][6][7] (low-symmetry structures, collective excitations), and puzzling mechanism 8,9 (driven by core electrons or zero-point contribution). Recently, the melting curves and the equation of state of some of the group-I elements have also been determined over a large pressure and temperature ranges, showing unexpected behaviors 10,11 . However, both experimental and theoretical difficulties still prevent extensive studies of their fluid states under high pressure. Among the many hardships, we can mention the existence of diffusion and relaxation processes within alkali elements, or their high chemical reactivity with consequent complications in the containment under extreme conditions, which result in a quite limited bibliography.

Solid cesium has been pioneeringly studied by Bridgman [START_REF] Bridgman | Proc. Am. Acad. Arts Sci[END_REF] , who discovered two consecutive phase transitions nearly at 2.3 GPa and 4.5 GPa. At 300 K, Cs is bodycentered cubic (bcc, Cs-I), stable up to 2.3 GPa, where it transforms to the face-centered cubic (fcc) Cs-II phase. An orthorhombic Cs-III exists over a very narrow pressure range 3 (between 4.2 and 4.3 GPa), which then transforms to the non-close-packed tetragonal Cs-IV (stable up to 12 GPa). While the bcc-to-fcc phase transition is purely structural, the transformation around 4.2 GPa has an electronic character [START_REF] Jayaraman | [END_REF]14 , where conduction electrons are transferred from the 6s to the 5d band.

The high pressure behavior of solid Cs has been largely studied over the years as this element is one of the most compressible substances over the whole alkali family (at 10 GPa, it is compressed to about one third of its volume at ambient pressure 15 ). As a consequence, Cs is advantageously expected to experience at relatively low pressure the same effects other less compressible monoatomic liquid metals undergo at much higher pressure, as lithium 10 . This hypothesis is validated through many experimental observations, as the existence of a bcc-to-fcc phase transition, of common complex structures (i.e. the orthorhombic one), or as the presence of a sequence of maxima and minima in the melting curve. In the liquid state, and mainly because of the technical difficulties mentioned above, only a couple of studies have been published on Cs. In the study of Tsuji et al. 16 , the pressure evolution of l-Cs has been followed through the modification of the structure factor S(Q). They observed changes on both the shape and the intensity of S(Q), suggesting the existence of two liquid-liquid transitions (LLT). A first transformation was seen to occur at 2.0 GPa, while a second one is suggested between 3.0 and 4.3 GPa, pressure range where a slender decrease of the S(Q) intensity is observed. However, such exciting conclusions have been derived on the basis of only four experimental data points, all collected at different temperatures. In addition, the measurement of S(Q) was experimentally limited to about 7 Å-1 , which hinder a reliable extraction of the pair distribution g(r), coordination number C N N , or of the atomic density ρ from experimental data. Subsequent more advanced xray diffraction measurements by Falconi et al. 17 came to different conclusions. Here, many data points have been recorded along two different isotherms, at 493 and 623 K. The main outcome of this work is the occurrence of only one single LLT, at 3.9 GPa, characterized by a very large density jump (17%), and a coordination number going down from 12 to 8. These results are also supported by ab initio simulations performed one year later by the same group 18 . The common underlying hypothesis of these works is a close similarity between the behavior of the liquid and what observed within the crystalline state, say the existence of dsp 3 electronic hybridization. However, the most recent experimental work carried out by x-ray absorption (see Hattori et al. 19 ) do not support any abrupt density jump at least up to 5 GPa and argues for a progressive 6s-5d electrons transfer.

II. EXPERIMENTAL METHODS

Experimentally, combined picosecond ultrasonics technique and diamond anvils cell (DAC) 20 has been proven to overcome many of previous technical barriers, and now enable to study subtle changes in liquid metals properties at high densities 21 . Using such state-of-the-art approach, we have here determined the pressure evolution along a 500 K isotherm of the l-Cs sound velocity with precision better than 1%. High temperature was generated through the use of a resistive external heater surrounding the whole DAC. The temperature was regulated using an electronic module and measured with an accuracy better than 1 K by two K-type thermocouples glued on each anvil. Using a glove box, ultra-pure Cs from Sigma Aldrich (99.99 %) was loaded fully embedded into a rhenium gasket hole of 250 µm diameter placed in a DAC equipped with 600 µm culet size diamonds.

Our acoustic set-up, described in reference [ 22 ], is based on the use of an ultrashort pulse of 60 fs generated every 12.554 ns by a Ti:Sapphire laser operating at λ = 800 nm. The laser beam is split into pump and probe beams. The pump is focused on one surface of the sample (focused spot of about 3 µm) through a diamond window and absorbed in a length scale ξ (≈ 36nm) whereas the probe is focused on the opposite side through the other diamond window. As soon as the pump laser pulse reaches the surface, it creates a sudden and small temperature rise ∆T (less than 10 K) which relaxes by launching an acoustic strain field (with frequency typically around the GHz in a metallic liquids) propagating at the sound velocity v l .

In a pure thermo-elastic model 23,24 , the time and space reflectance change δr(t) of the probe is a function of the photo-elastic coefficient ∂ ñ/∂η (where ñ is the sample refractive index, and η the stress generated by thermal expansion) and the surface displacement along the propagation axis z (u

0 (t) = +∞ 0 η(z, t)dz) : δr(t) r 0 = 2ik 0 n d +∞ 0 η(z, t)dz + ∂ ñ ∂η 2ñ n 2 d -ñ2 +∞ 0 η(z, t)e 2ik0 ñz dz (1)
where k 0 is the laser wave vector and n d the refractive index of diamond.

To summarize, after propagation across the sample both thermal and acoustic effects alter the optical reflectivity of the sample in two ways : the photo-elastic effect and the surface displacement (as the acoustic echo reaches the surface). The first modification contributes to the change of the intensity of the reflectivity and its phase shift, whereas the second one only modifies the phase of the reflectivity signal.

We performed two different runs with two different sample loadings. In both cases, pressure was increased to the maximum value (5 GPa) and data have been collected downstroke. The temporal method (described in a previous article 22 ) enables to extract the travel time ∆t corresponding to a single way of the acoustic wave into l-Cs. Sound velocity was then determined through the measurement of ∆t during decreasing pressure at continuous rate of the order of -0.02 bar/min on the membrane DAC. Pressures were determined from the SrB 4 O 7 : Sm 2+ fluorescence line shift before and after collection of each acoustic scope (pressure uncertainty given by symbols sizes in all figures). Using the imagery method 22 , the gasket thickness was determined simultaneously with the sound velocity at two pressures, 4.8 GPa and 2.3 GPa, leading in both cases to a constant value of e = 20(2)µm. Moreover, by white light interferences, we also estimated the thickness of the recovered gasket at ambient conditions to be 21(1)µm. A constant thickness upon decompression is consistent with many other experimental observations 22,25,26 and has been explained through the study of plasticity processes inside the rhenium gasket 27 under relaxing stresses.

III. RESULTS AND DATA ANALYSIS

The sound velocity determined from our measurements of travel time as a function of pressure is in agreement with an extrapolation of the low pressure ultrasonic data from Shaw 28 .

Fig. 1 shows the pressure evolution of of the l-Cs sound velocity at a constant temperature of 500 K. The linear dependence, expected for simple metals, only stands up to about 0.3 GPa. The low frequency limit of the sound velocity measured using inelastic x-ray scattering at 1 GPa and 493 K (v=1.18 km.s -1 , see Ref 5 ) is somewhat lower but in overall agreement with present adiabatic sound velocity. At higher pressures, the behavior becomes highly non-linear, with a flattening and a maximum at 2.0 GPa (pressure value in the vicinity of the bcc-fcc transition in the solid), but without discontinuity in the sound speed.

A further anomaly is observed between 2 and 4 GPa, where the velocity of the longitudinal wave decreases with pressure. Interestingly, this quite unusual behavior occurs over a pressure range where the liquid is denser than the solid [START_REF] Jayaraman | [END_REF] . Likewise, but to a lesser extent, we here emphasize that this softening was also present in the solid Cs-II phase between ∼3.5 GPa and 4.2 GPa, as reported by Voronov et al. 29 (see Fig. 1). This peculiar evolution is thermodynamically authorized, and can be here understood taking into account the existence of an hybridization between s and d orbitals. In a same manner, pure Ce is another well known example 30,31 , where the 4f -electron delocalization is at the origin of the reduction of the bulk modulus with pressure, an anomaly which is also observed well prior to the phase transition. In the present case, a progressive s-d hybridization in Cs is thus likely to be at the origin of the observed elastic softening occurring up to 4.0 GPa, pressure at which the sound velocity starts again to increase. Here again, similar behavior is observed in the solid Cs phase 29 , at the same pressure range where a structural phase transformation occurs in the solid phase below 500 K.

In order to discuss the electronic nature of the two consecutive extrema (the maximum at 2.0 GPa, and the minimum at 4.0 GPa), we can exploit the complementary of the two detection methods.

In both interferometric and reflectometric set-up, the shape of the strain depends on the acoustic impedance of the diamond anvils Z d = ρv l and the sample Z (where ρ is the density and v l the longitudinal sound velocity) via the acoustic strain reflection coefficient r ac = (Z d -Z)/(Z d + Z). In the present case r ac is large and positive (≈ 0.85), leading to a unipolar strain pulse shape in a simple thermoelastic generation theory. Moreover, since the laser probe is absorbed on a small ξ range, equation 1 becomes:

δr(t) r 0 ≈ 2ik 0 n d (e -v l t/ξ -(1 -r ac ))ξη 0 /2 + ∂ ñ ∂η 2ñ n 2 d -ñ2 v l te -v l t/ξ η 0 /2 (2)
The interferometric configuration allows the determi-nation of the imaginary part of the reflectivity change:

( δr(t) r 0 ) ≈ 4k 0 n d u 0 (t) 2 + 4k 0 n d v l t η(0, t) × ( ∂n ∂η n -∂κ ∂η κ)(n 2 d -(n 2 -κ 2 )) -( ∂n ∂η κ + ∂κ ∂η n)2nκ (n 2 d -(n 2 -κ 2 )) 2 + (2nκ) 2 (3)
We here emphasize that the change in phase of ∆r(t) (of about 10 -7 ) is generally assumed to be mainly due to a surface displacement u 0 (t) (as small as 10 fm). Within the reflectometry configuration, the variation of reflectivity as a function of time is detected through the direct measurement of the intensity modification of the probe. The signal is thus given by the real part of equation 2 as:

( δr(t) r 0 ) ≈ 4k 0 n d v l t η(0, t) × ( ∂n ∂η κ + ∂κ ∂η n)(n 2 d -(n 2 -κ 2 )) + ( ∂n ∂η n -∂κ ∂η κ)2nκ (n 2 d -(n 2 -κ 2 )) 2 + (2nκ) 2 (4)
The pulse profiles corresponding to equations ( 4) and ( 3) are shown in Fig. 2 for the two pressure ranges of interest around 2 and 4 GPa respectively. The pulse shape observed by interferometry does not significantly change under pressure, it only shifts. The same behavior is observed on the optical signal measured using the reflectometric configuration at 2.0 GPa ; on the contrary, it is largely modified around 4.0 GPa (change of sign).

IV. DISCUSSION

The pressure value of 2.0 GPa, where we document a maximum in sound velocity for the l-Cs, closely corresponds to CsI-CsII solid-solid phase transition, known to be purely structural (from eightfold coordinated bcc structure to 12-coordinated fcc structure 2,3 ). Furthermore, an analysis of the x-ray diffraction data in l-Cs by Falconi et al. 17 shows a plateau in the evolution of the coordination number from ambient conditions up to 2.0 GPa (pressure after which C N N begins to decrease), an observation not discussed by the authors but which could be either related to a pre-transitional effect ahead of the density change at 4 GPa (Falconi's point of view) or to the occurrence of a distinct transition pressure at 2 GPa. This last assumption would support structural nature of the anomaly in the liquid state above 2.0 GPa probably related to the fact that (as observed for l-Rb 7 ) l-Cs is not a simple liquid anymore and long-range repulsion have to be taken into account.

More complex is the analysis of the data at 4.0 GPa as change in the sign of only reflectivity is related to the relative values of the l-Cs refractive index and its of diamonds anvil. From ambient to low pressures, the refractive index of cesium is weaker than the diamond one, whereas at a moderated pressure due to the low compressibility of diamond and the huge compressibility of cesium the opposite scheme is expected. If the optical absorption of cesium is significant, it would smoothly go down to zero in intensities in both interferometric and reflectivity set-ups. This is clearly not what is here observed, with a sharp phase change of the reflectivity shape.

Nothing in equation 4 can account for a such abrupt change of the reflectivity signal without the same abrupt variation on the optical parameters n, κ or on the elastooptical ∂κ/∂η and ∂n/∂κ. This observation suggests that the change of shape (i.e. of signal phase) at 4.0 GPa, concomitant to the second extrema of the v(P ) evolution in l-Cs, signs a sudden modification either of the complex optical index or of the complex photo-elastic coefficient (or both) of the sample itself, thus pointing to an electronic nature of the transition.

An hypothesis would be that the electronic-character of a possible liquid-liquid transition observed by the present study finds its twin-image within the solid phase diagram, where a transition around 4.2 GPa is accompanied by abrupt changes in resistivity [START_REF] Jayaraman | [END_REF] , phenomenon attributed to the collapse of the 6s electronic orbital onto the 5d orbitals (electron transfer).

Such a subtle transformation within the liquid state should come with smooth discontinuities in the fluid equation of state V (P ), difficult to be detected by diffraction. Acoustic measurements are known as a very reliable alternative, since sound velocity is very sensitive to subtle changes in long-range order.

As illustrated in Fig. 3, the evolution of the liquid density with pressure along an isotherm at 500 K (extracted from the present sound velocity measurements on the basis of exact thermodynamic relations, an approach that have been already proven for many different metallic liquids 22,26 ) overall well compares with most recent density determination by x-ray absorption technique 19 , at least to the extent that any sharp discontinuity in density is ). The maximal uncertainties associated with the relative densities ∆ρ/ρ is estimated of about 2% 22,26 . The two black stars correspond to solid densities 29 at the pressure where two maxima is observed on the melting line, where both solid and liquid phases have the same density. We here emphasize the clear agreement between our data and those from Hattori 19 .

observed for increasing pressure, note even across liquidliquid transitions. Fig. 3 clearly emphasizes that a huge anomaly on the pressure dependence of the sound velocity does not necessarily comes with a clear effect on the equation of state. Indeed, while the pressure dependence of the volume is associated to the first derivative of the internal energy, the sound speed vs pressure is directly related to the second derivative with respect to the strain.

V. CONCLUSION

In summary, picosecond acoustics measurements on l-Cs under extreme conditions have provided experimental evidence of an S-shaped pressure dependence of sound velocity, with a maximum at 2.0 GPa and a minimum at 4.0 GPa. The first singularity could be related to a local change of the liquid structure, whereas present data do not provide a conclusive evidence for such behavior. The second anomaly (minimum at 4 GPa) is likely correlated to modifications of the electronic properties, as argued from the optical reflectivity measurements. By and large, the occurrence of such behavior within the liquid phase, never observed up to now, shows that under pressure l-Cs may mimic its solid phase, though at lower corresponding densities, as expected by the quasicrystalline paradigm, speculation which has to be tested using further simulation or experimental data.

FIG. 1 .

 1 FIG. 1. (color online) Longitudinal wave velocities of l-Cs as a function of pressure for the present work (T=500K, two runs, black and red open circles ; dotted line, as guides for eyes), plotted along with low-pressure ultrasonic data on l-Cs at 500 K from Ref 28 (black line) and ultrasonic measurements on solid-Cs at 300 K from Ref 29 (crosses).The maximal uncertainties associated with the relative sound velocity ∆v l /v l is less than 0.5%22,26 .

FIG. 2 .

 2 FIG. 2. (color online)Reflectivity change of l-Cs at 500 K as a function of the optical probe-pulse time delay. The modification of the optical reflectivity due to the acoustic strain has been recorded around 2 GPa using two types of detection, reflectometry (a) and interferometry (b). Same but around 4 GPa are given in (c) and (d) respectively. The pulse shape qualitatively varies (shifted in phase by about π) only in the vicinity of 4 GPa and using a reflectometric detection.

FIG. 3 .

 3 FIG.3. (color online) Density (ρ) of l-Cs at 500 K as a function of pressure deduced from present measurements, and compared to previous studies (x-ray diffraction results from Falconi 17 and x-ray absorption from Hattori19 ). The maximal uncertainties associated with the relative densities ∆ρ/ρ is estimated of about 2%22,26 . The two black stars correspond to solid densities 29 at the pressure where two maxima is observed on the melting line, where both solid and liquid phases have the same density. We here emphasize the clear agreement between our data and those from Hattori19 .


Arnaud Liefooghe
email: arnaud.liefooghe@univ-lille1.fr

Manuel López-Ibáñez
email: manuel.lopez-ibanez@manchester.ac.uk

Luís Paquete
email: paquete@dei.uc.pt

Sébastien Verel
email: verel@lisic.univ-littoral.fr

Dominance, epsilon, and hypervolume local optimal sets in multi-objective optimization, and how to tell the difference

Keywords: Multi-objective combinatorial optimization, Local search, Local optima, Set-based multi-objective optimization, Quality Indicators

INTRODUCTION

Local search methods operate over a search landscape defined by a triplet (S, ≼, N ), where S denotes a finite, or countably infinite, set of solutions (the search space), ≼ is a preorder on S (the preference relation) and N is a mapping N : S → 2 S (the neighborhood relation).

For any pair of solutions s, s ′ ∈ S, s ≼ s ′ denotes that solution s is at least as preferred as solution s ′ . For a given solution s ∈ S, the set N (s) is the neighborhood of s and an element s ′ ∈ N (s) is a neighbor of s. The most basic local search algorithm, commonly known as hill-climbing, starts from an initial solution s ∈ S, and iteratively improves the current solution by exploring its neighborhood and moving to an improving neighboring solution. When no improving neighbor is available, the algorithm is trapped in a local optimum. Hence, based on the triplet (S, ≼, N ), we can define the notions of local optimum (LO) and strict local optimum (sLO).

Although the concepts of (strict) LO are well-studied in singleobjective optimization, their extension and properties in a multiobjective context are much less understood. The difficulties arise from the fact that the search space S is actually the set of all mutually nondominated sets of feasible solutions, possibly bounded in size, thus the neighborhood can be seen as operating on sets. Moreover, the preference relation is usually defined in terms of Pareto dominance, but it may also be any other quality indicator that induces a preorder, such as the hypervolume. The implications of these different aspects are still open to investigation and may guide the design of new multi-objective algorithms, since even global search methods, such as multi-objective evolutionary algorithms, can be seen as iteratively identifying better-quality local optima, without any guarantee of finding a global optimum. Indeed, a global optimum is also a local optimum for any neighborhood relation.

Paquete et al. [START_REF] Paquete | On Local Optima in Multiobjective Combinatorial Optimization Problems[END_REF] provided definitions of local optimality with respect to solution-and set-dominance, and related them to the convergence point of multi-objective local search. Verel et al. [START_REF] Verel | Set-based Multiobjective Fitness Landscapes: A Preliminary Study[END_REF] introduced a set-based fitness landscape and measured ruggedness and non-linearity for fixed-size sets of solutions, using the hypervolume as the preference relation. That study was later extended to the quality of LO-sets and the convergence profile of hypervolumebased local search under different notions of set neighborhoods [START_REF] Basseur | On Set-based Local Search for Multiobjective Combinatorial Optimization[END_REF].

More recently, López-Ibáñez et al. [START_REF] López-Ibáñez | Local Optimal Sets and Bounded Archiving on Multi-objective NK-Landscapes with Correlated Objectives[END_REF] showed that the size of sets that are LO with respect to dominance (Pareto local optimum sets or PLO-sets) is exponentially correlated with the number of objectives or with their degree of conflict, while variable interactions have a minor effect. In addition, they showed that the estimated number of PLO-sets is also correlated with the number of objectives or their degree of conflict. It is also known that the number of PLOsolutions increases linearly with the problem non-linearity [START_REF] Verel | On the Structure of Multiobjective Combinatorial Search Space: MNK-landscapes with Correlated Objectives[END_REF], but that the number of unbounded PLO-sets decreases [START_REF] López-Ibáñez | Local Optimal Sets and Bounded Archiving on Multi-objective NK-Landscapes with Correlated Objectives[END_REF]. Finally, the use of bounded size archives [START_REF] López-Ibáñez | On Sequential Online Archiving of Objective Vectors[END_REF] does not change these trends, but increases the number of bounded PLO-sets significantly by a factor that depends on the size of the unbounded PLO-sets. However, so far, no work has examined how various definitions of local optimality relate to each other. In this paper, we extend previous work on LO-sets by considering various types of local optima, induced by different set preference relations (dominance, epsilon, hypervolume), and by analyzing their properties.

The paper is organized as follows. Section 2 defines the concept of (strict) LO-sets in a way the matches the usual definition of LO solutions in the single-objective case, but allows the use of set preference relations based on dominance or quality metrics. In addition, we describe an adaptive walk for sampling such LO-sets. Section 3 describes the multi-objective nk-landscapes and the experimental setup used for our experimental study. Section 4 describes the experiments carried out in this paper and the conclusions that can be extracted from them. Finally, we summarize our main findings and list remaining open questions in Section 5.

LOCAL OPTIMAL SETS

Multi-objective Optimization. Let us assume that we are given an optimization problem characterized by a pair (X , f ), where X is the set of feasible solutions (the decision space) and f is the objective function f : X → R m , to be maximized. In multi-objective optimization (m > 1), one is often interested in finding more than one optimal solution. Given two solutions x, x ′ ∈ X , we say that x weakly dominates

x ′ (x ≼ dom x ′ ) if f i (x ′ ) ⩽ f i (x) for all i ∈ {1, . . . , m}.
In terms of Pareto optimality, the goal is to find a set X ⋆ ⊆ X for which there exists no solution x ∈ X such that x ≼ dom x ⋆ for all x ⋆ ∈ X ⋆ . The set X ⋆ is the Pareto set, and its image in the objective space is the Pareto front.

Set Preference Relations. In set-based multi-objective optimization [START_REF] Zitzler | On Set-Based Multiobjective Optimization[END_REF], the search space can be defined as the collection of sets of feasible solutions (feasible sets): Σ ⊂ 2 X . We restrict to sets of mutually nondominated solutions and we consider that the cardinality of the sets is bounded by µ ∈ N + , that is, we define

Σ := {A ∈ 2 X : |A| ⩽ µ ∧ ∀x, x ′ ∈ A, x x ′ ⇒ ¬(x ≼ dom x ′ )}. Notice, however, that if the Pareto set X ⋆ is larger than µ, then X ⋆ Σ.
The aforementioned dominance relation among solutions can naturally be extended to sets. Given two sets A, B ∈ Σ, A weakly dominates B (A ≼ dom B), if for all b ∈ B there exists an a ∈ A such that a ≼ dom b. The quality of a set A ∈ Σ can also be measured as a single scalar value through a unary quality indicator I : Σ → R. We consider the (additive) epsilon indicator (I eps ), to be minimized, and the hypervolume indicator (I hv ), to be maximized [START_REF] Zitzler | Quality Assessment of Pareto Set Approximations[END_REF]. Interestingly, I eps (resp. I hv ) is order-preserving (resp. strictly order-preserving) with respect to the weak-dominance set preference relation [START_REF] Zitzler | Quality Assessment of Pareto Set Approximations[END_REF]:

A ≼ dom B ⇒ I eps (A) ⩽ I eps (B) , (1)
(A ≼ dom B) ∧ ¬(B ≼ dom A) ⇒ I hv (σ ) < I hv (σ ′ ) . (2)
We also define the corresponding set preference relations:

A ≼ eps B ⇐⇒ I eps (A) ⩽ I eps (B) , (3)
A ≼ hv B ⇐⇒ I hv (A) ⩾ I hv (B) . (4)
Local Optimality. Let A, B ∈ Σ. We define the strict partial order ≺ of a given partial order ≼ as:

A ≺ B ⇐⇒ ¬(B ≼ A) ∧ (A ≼ B) . (5)
Sets A and B are incomparable if neither

(A ≺ B) nor (B ≺ A) holds.
Given a collection of sets Σ, a preorder (preference relation) between sets ≼, and a neighborhood relation between sets N : Σ → 2 Σ , the definition of local optima can be adapted as follows.

Definition 2.1 (Local optimal set, LO-set (Σ, ≼, N)). A set A ∈ Σ is a local optimal set iff ∀B ∈ N(A) \ A, ¬(B ≼ A). Definition 2.2 (Strict LO-set, sLO-set (Σ, ≼, N)). A set A ∈ Σ is a strict local optimal set iff ∀B ∈ N(A) \ A, A ≺ B.
Under the definitions above, a Pareto local optimum set [START_REF] López-Ibáñez | Local Optimal Sets and Bounded Archiving on Multi-objective NK-Landscapes with Correlated Objectives[END_REF][START_REF] Paquete | On Local Optima in Multiobjective Combinatorial Optimization Problems[END_REF] is an LO-set where ≼ is the set-dominance relation ≼ dom . It would be a strict LO-set under the same definitions if there is no B ∈ N(A) such that A and B are incomparable. As another example, a multiobjective local search based on hypervolume (≼ hv ) stops on an LO-set A ∈ Σ if there exists no neighboring set B ∈ N(A) that has a larger hypervolume value. It stops on a strict LO-set if all neighboring sets have a (strictly) smaller hypervolume value than the current set. Therefore, the proposed definitions allow us to compare various types of LO-sets under a common terminology.

A Walk to Sample Local Optimal Sets. Following the definitions of strict and non-strict LO-sets, we define a set-based adaptive walk (Alg. 1), where the first improving neighboring set encountered during neighborhood exploration is accepted. This set-based local search is analogous to a classical single-objective first-improvement local search (or hill-climber). In Alg. 1, µ initial solutions are randomly generated and added to a nondominated archive A, which represents the current solution-set. Then, a main loop explores each neighboring solution x ′ of each element in A in a random order without replacement. If this neighbor x ′ is nondominated with respect to any solution in A and the cardinality of A is smaller than µ, then A can be trivially improved by adding solution x ′ . Otherwise, the algorithm explores all sets that are constructed by replacing one solution from A with x ′ . If the resulting set improves over A, it is accepted. In the case of a neutral walk, the solution is also accepted if the resulting set is incomparable with A. Otherwise, the procedure explores the next neighboring set. The main loop stops once all neighbors have been explored, returning a (possibly strict) LO-set, when a budget of solution evaluations has been consumed, or when there is a number of steps without any strict improvement. A step is here defined as a change in the current set, i.e., an iteration of the main loop (lines 5-19).

The proposed adaptive walk shares similarities with existing multi-objective local search methods. Compared against PLS [START_REF] Paquete | On Local Optima in Multiobjective Combinatorial Optimization Problems[END_REF]

EXPERIMENTAL SETUP

Multi-objective nk-Landscapes. We consider nk-landscapes as a problem-independent model of multi-objective multimodal landscapes [START_REF] Aguirre | Working principles, behavior, and performance of MOEAs on MNK-landscapes[END_REF][START_REF] Verel | On the Structure of Multiobjective Combinatorial Search Space: MNK-landscapes with Correlated Objectives[END_REF]. Candidate solutions are binary strings of size n and the objective function vector

f = (f 1 , . . . , f i , . . . , f m ) is defined as f : {0, 1} n → [0, 1] m such that each objective f i is to be max- imized.
As in well-established single-objective nk-landscapes [START_REF] Kauffman | The Origins of Order[END_REF], each separate objective function value f i (x) of a solution x = (x 1 , . . . , x j , . . . , x n ) is an average value of the individual contributions associated with each variable x j . Given objective f i , i ∈ {1, . . . , m}, and variable x j , j ∈ {1, . . . , n}, a component function f i j : {0, 1} k +1 → [0, 1] assigns a real-valued contribution for every combination of x j and its k epistatic interactions {x j 1 , . . . , x j k }. These f i j -values are uniformly distributed in [0, 1]. Thus, the individual contribution of a variable x j depends on its value and on the values of k < n other variables {x j 1 , . . . , x j k }. In this work, the epistatic interactions, i.e., the k variables that influence the contribution of x j , are set uniformly at random among the (n -1) variables other than x j [START_REF] Kauffman | The Origins of Order[END_REF]. By increasing the number of epistatic interactions k from 0 to (n -1), landscapes can be gradually tuned from smooth to rugged. We use the same epistatic degree and interactions for all the objectives. By construction, it is very unlikely that different solutions map to the same point in the objective space.

Parameter Settings. We generate 15 multi-objective nk-landscapes with the following settings. The problem size is set to n = 16, number of objectives m ∈ {2, 3, 5}, and problem non-linearity k ∈ {0, 1, 2, 4, 8}, that is, from linear to highly rugged landscapes.

We generate one instance independently at random for each combination of instance settings. We run the adaptive walk (Alg. 1) with respect to the set preference relations {≼ dom , ≼ hv , ≼ eps } and with various set cardinality bounds µ ∈ {2, 4, 8, 16, 32}. The reference set for computing I eps is the (exact) Pareto front. The reference point for computing I hv is set to (0, . . . , 0). We experiment with both neutral and non-neutral walks. In order to ensure a reasonable runtime for neutral walks, we set a maximum budget of 10 7 evaluations and a cutoff of 30 consecutive iterations of the main loop without improvement. The neighborhood relation among solutions (N ) is defined by the 1-bit-flip operator; i.e., two solutions are neighbors if the Hamming distance between them is one. We replicate each experiment 30 times with different random seeds.

EXPERIMENTAL ANALYSIS 4.1 Number of Local Optimal Sets

As a first question, we investigate the number of LO-sets of each type, that is, for each set preference relation (≼ dom , ≼ hv , and ≼ eps ) and either strict or non-strict definition (LO/sLO). Given previous results regarding Pareto local optimum sets [START_REF] López-Ibáñez | Local Optimal Sets and Bounded Archiving on Multi-objective NK-Landscapes with Correlated Objectives[END_REF], we expect the number of LO-sets to be affected by the number of objectives (m), the epistasis (k) and the cardinality bound (µ). However, we do not know how each type of LO-set is affected by these characteristics. Moreover, although we conjecture that some LO-sets of one type are also LO-sets of other types, their relative ratios are unknown. To answer these questions, after running the adaptive walk as described in the previous section, we simply count how many of the sets returned at the end of the runs satisfy the definition of each type of LO-set. Results are shown in Fig. 1 for selected settings. Results on other instances confirm the trends observed here.

The first observation is that non-neutral walks using a particular set preference relation always find a non-strict LO-set according to the same relation, in every run. That is, a walk based on ≼ dom (resp. ≼ eps , ≼ hv ) always falls into an LO ≼ dom (resp. LO ≼ eps , LO ≼ hv ). Moreover, the LO-set where a given walk falls into might be the same at different executions, as observed, for instance m = 2, k = 0 with µ = 32. This suggests that there is a single LO-set in this case, which is not a surprise because the corresponding nk-landscape is linear (k = 0) and its Pareto set cardinality is lower than µ = 32.

We did not notice any difference between neutral or non-neutral walks with ≼ hv , which suggests that neighboring LO-sets with the same hypervolume value are rare, thus there is no neutrality in the corresponding landscapes. Although we do not expect that real-world problems have many sets with the same hypervolume value, we cannot generalize this finding to any landscape since it is easy to think of artificial examples where two neighboring sets have equal hypervolume values. By contrast, we observe a large neutrality for ≼ dom and ≼ eps , as shown by the large differences between neutral and non-neutral walks in such cases. In fact, the neutral walk using ≼ dom is only able to find a sLO ≼ dom when µ is large, and when there are few objectives, e.g., for m = 2 and k = 8. We attribute this to a large non-linearity in the objective values in such cases, with many incomparable neighboring sets, which seem to increase the number of strict LO-sets. By contrast, the neutralwalk using ≼ eps is only able to find a sLO ≼ eps when µ is small and/or when non-linearity is small (k = 0), whereas the neutralwalk using ≼ hv is always able to find a sLO ≼ hv , as already reported above. The probable reason is that there are more neighboring sets with the same epsilon value and/or that the hypervolume gradient is easier to optimize that of epsilon. Interestingly, when there are many objectives, and when µ is especially small relative to the size of the exact Pareto set, it appears to be difficult to obtain a LO ≼ hv with any method besides a walk based on ≼ hv .

To summarize, by comparing LO-sets under ≼ dom and ≼ hv , we conjecture that: sLO ≼ dom ⇒ sLO ≼ hv ⇒ LO ≼ hv ⇒ LO ≼ dom . Although we do not obtain any clear trend by comparing LO-sets under ≼ dom and ≼ hv with LO-sets under ≼ eps , we conjecture that sLO ≼ dom ⇒ LO ≼ eps . We also suspect that there are slightly more LO ≼ eps than LO ≼ hv , given that the walk based on ≼ dom consistently finds more of those, but the difference seems to be rather small.

Finally, a general observation worth mentioning is that, whatever the set preference relation, the adaptive walk gets more easily trapped into an LO-set as the problem non-linearity k increases, and as the number of objectives m decreases.

Length of Adaptive Walks

As in single-objective optimization, the length of the adaptive walk provides an estimation of the number of LO-sets. The number of steps performed by the algorithm defines the length of the adaptive walk. This length is an estimator of the diameter of local optima's basins of attraction. Roughly speaking and assuming isotropy in the search space, the longer the walk, the larger the basins size, and the lower the number of local optima [START_REF] Kauffman | The Origins of Order[END_REF]. Fig. 2 reports the number of steps performed by each type of adaptive walk. In our experiments, the solution space has the same size for all instances; i.e. |X | = 2 n = 2 16 , whatever k and m. However, the number of candidate sets depends on the set cardinality bound µ and on the q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q m = 2 ; k = 0 m = 2 ; k = 2 m = 2 ; k = 8 m = 3 ; k = 8 m = 5 ; k = 8 dominance relations between solutions. For a given µ, the number of candidate sets is bounded by

µ i=1 |2 X | i = µ i=1 2 (2 16 ) -1 i
. Therefore, for a given instance, a larger value of µ induces an exponentially larger number of candidate sets. Of course, depending on the dominance relations between solutions, many candidate sets might be equivalent once dominated solutions are discarded.

We observe that the length of adaptive walks typically increases with µ. Therefore, a local search is more easily stuck when µ is small. This means that the absolute number of LO-sets decreases with µ. When relating that to the number of candidate sets, we argue that the proportional number of LO-sets is larger when µ is small, whatever the set preference relation. As expected, the length of adaptive walks decreases with the problem non-linearity k. As for singleobjective nk-landscapes, the larger k, the larger the number of local optima [START_REF] Kauffman | The Origins of Order[END_REF]. When considering the number of objectives m, we observe that adaptive walks runs longer as m increases, especially when µ is relatively large. A local search has a larger probability of getting stuck for two-objective landscapes than for three-and five-objective landscapes. This suggests that the number of LO-sets decreases with the objective space dimension.

When comparing neutral and non-neutral walks for a given set preference relation, we observe that neutral walks typically run longer. There are two potential explanations for this result: (i) a neutral walk may fail to identify a strict LO-set simply because it does not exist, explaining why the number of steps reaches the overall budget limit for some settings; and (ii) every strict LO-set under a given set preference relation is also an LO-set under the same relation, thus the number of sLO-sets is smaller or equal than the number of LO-sets. This is the case for ≼ dom and ≼ eps . Interestingly, the gap between the number of strict and non-strict LO-sets seems to decrease with µ for ≼ dom , whereas it increases for ≼ eps . In fact, for large sets, almost all LO ≼ dom are sLO ≼ dom , as also noticed in Fig. 1. We attribute this to the fact that it is more unlikely to come across a neighboring solution that is not dominated by the set when this set is larger. As already mentioned above, in the case of ≼ hv , there is no distinction between neutral and non-neutral walks for the considered instances, an LO ≼ hv is always a sLO ≼ hv .

Let us now compare non-neutral walks and non-strict LO-sets for different set preference relations. For m = 2 and µ ∈ {16, 32}, the length of the adaptive walk is roughly the same for all relations. They are the sole settings where the cardinality of LO-sets is actually smaller than the bound µ (not reported here due to space restriction), which is explained by the fact that µ is larger than the Pareto set in those cases. This suggests that there is no distinction between LOsets under the different set preference relations when µ has the same order of magnitude than the Pareto set, as also observed in Fig. 1. By contrast, for other instances, the length of the adaptive walk for ≼ dom is typically smaller than for ≼ eps , which is itself typically smaller than for ≼ hv . This gives us more evidence that, when µ is smaller than the Pareto set, we have more LO ≼ dom than LO ≼ eps , and more LO ≼ eps than LO ≼ hv . A multi-objective local search with bounded archive is then expected to get more easily trapped when comparing sets in terms of dominance rather than in terms of epsilon or hypervolume. On the contrary, a hypervolume-based local search is expected to perform more steps before being stuck.

Quality of Local Optimal Sets

In Fig. 3, we report the quality of the final set obtained by each walk on a selected subset of instances. The quality of the resulting sets is evaluated both in terms of the additive epsilon indicator (I eps ) and of the relative hypervolume deviation (I hvr ). The relative hypervolume deviation is computed as I hvr (A) := (I hv (R) -I hv (A))/I hv (R), where R is the Pareto set. Although a walk based on ≼ hv (resp. ≼ eps ) always outputs the best hypervolume (resp. epsilon) value, the indicator value of the final set is not necessarily the best one observed during the search process for walks that are based on a different set preference relation. In the next section, we will analyze the best indicator value obtained at different time steps.

Unsurprisingly, the quality of LO-sets always improves with higher set cardinality bound µ, for both hypervolume and epsilon. In fact, as suspected above, for all variants, the set found by each walk always maps to the Pareto set for the linear two-objective instance (k = 0, m = 2), as long as the cardinality bound is larger than the number of Pareto optimal solutions (µ = 32). This means q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q m = 2 ; k = 0 m = 2 ; k = 2 m = 2 ; k = 8 m = 3 ; k = 8 m = 5 ; k = 8 q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q m = 2 ; k = 0 m = 2 ; k = 2 m = 2 ; k = 8 m = 3 ; k = 8 m = 5 ; k = 8 that, whatever the set preference relation, there is only one LO-set for this setting: the Pareto optimal set. For all instances, the walk based on ≼ hv consistently converges to better LO-sets in terms of hypervolume. When analyzing LO-sets in terms of epsilon values, it is more difficult to distinguish between the walk based on ≼ hv and the (non-neutral) walk based on ≼ eps . However, a neutral walk based on ≼ eps often leads to better epsilon values for the most difficult instances (with large m and k), although in much more steps as depicted in Fig. 2. This once again emphasizes the high neutral degree induced by ≼ eps . As such, we argue that an epsilon-based local search will not necessarily converge to better epsilon values than a hypervolume-based local search, unless it explicitly handles equivalent sets in terms of epsilon. At last, the walks based on ≼ dom seem to converge to lower-quality LO-sets, in terms of both indicators, as the number of objectives increases. This confirms that dominance is probably not the best option to distinguish between candidate sets in many-objective local search.

Convergence Profile of Adaptive Walks

In order to better appreciate the anytime behavior of the walks under different settings, we report in Fig. 4 the convergence of the best-found indicator value for different budgets, measured in terms of a number of evaluations. This is different from Fig. 3, where only the quality of the final set was analyzed. It is worth noticing that we do not consider any restart mechanisms in our algorithm, and once an algorithm stops at a given iteration, it is assumed that the quality remains the same for subsequent ones.

First, we observe that a (non-neutral) walk under ≼ dom is only efficient when µ = 32 and m = 2, that is, when µ is larger than the Pareto set. Otherwise, the performance of such a walk is always very low, both in terms of epsilon and hypervolume. A walk based on ≼ eps follows the same trend according to hypervolume, although it is always slightly better. By contrast, it performs much better in terms of epsilon, although it is mostly outperformed by the walk under ≼ hv , except when µ is particularly small. The latter is actually never outperformed in terms of hypervolume, except for a few settings with a small µ and small m. It is also often the second-best approach in terms of epsilon, even consistently better than the former when µ ⩾ 8.

Regarding neutral walks, the one based on ≼ dom performs nicely for small µ values, but not so good for m = 5, which once again might explain the low performance of dominance-based search in many-objective optimization. Showing the opposite behavior, the neutral walk based on ≼ eps is often the best-performing approach in terms of epsilon, and second-best approach in terms of hypervolume, except for large µ and small m. It performs particularly well for m = 5, whatever the set cardinality bound. q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q m = 2 ; k = 0 ; mu = 32 m = 2 ; k = 2 ; mu = 32 m = # evaluations relative hypervolume deviation q q q q q neutral walk (dom) walk (dom) neutral walk (eps) walk (eps) walk (hv) q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q m = 2 ; k = 0 ; mu = 32 m = 2 ; k = 2 ; mu = 32 m = # evaluations epsilon q q q q q neutral walk (dom) walk (dom) neutral walk (eps) walk (eps) walk (hv)

Distance between Local Optimal Sets

As a last question, we go deeper into the comparison of LO-sets under different set preference relations by investigating their dissimilarity in the space of sets. In particular, we want to know how much different is a LO ≼ eps or a LO ≼ hv from a LO ≼ dom . We do not consider strict LO-sets in this section, since they do not necessarily exist for all settings, and since the success rate for the corresponding neutral walks is typically lower than 1.

Let us define the distance between a LO ≼ dom and a LO ≼ eps as the length (number of steps) required by a walk based on ≼ eps to reach a LO ≼ eps , while starting from a LO ≼ dom as an initial set. To do so, (i) we simply start by running a walk under ≼ dom until it falls into a LO ≼ dom , and then (ii) we run a walk under ≼ eps starting from the obtained LO ≼ dom . Only the steps performed in the second phase are taken into account to measure the distance. The distance between a LO ≼ dom and a LO ≼ hv follows the same reasoning, but using a walk under ≼ hv . This notion of distance gives how many 1-bit-flips, performed on any solution from the initial set, separates a set A from a set B. Thus, if dist(A, B) = d, then A may differ from B in d solutions, all connected at Hamming distance 1, or they may differ in a single solution with Hamming distance d.

The obtained distances are reported in Fig. 5. When compared against the walks that start from a random set, as reported in Fig. 2, the number of steps performed from a LO ≼ dom is lower by an order of magnitude. This means that a LO ≼ dom is much closer to a LO ≼ eps or a LO ≼ hv than a random set is with any of the three. The distance between a LO ≼ dom and a LO ≼ eps is often larger for medium µ values (µ ∈ {4, 8}) than for small and large values (µ ∈ {2, 16, 32}).

When considering the hypervolume, the distances from a LO ≼ dom to a LO ≼ hv are always larger than to a LO ≼ eps . When m = 2, these distances roughly follow the same trend as for LO ≼ eps , however, q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q m = 2 ; k = 0 m = 2 ; k = 2 m = 2 ; k = 8 m = 3 ; k = 8 m = 5 ; k = 8

CONCLUSIONS

In this paper, we empirically studied the properties of various types of LO-sets. Our results confirm previous findings and observations in multi-objective optimization, such as the fact that algorithms relying solely on dominance tend to perform worse for more than three objectives. We also observed that the number of LO-sets of any type increases with increasing ruggedness of the landscape, and with decreasing number of objectives and decreasing cardinality bound. Similar results were previously known for (bounded size) PLO-sets [START_REF] López-Ibáñez | Local Optimal Sets and Bounded Archiving on Multi-objective NK-Landscapes with Correlated Objectives[END_REF] and here we show that they are true for other types of LO-sets. In addition, we advance several hypotheses based on our experimental results. In particular, we conjecture that: sLO ≼ dom sLO ≼ hv LO ≼ hv LO ≼ dom LO ≼ eps which means that there are more LO ≼ dom than LO ≼ hv , but more sLO ≼ hv than sLO ≼ dom (except for the trivial case when the cardinality bound is larger than the actual size of the Pareto set, in such case there is no distinction between the various LO-sets). In addition to the implications above, we also observed that there are many more LO ≼ dom than LO ≼ eps , and slightly more LO ≼ eps than LO ≼ hv , the latter being perhaps the most surprising conclusion.

We conjecture that our findings regarding LO ≼ eps (resp. LO ≼ hv ) generalize to other LO-sets under any order-preserving (resp. strictly order-preserving) indicators. Our analysis should also guide the design of new multi-objective optimizers. For instance, we conclude that an epsilon-based local search does not necessarily converge to better epsilon values than a hypervolume-based local search, unless it explicitly handles sets that are equivalent in terms of epsilon.

Our conclusions provide at least two directions for further work. One direction should attempt to formally prove some of our conjectures, thus increasing our theoretical understanding of multiobjective landscapes. A second direction should try to extend our experimental analysis to additional problems, different neighborhoods and other order-preserving indicators, to corroborate that our conjectures indeed generalize as expected. Of particular interest is the extension of our work to LO-sets for continuous problems [START_REF] Kerschke | Towards Analyzing Multimodality of Continuous Multiobjective Landscapes[END_REF]. Furthermore, there are other factors that were not considered here, such as the size of the search space and the correlation between objectives.

Figure 1 :

 1 Figure 1: Number of each type of LO-set found by each type of LS walk (by column) for different instances (by row), depending on the set cardinality bound (µ). Results for neutral walk (hv) is not reported because they are the same as for walk (hv).

Figure 2 :

 2 Figure 2: Number of steps performed by each walk (colors) for different instances (non-linearity k and number of objectives m, by column), depending on the set cardinality bound.

Figure 3 :

 3 Figure 3: Final relative hypervolume deviation and epsilon value obtained by each walk (colors) for different instances (nonlinearity k and number of objectives m, by column), depending on the set cardinality bound.

2 1

 2 2 ; k = 8 ; mu = 32 m = 3 ; k = 8 ; mu = 32 m = 5 ; k = 8 ; mu = 32 m = 2 ; k = 0 ; mu = 8 m = 2 ; k = 2 ; mu = 8 m = 2 ; k = 8 ; mu = 8 m = 3 ; k = 8 ; mu = 8 m = 5 ; k = 8 ; mu = 8 m = 2 ; k = 0 ; mu = 2 m = 2 ; k = 2 ; mu = 2 m = 2 ; k = 8 ; mu = 2 m = 3 ; k = 8 ; mu = 2 m = 5 ; k = 8 ; mu =

Figure 4 :

 4 Figure 4: Convergence profile of hypervolume and epsilon for each walk (colors), for different instances (non-linearity k and number of objectives m, by column) and different set cardinality bound (µ, by row), depending on the number of evaluations.

Figure 5 :

 5 Figure 5: Number of steps performed by the walk to go from a LO ≼ dom to a LO ≼ eps and LO ≼ hv for different instances (nonlinearity k and number of objectives m, by column), depending on the set cardinality bound.

and

  Algorithm 1: Adaptive Walk Input : Set cardinality bound µ, neutral ∈ {true, false}, partial order ≼∈ {≼ dom , ≼ eps , ≼ hv } Output : Nondominated set A

	1 A ← ∅
	2 for i ← 1 to µ do
	3	x ← RandomSolution()
	4	A ← FilterDominated(A ∪ {x })
	5 repeat	// main loop
	6	for each x ′ ∈ {N (x) \ A | x ∈ A} do // random order
	7	A ′ ← FilterDominated(A ∪ {x ′ })
	8	if |A ′ | ⩽ µ then
	9	A ← A ′
	10	goto line 19
	11	for each x ′′ ∈ A do	// random order
	12	A ′ ← {A ∪ x ′ } \ {x ′′ }
	13	if (A ′ ≺ A) then	// A ′ better than A
	14	A ← A ′
	15	goto line 19
	16	else if neutral ∧ A ′ ≼ A then
	17	A ← A ′ // A ′ at least as good as A
	18	goto line 19
	19 until A is a (s)LO-set or no budget left or cutoff reached
	SEMO [5], we consider mutually nondominated sets of bounded car-
	dinality. The neighbors of a set are the same as those in SEMO [5];
	i.e., given A ∈ Σ, then B ∈ N(A) ⇐⇒ |B \ A| ⩽ 1 ∧ ∀b ∈
	B \ A, ∃a ∈ A such that b ∈ N (a) [2]. The main difference is that
	we explore neighboring sets without replacement, which allow us
	to detect when the walk falls into a (possibly strict) LO-set. As in
	single-objective local search, the proposed non-neutral adaptive
	walk always falls into an LO-set, whereas a neutral walk may either
	eventually fall into a strict LO-set, or terminate without reaching
	any type of LO-set. By using this adaptive walk, we can experi-
	mentally estimate the number, quality, and dissimilarity of various
	types of LO-sets, as shown below.

Acknowledgments. This work benefited from the COST action "Improving applicability of nature-inspired optimization by joining theory and practice" (ImAppNIO, CA15140, European Cooperation in Science and Technology).


Abdourahim Sylla
email: abdourahim.sylla@mines-albi.fr

Élise Vareilles
email: elise.vareilles@mines-albi.fr

Thierry Coudert
email: thierry.coudert@enit.fr

Michel Aldanondo
email: michel.aldanondo@mines-albi.fr

Laurent Geneste
email: laurent.geneste@enit.fr

E Vareilles

Offer Elaboration: New Confidence Indexes to take into account Uncertainty

Keywords: Bidding Process, Offer Elaboration, Systems Engineering, Uncertainty, Confidence Index (CI), Technology Readiness Level (TRL), Activity Risk Level (ARL), Human Factors Bidding Process, Offer Elaboration, Systems Engineering, Uncertainty, Confidence Index (CI), Technology Readiness Level (TRL), Activity Risk Level (ARL), Human Factors Bidding Process, Offer Elaboration, Systems Engineering, Uncertainty, Confidence Index (CI), Technology Readiness Level (TRL), Activity Risk Level (ARL), Human Factors Bidding Process, Offer Elaboration, Systems Engineering, Uncertainty, Confidence Index (CI), Technology Readiness Level (TRL), Activity Risk Level (ARL), Human Factors

come   L'archive ouverte pluridisciplinaire

INTRODUCTION

The call for tenders or bidding process is a process in which, a customer puts into competition several potential suppliers in order to choose the best one for the acquisition of a product/system or service (Vanwelkenhuysen 1998). In order to respond to a call for tenders, bidders (potential suppliers) must define and evaluate potential solutions, based upon the specifications of customer's requirements and their capabilities (skills, existing solutions, resources … etc.) (Krömker, Thoben, and Wickner 1997). In this paper, we only focus on call for tenders referring to the acquisition of a product/system and not that of a service. Therefore, all the proposals presented in this paper are relevant for any product/system development but not necessarily for services.

The bidding process, including the definition and the evaluation of potential solutions, corresponds to the first phase of the product/system development (Chalal and Ghomari 2008). The bidding process is often characterized by stringent and tight deadline for the submission of offers (Kroemker et al. 1997) and [START_REF] Lopez | ntegration of xperience Feedback into the Product Lifecycle: An Approach to est espond to t e idding rocess[END_REF]). Therefore, it is difficult to bidders to establish a detailed design (description) of all potential solutions. In some cases, it may be opportune for bidders to avoid detailed description of all potential solutions in order to reduce efforts and resources involved, especially in the cases in which the offers are not accepted (Sylla et al. 2017). Given all these previous elements, it is clear that the definition and the evaluation of potential solutions are not trivial. The difficulty can vary depending on the context of the definition of potential solutions. In the Make-To-Oder (MTO) or Assembly-To-Order (ATO) contexts, relevant solutions already exist. No design or engineering activities are necessary. At the opposite, for the Engineering-To-Order (ETO) context, some design and engineering activities are necessary in order to define novel solutions that are relevant to the customer's expectations. In both MTO/ATO and ETO situations, the evaluation of offers in terms of cost, performance and delivery time, may be imprecise and uncertain. The imprecision and the uncertainty are more important for novel solutions as the knowledge about the solutions for both the technical system and its implementation process are less available and less accurate (Brown and Chandrasekaran 1985) and (Sylla et al. 2017). The presence of imprecision and uncertainty makes the choice of the most relevant solution to be sent as an offer to the customer very difficult. Then, the choice of the relevant solution is based upon the standards indicators (cost, performance and lead time) and the subjective feeling of bidders. This may leads to the choice of unfeasible offer with regards to customer expectations (cost, performance and delivery time) [START_REF] Leśniak | upporting ontractors' idding Decision: R eural et orks pplication[END_REF].

Therefore, the aim of this paper is twofold: (i) first, to clarify the notion of imprecision and uncertainty in offer evaluation; and (ii) second, to propose two Confidence Indexes (CI) in order to take into account the uncertainty in offer elaboration.

INTRODUCTION

The call for tenders or bidding process is a process in which, a customer puts into competition several potential suppliers in order to choose the best one for the acquisition of a product/system or service (Vanwelkenhuysen 1998). In order to respond to a call for tenders, bidders (potential suppliers) must define and evaluate potential solutions, based upon the specifications of customer's requirements and their capabilities (skills, existing solutions, resources … etc.) (Krömker, Thoben, and Wickner 1997). In this paper, we only focus on call for tenders referring to the acquisition of a product/system and not that of a service. Therefore, all the proposals presented in this paper are relevant for any product/system development but not necessarily for services.

The bidding process, including the definition and the evaluation of potential solutions, corresponds to the first phase of the product/system development (Chalal and Ghomari 2008). The bidding process is often characterized by stringent and tight deadline for the submission of offers (Kroemker et al. 1997) and[START_REF] Lopez | ntegration of xperience Feedback into the Product Lifecycle: An Approach to est espond to t e idding rocess[END_REF]). Therefore, it is difficult to bidders to establish a detailed design (description) of all potential solutions. In some cases, it may be opportune for bidders to avoid detailed description of all potential solutions in order to reduce efforts and resources involved, especially in the cases in which the offers are not accepted (Sylla et al. 2017). Given all these previous elements, it is clear that the definition and the evaluation of potential solutions are not trivial. The difficulty can vary depending on the context of the definition of potential solutions. In the Make-To-Oder (MTO) or Assembly-To-Order (ATO) contexts, relevant solutions already exist. No design or engineering activities are necessary. At the opposite, for the Engineering-To-Order (ETO) context, some design and engineering activities are necessary in order to define novel solutions that are relevant to the customer's expectations. In both MTO/ATO and ETO situations, the evaluation of offers in terms of cost, performance and delivery time, may be imprecise and uncertain. The imprecision and the uncertainty are more important for novel solutions as the knowledge about the solutions for both the technical system and its implementation process are less available and less accurate (Brown and Chandrasekaran 1985) and (Sylla et al. 2017). The presence of imprecision and uncertainty makes the choice of the most relevant solution to be sent as an offer to the customer very difficult. Then, the choice of the relevant solution is based upon the standards indicators (cost, performance and lead time) and the subjective feeling of bidders. This may leads to the choice of unfeasible offer with regards to customer expectations (cost, performance and delivery time) [START_REF] Leśniak | upporting ontractors' idding Decision: R eural et orks pplication[END_REF].

Therefore, the aim of this paper is twofold: (i) first, to clarify the notion of imprecision and uncertainty in offer evaluation; and (ii) second, to propose two Confidence Indexes (CI) in order to take into account the uncertainty in offer elaboration.

INTRODUCTION

The call for tenders or bidding process is a process in which, a customer puts into competition several potential suppliers in order to choose the best one for the acquisition of a product/system or service (Vanwelkenhuysen 1998). In order to respond to a call for tenders, bidders (potential suppliers) must define and evaluate potential solutions, based upon the specifications of customer's requirements and their capabilities (skills, existing solutions, resources … etc.) (Krömker, Thoben, and Wickner 1997). In this paper, we only focus on call for tenders referring to the acquisition of a product/system and not that of a service. Therefore, all the proposals presented in this paper are relevant for any product/system development but not necessarily for services.

The bidding process, including the definition and the evaluation of potential solutions, corresponds to the first phase of the product/system development (Chalal and Ghomari 2008). The bidding process is often characterized by stringent and tight deadline for the submission of offers (Kroemker et al. 1997) and[START_REF] Lopez | ntegration of xperience Feedback into the Product Lifecycle: An Approach to est espond to t e idding rocess[END_REF]). Therefore, it is difficult to bidders to establish a detailed design (description) of all potential solutions. In some cases, it may be opportune for bidders to avoid detailed description of all potential solutions in order to reduce efforts and resources involved, especially in the cases in which the offers are not accepted (Sylla et al. 2017). Given all these previous elements, it is clear that the definition and the evaluation of potential solutions are not trivial. The difficulty can vary depending on the context of the definition of potential solutions. In the Make-To-Oder (MTO) or Assembly-To-Order (ATO) contexts, relevant solutions already exist. No design or engineering activities are necessary. At the opposite, for the Engineering-To-Order (ETO) context, some design and engineering activities are necessary in order to define novel solutions that are relevant to the customer's expectations. In both MTO/ATO and ETO situations, the evaluation of offers in terms of cost, performance and delivery time, may be imprecise and uncertain. The imprecision and the uncertainty are more important for novel solutions as the knowledge about the solutions for both the technical system and its implementation process are less available and less accurate (Brown and Chandrasekaran 1985) and (Sylla et al. 2017). The presence of imprecision and uncertainty makes the choice of the most relevant solution to be sent as an offer to the customer very difficult. Then, the choice of the relevant solution is based upon the standards indicators (cost, performance and lead time) and the subjective feeling of bidders. This may leads to the choice of unfeasible offer with regards to customer expectations (cost, performance and delivery time) [START_REF] Leśniak | upporting ontractors' idding Decision: R eural et orks pplication[END_REF].

Therefore, the aim of this paper is twofold: (i) first, to clarify the notion of imprecision and uncertainty in offer evaluation; and (ii) second, to propose two Confidence Indexes (CI) in order to take into account the uncertainty in offer elaboration.

INTRODUCTION

The call for tenders or bidding process is a process in which, a customer puts into competition several potential suppliers in order to choose the best one for the acquisition of a product/system or service (Vanwelkenhuysen 1998). In order to respond to a call for tenders, bidders (potential suppliers) must define and evaluate potential solutions, based upon the specifications of customer's requirements and their capabilities (skills, existing solutions, resources … etc.) (Krömker, Thoben, and Wickner 1997). In this paper, we only focus on call for tenders referring to the acquisition of a product/system and not that of a service. Therefore, all the proposals presented in this paper are relevant for any product/system development but not necessarily for services.

The bidding process, including the definition and the evaluation of potential solutions, corresponds to the first phase of the product/system development (Chalal and Ghomari 2008). The bidding process is often characterized by stringent and tight deadline for the submission of offers (Kroemker et al. 1997) and[START_REF] Lopez | ntegration of xperience Feedback into the Product Lifecycle: An Approach to est espond to t e idding rocess[END_REF]). Therefore, it is difficult to bidders to establish a detailed design (description) of all potential solutions. In some cases, it may be opportune for bidders to avoid detailed description of all potential solutions in order to reduce efforts and resources involved, especially in the cases in which the offers are not accepted (Sylla et al. 2017). Given all these previous elements, it is clear that the definition and the evaluation of potential solutions are not trivial. The difficulty can vary depending on the context of the definition of potential solutions. In the Make-To-Oder (MTO) or Assembly-To-Order (ATO) contexts, relevant solutions already exist. No design or engineering activities are necessary. At the opposite, for the Engineering-To-Order (ETO) context, some design and engineering activities are necessary in order to define novel solutions that are relevant to the customer's expectations. In both MTO/ATO and ETO situations, the evaluation of offers in terms of cost, performance and delivery time, may be imprecise and uncertain. The imprecision and the uncertainty are more important for novel solutions as the knowledge about the solutions for both the technical system and its implementation process are less available and less accurate (Brown and Chandrasekaran 1985) and (Sylla et al. 2017). The presence of imprecision and uncertainty makes the choice of the most relevant solution to be sent as an offer to the customer very difficult. Then, the choice of the relevant solution is based upon the standards indicators (cost, performance and lead time) and the subjective feeling of bidders. This may leads to the choice of unfeasible offer with regards to customer expectations (cost, performance and delivery time) [START_REF] Leśniak | upporting ontractors' idding Decision: R eural et orks pplication[END_REF].

Therefore, the aim of this paper is twofold: (i) first, to clarify the notion of imprecision and uncertainty in offer evaluation; and (ii) second, to propose two Confidence Indexes (CI) in order to take into account the uncertainty in offer elaboration.

Proceedings of the 20th World Congress

The International Federation of Automatic Control Toulouse, France, July 9-14, 2017

This will enable bidders to compare the potential solutions in terms of confidence and to choose the most relevant one to be sent as an offer to the customer not only based upon the standard indicators but also considering the confidence. The rest of the paper is structured in four sections. The second section is dedicated to the notions of imprecision and uncertainty in offer evaluation. In the third section the proposed confidence are presented and discussed. The fourth section presents an illustrative application of the proposed method for the assessment of the confidence indexes. And the last section presents some conclusions and future works.

IMPRECISION and UNCERTAINTY in OFFER EVALUATION

Each phase of the development of a product/system is characterized by the presence of both imprecision and uncertainty (Wood and Antonsson 1990). Risk: is defined as a measure of the uncertainty of achieving an objective [START_REF] Haskins | INCOSE Systems Engineering Handbook. lir, ., and . olger. 1 . ypes of ncertainty', u y ets, ncertainty, and nformation[END_REF].

Reliability: is related to the truth of an information [START_REF] Dubois | Possibility Theory: An Approach to Computerized Processing of Uncertainty[END_REF]. Ambiguity: is associated to situations in which the choice between several alternatives is left unspecified (Klir and Folger 1988). Vagueness: is associated with the difficulty of making precise distinctions in the world (Klir and Folger 1988). Nonspeficity: can be seen as an ambiguity (Thunnissen 2003).

The presence of imprecision and uncertainty in the evaluation of potential solutions makes the evaluation imperfect, and then often leads to the choice of unfeasible solutions with regards to customer's expectations (cost, performance and delivery time). The source of uncertainty and imprecision can be epistemic or aleatory (Dantan et al. 2013). The epistemic uncertainty and imprecision are due to any lack of knowledge whereas the aleatory uncertainty and imprecision are due to the inherent variability of the characteristics of the considered artifact (Thunnissen 2003). According to the offer definition context (MTO/ATO or ETO), the imprecision and uncertainty can be more or less important (Sylla et al. 2017). The table 1 below depicts a classification of imprecision and uncertainty based upon the offer definition context and the source of the imprecision and the uncertainty. In the context of MTO/ATO, relevant solutions (systems) have already been designed, implemented and successfully deployed. All the relevant knowledges for the design and the implementation of these solutions are completely available and accurate (Brown and Chandrasekaran 1985). Therefore, we assume that, there are no imprecision or uncertainty due to any lack of knowledge (epistemic uncertainty or epistemic imprecision).

In the context of ETO, all relevant knowledge for the design and the implementation of the solutions (systems) are not available. This lack of knowledge is the source of the epistemic imprecision and uncertainty in ETO situations.

Table 1. Imprecision and Uncertainty in Offer Evaluation

Context of Offer Definition

Source of Imprecision and Uncertainty MTO and ATO Aleatory ETO Aleatory and Epistemic

The inherent variability of some characteristics of the solutions (e.g. variability of component's cost and variability due to the properties of a specific material) may lead to an imprecise and uncertain evaluation of these solutions. Therefore, the aleatory imprecision and uncertainty are always present in offer definition and evaluation for both MTO/ATO and ETO situations.

The epistemic imprecision and uncertainty are more important in first phase of product/system development and then in offer elaboration. This kind of imprecision and uncertainty can be reduced by more analysis and efforts [START_REF] Perry | xploring esign pace in mbodiment esign it onsideration of odels ccuracy[END_REF]. In this paper we focus on the epistemic uncertainty. We propose two Confidence Indexes (CI) in order to take into account the epistemic uncertainty in the choice of relevant solutions to be sent as an Table 2. Proposed Indicators

Objective Indicators

Objective indicators provide reliable information on the solutions of both technical system and its implementation process. At the system side, it is related to the notion of readiness level of subsystems, integrations and systems (Mankins 1995) and (Sauser et al. 2008). At the process side, it is based on the risk level of process activities and processes (Sylla et al. 2017). As in (Sylla et al. 2017), we propose to add to each elements of the system and the process, the proposed objective indicators (see Table 2).

For the system, the Confidence Index (CI S ) evaluation starts with the characterization of the Technology Readiness Level (TRL) of each subsystem and the characterization of the Integration Readiness Level (IRL) of each relevant integration involved in a system. The TRL is a systematic and factual measurement that indicates how much a subsystem technology is ready to be deployed for a given function and environment (Mankins 1995). It has been adopted by US Department of Defense (DoD) and the US Department of Energy (DoE) for the evaluation of the maturity of a technology (Tan, Sauser, and Ramirez-Marquez 2011). It is widely used in industry in order to take into account the uncertainty related to the development of a technology. TRL is measured on a nine-level scale (1 being the less maturation stage and 9 the highest maturation stage) (see table 3). In the same sense as the TRL, the IRL is a systematic measurement that provides a factual evaluation of the maturity of integration between two technologies. IRL is also measured on a nine-level scale (1 being the less maturation stage and 9 the highest maturation stage) (see table 3) (Sauser et al. 2008). In order to compute the readiness of a whole system, (Sauser et al. 2008) have proposed a System Readiness Level scale (SRL). The SRL value is computed as a function of TRLs of subsystems and relevant IRLs of integrations. The calculation method proposed by (Sauser et al. 2008) is based on the matrix algebra and this method is used in this paper for the computation of SRL value of a system. SRL is then measured on a five-level scale (see table 4) (Sauser et al. 2008). In the proposed method, each subsystem is characterized with a TRL and each integration between two subsystems with an IRL. Then each system is characterized with a SRL. Integration is Mission Proven through successful mission operations.

8

Actual system completed and qualified through test and demonstration

Actual integration completed and Mission Qualified through test and demonstration in the system environment.

System prototype demonstration in operational environment

The integration of technologies has been Verified and Validated with sufficient detail to be actionable.

6

System/subsystem model or prototype demonstration in relevant environment

The integrating technologies can Accept, Translate, and Structure Information for its intended application.

Component and/or breadboard validation in relevant environment

There is sufficient Control between technologies necessary to establish, manage, and terminate the integration. 4

Component and/or breadboard validation in laboratory environment

There is sufficient detail in the Quality and Assurance of the integration between technologies.

Analytical and experimental critical function and/or characteristic proof of concept

There is Compatibility (i.e., common language) between technologies to orderly and efficiently integrate and interact.

Technology concept and/or application formulated

There is some level of specificity to characterize the Interaction (i.e., ability to influence) between technologies through their interface.

1

Basic principles observed and reported

An Interface between technologies has been identified with sufficient detail to allow characterization of the relationship. For the process, the Confidence Index (CI P ) starts with the characterization of the Activity Risk Level (ARL) of each process activity. As already said in (Sylla et al. 2017), every business is exposed to risks all the time and such risks can directly affect day-to-day operations, decrease revenue or increase expenses. The impacts of these risks may lead to cost growth and schedule slippage in the implementation process. Therefore, we propose the ARL in order to take into account the uncertainty associated to an activity of the implementation process. This ARL is inspired by the risk Proceedings of the 20th IFAC World Congress Toulouse, France, July 9-14, 2017 management process area of CMMI (Software Engineering Institute 2006) and the TRL scale. It is based on three elements: (main risk probability (high or low), the main risk impact (serious or marginal) and the main risk treatment (it exists or not action plans to manage the risk) (Sylla et al. 2017). ARL is measured on a nine-level scale (1 being the most risked and 9 less risked) as shown by the table 5. The phenomenon of integration between sub-systems introduced for the system readiness calculation seems not relevant to the delivery process. Therefore, the Process Risk Level of the whole implementation process is computed as a function of the ARLs of all activities involved in this process. Several functions could be used in order to compute PRL (minimum function, maximum function …etc.). In this paper we use a weighted average to compute the PRL of the process in order to take into account the relative importance of each activity.

The ARL of activities are first normalized. As the SRL, the PRL is measured on a five-level scale. In the proposed method, each activity of the implementation process and each process are respectively characterized by an ARL and a PRL. Risk with low probability, marginal impact and treatments 8

Risk with high probability, marginal impact and treatments 7

Risk with low probability, serious impact and treatments 6

Risk with high probability, serious impact and treatments 5

Risk with low probability, marginal impact and no treatment 4

Risk with high probability, marginal impact and no treatment 3

Risk with low probability, serious impact and no treatment 2

Risk with high probability, serious impact and no treatment 1

No risks management

Subjective Indicators

The objective indicators provide relevant information about the readiness of the potential solutions of a system and the risk level of the associated processes. However this information is not sufficient to measure that the system finally designed and implemented will match all customer's expectations (cost, performance and delivery time). Moreover, as already said by Mankins, not all sub-systems need a maximum readiness level as a prerequisite for an application (Mankins 2009). The same reasoning can be applied to the process. Not all activities need a maximum ARL to be performed.

Therefore, we propose a second version of Supplier Feeling Level (SFL) in order to capture the thought of the person in charge of the offer elaboration. Based on his experience and his risk aversion, the person (expert) provides a subjective judgment about the offer. In the contrary to the first version of SFL which is measured on a three level-scale (Sylla et al. 2017), this second version of SFL is measured on a five-level scale as shown by the table 6. This is to simplify the computation of the overall Confidence Indexes (CI S for system and CI P for process) introduced in the next subsection. This SFL scale is used for both the elements of system and those of process (table 2). The aggregation mechanisms proposed for the objective indicators are used to compute the SFL at the system (SFL S ) and process (SFL P ) level. The CI S and CI P are computed only at the system and process level (see table 2). The CI S is a function of SRL and SFL S of the system whereas the CI P is a function of PRL and SFL P of the process. The same function is used to compute them.

Several methods could be used to compute the CI S and CI P (minimum function, maximum function, average … etc.). In this paper, as a first idea, we proposed to compute CI S and CI P using the formulas below. The CI S and CI P are then measured on a nine-level scale.

ILLUSTRATIVE APPLICATION

The aim of this section is to show the applicability and the effectiveness of the proposed method for the evaluation of the confidence indexes of potential solutions. In this illustrative application, we consider the development of a system.

For each potential solution, we consider two items that have to be evaluated, a technical system and the associated implementation process. The technical system is composed of three subsystems (SS 1 , SS 2 and SS 3 ) and two relevant integrations (IT. SS 1 -SS 2 and IT. SS 1 -SS 3 ) (left part of figure 2). Each subsystem is characterized with a cost (C SS ), a TRL and a SFL (SFL SS ) and each integration is also characterized with a cost (C IN ), an IRL and a SFL (SFL IN ). Then, thanks to the proposed aggregation mechanisms for the system, the SRL, SFL S and CI S of the system are determined. The cost (C S ) of the whole technical system is computed as a sum of the costs of the subsystems and their integrations.

The implementation process is composed of a sequence of three activities (ACT 1 , ACT 2 and ACT 3 ) as presented in the right part of figure 2. Similarly to the technical system, each activity of the process is characterized with a Cost (C A ), duration (D A ), an ARL and a SFL A . The cost of the process (C P ) is determined as the sum of the costs of all activities, and the duration of the process (D P ) as the sum of the duration of all the activities. Then, thanks to the proposed aggregation mechanisms for the process, the PRL, SFL P and CI P of the process are determined.

Figure 2: System and Process

Proceedings of the 20th IFAC World Congress Toulouse, France, July 9-14, 2017

In order to demonstrate all the proposals of this paper, fifteen potential solutions have been generated using a systemprocess configuration tool, called CoFiADe For the analysis of this evaluation, we only focus on the Confidence Indexes evaluation.

Table 7. ARL scale

For the potential solution I, at the technical system side, the TRL of each subsystem and the IRL of each integration are equal to 9 (maximum level of TRL and IRL scales). The SFL SS of each subsystem and the SFL IN of each integration are equal to 5 (maximum level of SFL scale). Therefore, the calculated SRL, SFL S and CI S of the technical system are respectively 5, 5 and 9. These values (5, 5, and 9) correspond respectively to the maximum levels of SRL, SFL S and CI S . This means that this technical system is at the highest maturity level and the person in charge of the offer elaboration has a very good feeling about it. Therefore the CI S of this technical system is at the highest level. At the process side, the ARL of each activity is equal to 9 (maximum level of ARL scale) and the SFL A of each activity is equal to 5 (maximum level of SFL scale). Therefore the calculated PRL SFL P , and CI P are respectively equal to 5, 5 and 9. These values (5, 5, and 9) correspond respectively to the maximum levels of PRL, SFL P and CI P . This means that, this implementation process is not risky and the person in charge of the offer elaboration has a very good feeling about this process. The evaluation of this potential solution I shows that this solution will be performed with respect to all the objectives (cost, performance and delivery time). Therefore, the calculated SRL, SFL S and CI S of the technical system are respectively 4, 2 and 5. This means that this technical solution has a high maturity, but the person in charge of the offer elaboration has a bad feeling about this technical solution. Therefore the CI S of this technical solution is at a medium level. At the process side, the ARL of the activities are: ARL A1 = 4, ARL A2 = 3 and ARL A3 = 3. The SFL A of the activities are: SFL A1 = 3, SFL A2 = 2 and SFL A3 = 3. Therefore the calculated PRL, SFL P , and CI P are respectively equal to 2, 2 and 3. This means that, this implementation process has a high risk level and the person in charge of the offer elaboration has a bad feeling about this process. The evaluation of this potential solution XV shows that this solution could not be performed with respect to all the objectives.

CONCLUSIONS and FUTURE WORKS

In this paper, the notions of imprecision and uncertainty in the evaluation of the potential solutions in offer elaboration have been clarified. A classification of uncertainty in the evaluation of potential solutions has also been proposed. Then based on the previous work presented in (Sylla et al. 2017), two confidence indexes and their evaluation method have been proposed for the characterization of the confidence level of potential solutions (each potential solution is composed of a technical system and its implementation). Two kinds of indicators are used in order to compute the confidence indexes. The first one is objective and the second one based on human feeling. Both kinds of indicators characterize the technical system and its implementation process. The illustrative application has shown that the proposed method can be used to evaluate the confidence in the potential solutions for the development of a system. Although the illustrative application deals with limited number of sub-systems and activities, the proposed approach is applicable on systems that have more sub-systems and require more activities in its implementation process. However this approach supports only one level of decomposition for both the system and the process.

With these two Confidences indexes (CI S and CI P ), a bidder is now able to explicitly take into account the confidence in potential solutions in the elaboration of offer. In fact, the CI S and CI P will enable the bidder to compare the potential solutions and choose the most relevant one to be sent as an offer to the customer not only based upon the standard indicators (cost, performance and delivery time) but also considering the confidence. Several companies from the system development sector have already confirmed these proposals.

Proceedings of the 20th IFAC World Congress Toulouse, France, July 9-14, 2017

Future works should consider the development of a new knowledge based model (e.g. CSP model) for offer elaboration in MTO/ATO and ETO situations. The new knowledge based model will integrate all the proposals of this paper in order to enable the characterization of the confidence level of the potential solutions. Future works should also consider providing a formal representation of imprecision associated to the values of design attributes and standards indicators. One could consider using possibility theory or a similar approach. Finally, in order to help the bidder to choose relevant solutions among several potential solutions, it is imperative to develop a Multi Criteria Decision Making (MCDM) method. Using the formal representation of imprecision and the proposed CI S and CI P , this MCDM method will enable the bidder to select the relevant solution while taking into account the epistemic uncertainty and imprecision in offer elaboration.

  Several efforts have been dedicated to the clarification, modelling and treatment of imprecision and uncertainty in many fields. According to the field and the application, different concepts, definitions and classification have been proposed in the scientific literature (Thunnissen 2003), (Dantan et al. 2013) and (Klir and Folger 1988). In this paper, in the same sense as in (Dubois and Prade 2012), imprecision is related to the content of information, to the values of design attributes or performance indicators (e.g. cost and duration). Uncertainty concerns the confidence in the values of a design attribute or performance indicators. Let's consider the following evaluation of the cost of an engine: the engine possibly costs 10 ± 3. If we consider this information as a quadruplet of (object, attribute, value, confidence) as suggested in (Dubois and Prade 2012), we can easily identify respectively (engine, cost, 10 , possibly). e imprecision is ± 3 composing the value of the cost and the uncertainty (confidence) is possibly . These two notions of imprecision and uncertainty encompass several concepts and have various definitions. The figure 1 below depicts some concepts related to imprecision and uncertainty. The concepts presented in this figure 1 are not exhaustive. Thunnissen (2003) provides more concepts related to imprecision and uncertainty. Confidence: is a kind of measure of the feasibility of a solution (Vareilles et al. 2014).

Figure 1 :

 1 Figure 1: Concepts related to Uncertainty and Imprecision

  . The proposed indicators and aggregation mechanisms have been implemented using the Matlab software. Then, the evaluation of each potential solution has been performed using this Matlab software. The table 7 below summarizes the results of the evaluation of all the fifteen potential solutions. The potential solutions are presented in the columns (e.g. I, II and III). The upper part of the table presents the subsystems (SS1, SS2 and SS3), the integrations (IN. SS1-SS2 and IN. SS1-SS3) and the technical system (SYSTEM) of each potential solution. The lower part of the table presents the activities (ACT1, ACT2 and ACT3) and the implementation process (PROCESS) of each potential solution. The relevant indicators for each element are presented in the front of the element (e.g. for SS1, C SS1 ( ), L SS1 and SFL SS1 ).

For

  the potential solution XV, at the technical system side, the TRL of the subsystem are: TRL SS1 = 9, TRL SS2 = 9 and TRL SS3 = 8. The IRL of the integrations are: IRL IN. SS1-SS2 = 8 and IRL IN. SS1-SS3 = 5. The SFL SS of the subsystems are: SFL SS1 = 3, SFL SS2 = 3 and SFL SS3 = 2. The SFL IN of the integrations are: SFL IN. SS1-SS2 = 2 and SFL IN. SS1-SS3 = 2.

Table 3 . TRL and IRL scales

 3

	Level	TRL	IRL
	9	Actual system proven through successful mission operations

Table 4 . SRL scales Level SRL SRL Value 5

 4

	0,9-1,00

Execute a support program that meets operational support performance requierements and sustains the system in the most cost-effective manner over its total life cycle.

Table 5 . ARL scale Level ARL 9

 5

Table 6 . SFL scale

 6

	Level	SFL
	5	Very good
	4	Good
	3	Neutral
	2	Bad
	1	Very bad
	3.3 Overall Confidence Indexes (CI S and CI P )

Acknowledgement: The authors would like to thank all ANR OPERA partners for their implications in our research work.