Charlotte Herzog

Xavier Granier

Fabrice Harms

Philippe Zeitoun

Ombeline De

L A Rochefoucauld
email: odlrochefoucauld@imagine-optic.com

Study on Contrast Variations with Depth in Focused Plenoptic Cameras

A focused plenoptic camera has the ability to record and separate spatial and directional information of the incoming light. Combined with the appropriate algorithm, 3D scene could be reconstructed from a single acquisition, over a depth range called plenoptic Depthof-Field. In this article, we study the contrast variations with depth as a way to assess plenoptic Depth-of-Field. We take into account the impact of diffraction, defocus and, magnification on the resulting contrast. We measure the contrast directly on both simulated and acquired images. We demonstrate the importance of diffraction and magnification in the final contrast. Contrary to classical optics, the maximum of contrast is not centered around the main object plane, but around a shifted position, with a fast and non-symmetric decrease of contrast.

INTRODUCTION

Light-Field imaging is a technology that samples a part of the Light-Field (LF) defined as the radiance flowing through each point and direction of a scene [1][2][3]. It allows to retrieve more information than in conventional imaging, by separating angular and spatial information contained in the incoming light. It enables new applications such as synthetic aperture, viewpoint changes, depth estimation and 3D imaging [4,5]. Plenoptic Cameras are Light-Field imaging systems composed of a main lens (ML), a microlens array (MLA) and, a detector [6].

The main advantage of a plenoptic system is the possibility from a single acquisition to reconstruct all the planes of a scene along a depth range that we call plenoptic Depth-of-Field (DoF pleno ), defined in [7][8][9][10]. Levoy showed theoretical and experimental results in the case of his unfocused light-field mi-croscope [7]. A detailed derivation of DoF pleno equation was presented in [9] but not experimentally validated. Zhu derived a similar equation and confronted it to experimental measurements of a point source [10]. Our work aims at confronting the theoretical DoF pleno to simulations and experiments when imaging with a focused plenoptic camera. We decided to use the contrast as a parameter for assessing if a plane belongs to DoF pleno , as in-focus depth planes are expected to be of higher contrast than out-of-focus ones [5,11]. Previously reported results either provided a study of the variation of modulation transfer function with depth in the case of an unfocused plenoptic microscope [12], or a characterization of contrast for a focused plenoptic system but without considering its variation with depth [13]. Liang and Ramamoorthi presented a study of contrast along depth but do not consider the effects of diffraction [14].

In this article, we study the variations of contrast with the object's depth for a focused plenoptic system [15,16]. First, we simulate the expected raw plenoptic sub-images to observe the effects of diffraction, defocus and magnification, separately or combined. Simulated sub-images are then used to determine the variations of contrast with depth. We then confront our simulation results with experimental data.

PLENOPTIC DEPTH OF FIELD OF A FOCUSED PLENOPTIC CAMERA

The system studied in this article is a focused plenoptic camera (Fig. 1). The MLA acts as a relay imaging system, re-imaging the image plane of the ML directly on the detector. There is an intrinsic privileged position, that we call reference plane, corresponding to the only plane that is perfectly in focus on the detector. From the physical position of the detector b ref , we calculate the position of the intermediate image plane from the MLA (a ref ) and from the ML (z ref 1 ), and the position of the reference object plane z ref 0 . The distances z 1 , a and b correspond to the associated distances when choosing an arbitrary z 0 . When a = 0, the object plane is at a position z trad 0 , optically conjugated with the plane positioned at z ref 1 + a ref from the ML, which corresponds to the physical position of the MLA. This is the traditional (or unfocused) plenoptic configuration [17]. We built our own plenoptic setup for visible light in our laboratory. The ML is an achromatic doublet of focal length f 1 = 200mm and diameter d 1 = 24mm. The MLA is composed of 30 × 30 square microlenses of focal length f 2 = 18.6mm and side d 2 = 0.3mm. Each microlens creates a sub-image on the detector. The detector has 1280x960 pixels of size 6.45 µm. The distances used for simulations and experiments are:

z ref 0 = 233mm, z ref 1 + a ref = 1597mm and b ref = 20.7mm.
The object is a 1951 USAF Resolution Test Target (Fig. 2). Some previous definitions of DoF pleno are based on the same principle of geometrical optics: a depth plane is considered focused if the corresponding defocus blur is bellow a chosen acceptable limit [8][9][10]. We define DoF pleno in the object plane, taking into account both ML and MLA. A first extension to wave optics is to use the effective pixel size e = max(p, s λ ) (maximum between pixel size p and diffraction limit spot size on the sensor s λ ) [7,9]. For focused plenoptic cameras, we derive the following equation (similar to Eq. ( 4) in [7]):

DoF pleno = λ M 2 • N A 2 imMLA + e m 2 • M 2 • N A imMLA (1)
with m = b ref /a, M = z 1 /z 0 and N A imMLA = d 2 /(2b ref ).
The first term corresponds to a wave optics term and the second, to a corrected geometrical term. We obtain a DoF pleno of 16.3mm for our configuration.

In our paper, we study the DoF pleno using contrast estimation on a single sub-image. The condition of 3D reconstruction at a chosen depth is that the plane at this depth has been imaged by sharp sub-images: a depth belongs to DoF pleno if and only if it is included in the depth of field of a single sub-image [18]. Therefore, DoF pleno is the depth of field of a single sub-image, and can be directly studied on the raw plenoptic image, without the need for reconstruction. We study the effects of diffraction, defocus and magnification introduced by Eq. (1).

SIMULATIONS

A raw plenoptic sub-image is simulated on the detector's plane, positioned at a fixed distance b ref from the MLA (Fig. 1). The simulated object, a portion of a test target (Fig. 2) is placed at a variable distance z 0 from the ML. The distance between the ML The contrast used as our criterion is defined by: (I max -I min )/(I max + I min ), with I max and I min the maximal and minimal intensity values measured on the detector plane.

Diffraction.

To simulate diffraction, we performed the convolution of the object with a cardinal sine function, representing the diffraction pattern of our square microlenses [19]:

I(r) = I 0 sinc 2 π • r • d 2 λ • b ref (2)
with r the position on the detector, sinc(x) = sin x/x and I 0 a normalization constant such that I(r) dr = 1. Diffraction from ML is ignored, because it is reduced by the mignification of the MLA compared to the sub-image and pixel sizes.

Defocus.

The Circle of Confusion corresponds to the region over which a point is blurred in the case of defocus (Fig. 1) [10]. Its diameter CoC is defined as:

CoC = d 2 1 - b ref b ( 3
)
The object is in focus and the image is sharp when the image plane is close to the detector (i.e., |1b ref /b| << 1). Convolutions of the object with I(r) from Eq. ( 2) and a circle of size CoC from Eq. (3) simulate the effects of diffraction and defocus. They strongly depend on the depth z 0 .

Magnification.

The third phenomenon is the total magnification M tot of the system, combining the effects of the ML and the MLA. It is a hyperbolic function of depth z 0 :

M tot = z 1 z 0 b ref a = f 1 b ref z ref 1 + a ref -f 1 1 z 0 -z trad 0 with z trad 0 = f 1 (z ref 1 + a ref ) z ref 1 + a ref -f 1 (4)
where z trad 0 corresponds to the unfocused plenoptic configuration (a = 0).

Impact of diffraction and defocus.

Fig. 3 shows the effects of diffraction and defocus on a plenoptic raw sub-image for an object at z 0 = 240mm, whereas the optical system is optimized for z ref 0 = 233mm. The black dotted curve represents the shape of the original signal without the effects of diffraction or defocus. At z 0 = 240mm, the defocus (green curve) only affects the shape and width of the bars, because the size of CoC is too small compared to the width of the bars on the screen to affect the amplitude and contrast of the signal. On the contrary, considering the diffraction (red curve) results in a drop of contrast from 1 to 0.59. With the combination of both diffraction and defocus (blue curve), the contrast is even lower with a value of 0.52.

Impact of diffraction, defocus and magnification.

The cumulative effects of the three factors are illustrated in Fig. 4 at four different depths. Magnification governs the spatial frequency of the test object. On the detector, we measure a spatial frequency of 3.20cy/mm, 5.89cy/mm, 8.59cy/mm and 15.34cy/mm for z 0 = 231mm, 233mm, 235mm and 240mm respectively. In comparison, the physical size of the test target of bar width =125µm corresponds to a frequency of 4.00cy/mm.

z ref 0 = 233mm (
blue), 231mm (dotted orange), 235mm (dotted green), and 240mm (purple, same depth as in Fig. 3).

The difference in amplitude is mainly due to diffraction and defocus. Magnification plays a role in the amplitude variations, but effects are not symmetric: the contrast is higher close to z trad 0 (0.96 at 231mm), and decreases as the depth increases (0.89 at 233mm, 0.86 at 235mm and 0.5 at 240mm). Amplitude at z ref 0 is 11% lower in respect to the test target at object plane.

Simulated contrast curves.

Parameters given in Section 2 were used for the simulations, except that the size of the sub-image has been artificially enlarged to fully include the magnified image. Then the contrast in the simulated raw sub-images was extracted at different depths to study the consequence of the three phenomena (diffraction, defocus and magnification) on the plenoptic image. Fig. 5 shows their impacts on contrast curves as a function of depth position z 0 .

In Fig. 5, defocus (green curve) does not significantly affect the contrast as depth varies: a plateau of contrast=1 nearly centered around the z ref 0 position is observed, as already seen in Fig. 3. The curve with diffraction and magnification (orange) is maximal at and symmetric around the z trad 0 position, and not at the expected z ref 0 position. When the three effects are combined (blue curve), the maximum contrast is located around z trad 0 . Defocus is responsible for an asymmetry, with a slow decrease of contrast from z trad 0 to a plateau around z ref 0 . The fast variations in magnification, combined with diffraction and defocus, explain the fast decrease in the contrast curve: higher contrast is measured for larger magnification (around z trad 0 ), whereas for smaller magnification the image is more affected by defocus and mainly by diffraction. These curves have to be compared to the theoretical value: a region of maximal contrast over 16.3mm around the reference position.

This can be generalized to other sets of parameters: the curves combining magnification with either defocus or diffraction will have similar shapes and will be centered around z ref 0 and z trad 0 respectively. On the contrary, when the three effects are combined, the shape of the contrast curve will depend on the ratio between magnification, diffraction and defocus.

COMPARISON WITH EXPERIMENTAL DATA

Using our setup (cf. Section 2), we imaged a test target at different depths. The optical system was optimized for the reference object plane located at z ref 0 = 233mm. Fig. 6a shows sub-images extracted from raw plenoptic images acquired at different depths. In this configuration, total magnification is maximum at the unfocused plenoptic plane z trad 0 = 228.6mm, and decreases as depth increases (Eq. ( 4)). Fig. 6a confirms this effect: at 228.5mm, only a part of one bar appears while as the depth increases, three bars can slowly be seen on the sub-images. For each experimental raw plenoptic image we measured the contrast of one sub-image taken in the middle of the image, and plot it against depth (pink curve in Fig. 6c). It can be compared to the simulated curve (blue, Fig. 6c), obtained using the parameters of the setup (without the enlarged sub-image size as in Fig. 5).

Both curves present the same shape, with maximal values at z 0 = 227 and 230mm surrounding a large gap located at z trad 0 . The gap is due to the magnification being so large that the image of the bars does not fit inside the sub-image (as illustrated by the 2 nd figure from the left in Fig. 6a). This leads to unreliable contrast values measured on only a part of the total magnified pattern, similarly to what happens in the experimental setup.

On both sides of this gap, the two curves slowly decrease following the decrease in magnification. Near the position z trad 0 , magnification is large enough so that diffraction and defocus have little effect on the measured contrast, but when the bars are smaller on the detector, they are more influenced by defocus and mainly by diffraction. At z ref 0 , defocus is minimal. Effect of defocus increases when z 0 moves further from z ref 0 which explains the asymmetry of the curves around the z ref 0 position compared to the left part of the curve.

Although the simulated (blue) and measured (pink) curves are close, they do not overlap. It may be explained by a difference of dynamic ranges: the experimental images are affected by noise and light adjustments that will affect the intensity distribution and thus the measured contrasts in the image.

The quality of a Light-Field imaging depends on the combination of an optical systems with a reconstruction algorithm to compute the final images. In our work, we chose to estimate the contrast on raw sub-images instead of the reconstructed ones. To validate such a choice, we present a contrast curve (in gray, Fig. 6c) computed from images reconstructed at the same depths as in Fig. 6a with the patch tilling method [15] (Fig. 6b) with parameter of refocusing adjusted for each raw image. As expected, the resulting contrast curve (gray) has a similar shape to the one from raw images (pink) except around z trad 0 , where it reaches a local maximum instead of a gap.

CONCLUSION

In this article, we studied the contrast versus depth in a focused plenoptic camera as an indicator for assessing DoF pleno , the depth range over which a scene can be reconstructed from a single plenoptic raw image. The study of contrast versus depth shows that DoF pleno is more complex than expected by theoretical equations from the literature. We highlighted the combined effects of diffraction, defocus and magnification on the resulting image. Magnification together with diffraction is responsible for important unexpected effects. The contrast curve reaches a maximum at the unfocused plenoptic configuration z trad 0 instead of reference depth plane z ref 0 . Defocus is responsible for an asymmetry with a slow decrease in-between these two depths and a plateau around z ref 0 . Beyond this interval, the contrast decreases quickly due to the fast variations of magnification.

The variations of magnification over the whole depth range is a potential problem for 3D reconstruction: not only is it responsible for contrast reduction, but it will also lead to large variations of size of the imaged sample depending on where it is located. As a solution to this issue, a telecentric plenoptic system can be built, meaning the magnification is constant across depth planes. Furthermore, appropriate algorithms should be used in order to correct for potential size errors.

Fig. 1 .

 1 Fig. 1. A focused plenoptic system. Red rays come from the reference depth plane z ref 0 whereas green rays correspond to another depth to illustrate the Circle of Confusion (CoC) due to defocus.

Fig. 2 .

 2 Fig. 2. The 1951 USAF Resolution Test Target used in the experiments (left) and zoom in an experimental raw plenoptic image of group 2.1 (bar width = 125 µm) (right).

Fig. 3 .

 3 Fig.3. Simulated 1D raw image of the test object versus position r on the detector with the effect of defocus only (green; contrast = 1), with diffraction only (red; contrast = 0.59) and with both effects combined (blue; contrast = 0.52), calculated at a depth z 0 = 240mm, compared to the image with no effect (dotted black; contrast = 1).

Fig. 4 .

 4 Fig.4. Simulated 1D raw image with the three effects versus position r on the detector for different depths z 0 : z ref 0 = 233mm (blue), 231mm (dotted orange), 235mm (dotted green), and 240mm (purple, same depth as in Fig.3).

Fig. 5 .

 5 Fig. 5. Contrast curves versus depth: with defocus and magnification only (green), with diffraction and magnification only (orange) and with the three effects combined (blue). Depths z ref 0 = 233mm and z trad 0 = 228.6mm. Note that the small oscillations are due to pixel discretization of the signal.

Fig. 6 . 0 =

 60 Fig. 6. a) Raw sub-images acquired at planes: z 0 = 223.5, 228.5, 233, 236, 242mm; b) Corresponding reconstructed images; c) Comparison of the simulated contrast curve (blue) and experimental contrast curve measured on raw sub-images (pink) and on reconstructed images (gray). The gap located around z trad 0 = 228.6mm is due to the large magnification that makes the bars exceeding the sub-image size.

FUNDING

This work was funded by the VOXEL project (European Union's Horizon 2020 research and innovation program under grant agreement Nº 665207).


Amadeu Almeida Coco
email: amadeuac@dcc.ufmg.br

Elyn L Solano-Charris
email: elyn.solanocharris@utt.fr

Andréa Cynthia Santos

Christian Prins
email: christian.prins@utt.fr

Thiago Noronha

Robust optimization criteria: state-of-the-art and new issues

Uncertain parameters appear in many optimization problems raised by real-world applications. To handle such problems, several approaches to model uncertainty are available, such as stochastic programming and robust optimization. This study is focused on robust optimization, in particular, the criteria to select and determine a robust solution. We provide an overview on robust optimization criteria and introduce two new classifications criteria for measuring the robustness of both scenarios and solutions. They can be used independently or coupled with classical robust optimization criteria and could work as a complementary tool for intensification in local searches.

Introduction

Uncertain parameters appear in many optimization problems raised by realworld applications. In general, uncertain data arise due to incomplete information and undifferentiated information [START_REF] Lipshitz | Coping with uncertainty: A naturalistic decision-making analysis[END_REF]. Several approaches are available to 1 model them in the context of optimization problems, in particular stochastic programming where uncertain data are modeled as random variables [START_REF] Shapiro | Lectures on stochastic programming: modeling and theory. The society for industrial and applied mathematics and the mathematical programming society[END_REF][START_REF] Wets | Stochastic programming models: Wait-and-see versus hereand-now[END_REF]. However, such approach is limited to the cases where uncertainties have a stochastic nature (which is not always the case) and when it is possible to identify the probability distribution, which can be difficult to obtain, especially for largescale problems [START_REF] Ben-Tal | Robust convex optimization[END_REF]. Many studies deal with stochastic programming approaches and the pioneer models were proposed by Beale [START_REF] Beale | On minimizing a convex function subject to linear inequalities[END_REF] and Dantzig [START_REF] Dantzig | Linear programming under uncertainty[END_REF].

Robust optimization has been applied in general as a way to self-protection against undesirable impacts due to vague approximations, incomplete, imprecise, or ambiguous data. Readers are referred to [START_REF] Roy | Robustness in operational research and decision aiding: A multifaceted issue[END_REF] for an interesting survey on different uses of robustness in the field of Operations Research. This study is dedicated to robust optimization problems for which uncertain data are defined as a set of possible values, usually called as scenarios. In this context, the literature covers a large number of applications [START_REF] Montemanni | The robust traveling salesman problem with interval data[END_REF][START_REF] Schneider | On the robustness of non-linear personalized price combinatorial auctions[END_REF][START_REF] Sungur | A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty[END_REF][START_REF] Zhang | Two-stage minimax regret robust uncapacitated lot-sizing problems with demand uncertainty[END_REF], such as scheduling [START_REF] Goren | Robustness and stability measures for scheduling: single-machine environment[END_REF][START_REF] Hazir | Robust scheduling and robustness measures for the discrete time/cost trade-off problem[END_REF], facility location [START_REF] Alumur | Hub location under uncertainty[END_REF][START_REF] Baron | Facility location: A robust optimization approach[END_REF][START_REF] Gulpinar | Robust strategies for facility location under uncertainty[END_REF][START_REF] Minoux | Robust network optimization under polyhedral demand uncertainty is np-hard[END_REF], inventory [START_REF] Ben-Tal | Robust multi-echelon multi-period inventory control[END_REF][START_REF] Bienstock | Computing robust basestock levels[END_REF], finance [START_REF] Bertsimas | Robust multiperiod portfolio management in the presence of transaction costs[END_REF]22,[START_REF] Gulpinar | Worst-case robust decisions for multi-period mean-variance portfolio optimization[END_REF][START_REF] Pinar | Robust scenario optimization based on downside-risk measure for multi-period portfolio selection[END_REF][START_REF] Schoettle | Robustness properties of mean-variance portfolios[END_REF], queuing networks, stochastic systems and game theory [START_REF] Bertsimas | Robust and data-driven optimization approaches to call centers[END_REF][START_REF] Kardes | Discounted robust stochastic games and an application to queueing control[END_REF][START_REF] Kirkizlar | Robustness of efficient server assignment policies to service time distributions in finite-buffered lines[END_REF][START_REF] Ordóñez | Wardrop equilibria with risk-averse users[END_REF], machine learning and statistics [START_REF] Ben-Tal | Chance constrained uncertain classification via robust optimization[END_REF][START_REF] Xu | Robust PCA via outlier pursuit[END_REF][START_REF] Xu | Robust regression and lasso[END_REF], and energy systems [START_REF] Bertsimas | Performance analysis of queueing networks via robust optimization[END_REF][START_REF] Ribas | Optimization under uncertainty of the integrated oil supply chain using stochastic and robust programming[END_REF].

The robust optimization approach considered here is then, an alternative to stochastic programming where the optimization is done over a set of scenarios. A scenario denotes the way to structure the uncertain data, where two common ways of modeling are interval or discrete data. Interesting definitions for a robust model and a robust solution are introduced by [START_REF] Kouvelis | Robust discrete optimization and its applications[END_REF][START_REF] Mulvey | Robust optimization of large-scale systems[END_REF]. Roughly, a robust solution is related to the robust optimization criteria. For instance, whenever a minmax objective function is addressed, a robust solution is the one which minimizes the worst case. For the sake of clarity, let us consider the classical Robust Shortest Path (RSP) problem as an example to show the use of interval and discrete data. The RSP problem is defined on a digraph G = (V, A), where V denotes the vertex-set while A is the set of arcs. An origin vertex t ∈ V and a destination vertex d ∈ V are given, but the costs associated with each arc (i, j) ∈ A are uncertain. Thus, such uncertain data can be modeled as an interval (RSP-I) [l ij , u ij ], with l ij , u ij ∈ R, where u ij ≥ l ij ≥ 0, or else by a set of discrete scenarios (RSP-D) S = {1, 2, ..q}, where every scenario k ∈ S specifies a cost value c k ij for each arc. Without loss of generality, using the interval data, a scenario k is an assignment of arc costs c k ij ∈ [l ij , u ij ], for all (i, j) ∈ A. Three main components are related in the application of robust optimization methods. These components are: (i) the way uncertain data are modeled (e.g. with the use of scenarios), (ii) the selection of an appropriate robust optimization criterion such as minmax, minmax regret, minmax relative regret, α-robustness, bw -robustness, pw-robustness, referred here as Robust Optimization Criteria (ROC), and (iii) the choice of a mathematical model and methods to generate robust solutions [START_REF] Kouvelis | Robust discrete optimization and its applications[END_REF].

In this study, different ROC and their main applications are reviewed. Then, we introduce two Robust Classifications Criteria (RCC) that can be applied for measuring the robustness of both scenarios and solutions. The alternative RCC proposed here can be used independently of other criteria, as an additional support to classical ROC, or still as a tool for intensification in local search strategies. It is important to highlight that the proposed RCC are not optimization criteria, instead they are a mesure of quality based on ranking (classification) of solutions over all the scenarios considered. The remain of this work is organized as follows: a state-of-the-art on ROC is presented in Section 2, followed by a detailed description of the proposed RCC in Section 3. Finally, concluding remarks are given in Section 4.

State of the art on ROC

The robust optimization approach has been typically modeled with a set of scenarios defined with discrete or interval values [START_REF] Assavapokee | A new min-max regret robust optimization approach for interval data uncertainty[END_REF], as previously mentioned. In either case, decisions can be made according to one of the following ROC: minmax, minmax regret, minmax relative regret, lexicographical criteria, α-robustness, bwrobustness and pw-robustness, etc. These are the most common ROC to deal with robust optimization problems, and their use mainly depend on the application and the optimization goals. Below we review such criteria and provide some practice cases for them.

The minmax family criteria, i.e, the absolute minmax, the minmax regret and the minmax relative regret [START_REF] Roy | Robustness in operational research and decision aiding: A multifaceted issue[END_REF], are usually refereed as conservative criteria since they aim at minimizing the possible losses whenever the worst case scenario occurs [START_REF] Kouvelis | Robust discrete optimization and its applications[END_REF].

The minmax criterion has been initially developed for game theory by Von Neumann [START_REF] Neumann | Zur theorie der gesellschaftsspiele[END_REF] for a two-player zero-sum game. The minmax dual problem relies on maximizing the minimum gain, named maxmin. Both the minmax and the maxmin are used whenever the worst case scenario can imply a major damage. Extending the work of Von Neumann [START_REF] Neumann | Zur theorie der gesellschaftsspiele[END_REF], Wald proposed a non-probabilistic decision-making model based on the worst-case of a decision [START_REF] Wald | Contributions to the theory of statistical estimation and testing hypotheses[END_REF]. According to the author's definition, the decisions are ranked based on their worst-case outcomes. This strategy discards the worst case scenario among the possible decisions in an optimization process. Actually, the minmax criterion is one of the most studied ROC and has been successfully applied to different problems [START_REF] Ben-Tal | Robust optimization -methodology and applications[END_REF][START_REF] Kasperski | Discrete Optimization with Interval Data -Minmax Regret and Fuzzy Approach[END_REF][START_REF] Kouvelis | Robust discrete optimization and its applications[END_REF], such as: competitive situations, punctual risky decisions, robust shortest path [START_REF] Karasan | The robust shortest path problem with interval data[END_REF][START_REF] Montemanni | A branch and bound algorithm for the robust shortest path problem with interval data[END_REF][START_REF] Yu | On the robust shortest path problem[END_REF], robust minimum spanning tree [START_REF] Kasperski | On the approximability of robust spanning tree problems[END_REF][START_REF] Montemanni | A branch and bound algorithm for the robust spanning tree problem with interval data[END_REF][START_REF] Yaman | The robust spanning tree problem with interval data[END_REF], among others.

Another possible ROC is the lexicographic minmax introduced by Dresher [START_REF] Dresher | Games of Strategy[END_REF], which extends the work of Von Neumann known as the nucleolus of a matrix game in game theory. The idea consists in selecting a subset of optimal strategies, based on the optimal solution of minmax, which take advantage of the opponent player's mistakes. In the lexicographic minmax not only the worst case is minimized, as in the classical minmax. It also considers the second worst case, the third worst, etc. Therefore, the lexicographic minmax refines the concept of solution in the minmax approach, since it selects a unique set of outcomes, but not necessarily a unique solution (if there is more than one solution, all solutions selected have the same distribution).

Extending the work [START_REF] Dresher | Games of Strategy[END_REF], the lexicographic minmax has been studied by [START_REF] Ogryczak | On the lexicographic minimax approach to location problems[END_REF] to improve the minmax when the uncertain data are modeled with discrete scenarios. The author in [START_REF] Ogryczak | On the lexicographic minimax approach to location problems[END_REF] also showed that the lexicographic minmax complies with both "Pareto-Optimality Principle" and the "Principle of the Transfers", whereas the standard minmax may violate both principles. In accordance with the "Pareto-Optimality Principle" all the objective functions are treated on the same way without preferences and/or specific assumptions, and the Principle of the Transfers is commonly recognized as the essential axiom for equity measure [START_REF] Mandell | Modelling effectiveness-equity trade-offs in public service delivery systems[END_REF]. Finally, the author showed that the solutions obtained by the lexicographic minmax are better than those obtained by the minmax applying this criterion to location problems [START_REF] Ogryczak | On the lexicographic minimax approach to location problems[END_REF]. The lexicographic minmax has been successfully applied to allocation problems [START_REF] Luss | On equitable resource allocation problems: A lexicographic minimax approach[END_REF][START_REF] Wang | Lexicographic minimax approach to fair water allocation problem[END_REF], location problems [START_REF] Narasimhan | Efficient service location design in government services: A decision support system framework[END_REF][START_REF] Ogryczak | On the distribution approach to location problems[END_REF], and sensor node placement [START_REF] Abidin | Sensor node placement based on lexicographic minimax[END_REF], as well as it has been modeled and integrated to mathematical programming [START_REF] Kostreva | Equitable aggregations and multiple criteria analysis[END_REF][START_REF] Hooker | Combining equity and utilitarianism in a mathematical programming model[END_REF] The α-robustness has been proposed by Kalaï [START_REF] Kalaï | Lexicographic α-robustness: An alternative to min-max criteria[END_REF] to be less conservative than the minmax. It extends the lexicographic minmax and is applied whenever the uncertain data are modeled using discrete scenarios [START_REF] Ogryczak | On the lexicographic minimax approach to location problems[END_REF]. Both criteria, the lexicographic minmax and the α-robustness, rank solutions considering the worst scenarios. Concerning the α-robustness, a vector of solutions, called "ideal solutions" are defined. An ideal solution is the best solution obtained for each scenario, and it is used to compute deviations. Given a solution θ, an ideal solution θ * and a set of scenarios S, the cost of θ, also called distance, is the scenario k ∈ S where the difference between the cost of θ and the cost of θ * in scenario k is maximum. For example, considering a problem with two scenarios, if the ideal solution values for each scenario k ∈ S are given by cost(θ * , k) = {10, 8} and the cost of a solution θ for each scenario k ∈ S is cost(θ, k) = {15, 10}, then the maximum deviation between cost(θ, k) and cost(θ * , k) is equal to 5. Recently, this criterion is used to treat uncertain attribute evaluations in the outranking methods [START_REF] Durbach | Outranking under uncertainty using scenarios[END_REF] which build a list of preferences following a set of predetermined alternatives.

An alternative ROC to the minmax using discrete scenarios is presented by Bertsimas and Sim [START_REF] Bertsimas | Robust discrete optimization and network flows[END_REF]. The authors propose a robust integer programming model that allows to control the conservatism degree of a solution by using probabilistic bounds and violation constraints. Let n be the number of binary variables for a discrete optimization problem with uncertain data associated with the cost coefficients. Then, we solve the robust counterpart by solving n + 1 instances of the original problem. Besides, the authors have proposed an algorithm for robust network flows using their model. This criterion has been mostly used for solving facility location problems [START_REF] Averbakh | Facility location problems with uncertainty on the plane[END_REF], robust prize-collecting Steiner tree problems [START_REF] Álvarez-Miranda | Exact approaches for solving robust prize-collecting Steiner tree problems[END_REF], robust knapsack problem [START_REF] Monaci | Exact solution of the robust knapsack problem[END_REF] and the robust network loading problem with dynamic routing [START_REF] Mattia | The robust network loading problem with dynamic routing[END_REF].

Roy (2010) [START_REF] Roy | Robustness in operational research and decision aiding: A multifaceted issue[END_REF] argues the minmax approach fails to translate the robustness since it focuses only on minimizing the worst case. Thus, the robust optimization is defined in his work as the ability to prevent undesirable impacts when uncertain data are handled. The author proposed a new ROC as an alternative for the minmax, named bw-robustness. A non-negative value b establishes a threshold that cannot be exceeded on most of the scenarios, while the constant w defines the value that cannot be exceeded by any scenario represented as follows, w ≤ max θ min k (v k (θ)), where k is a scenario, θ is a feasible solution and v k (θ) is the cost of the feasible solution in a scenario. The bw-robustness is used only when the scenarios correspond to discrete values and the number of scenarios is very large. Like for the minmax family criteria, the bw-robustness can be addressed as bw-absolute robustness, bw-absolute deviation and relative regret bw-relative deviation. The bw-robustness has been successfully applied to the robust shortest path problem [START_REF] Gabrel | New models for the robust shortest path problem: complexity, resolution and generalization[END_REF] and to the robust military mission planning problem [START_REF] Tang | Robust mission planning based on nested genetic algorithm[END_REF] which consists of allocating resources and scheduling tasks during a military mission in order to protect the city borders.

The pw -robustness criterion is an extension of the bw -robustness criterion [START_REF] Gabrel | La pw-robustesse: pourquoi un nouveau critère de robustesse et comment l'appliquer?[END_REF]. Thus, a solution is said to be robust whenever it ensures a w value for all scenarios, and if it reaches a value b in a p percentage of scenarios.

Robust Classification Criteria

We suggest here two RCC for measuring the solutions quality, as well as the impact of the scenarios over the solutions, named robust absolute rank and robust mean rank. In terms of solutions quality, the general idea of the RCC is to provide an evaluation of solutions based on their evaluation over all the scenarios. They do not look only for avoiding the worst case, neither for computing the worst case, the second one, etc., like in the α-robustness, the bw-robustness and the pw-robustness. The RCC focus on the number of times a solution obtain the best results in its evaluation over a given set of scenarios. Thus, in terms of evaluating a solution, it means that a solution is a good one if it is good in a higher number of scenarios.

In terms of scenarios, the proposed criteria provide an evaluation considering the impact of the solutions found for a given scenario, by identifying the scenarios which produce a higher number of better solutions.

The proposed RCC are less conservative than the minmax family and the lexicographic family of criteria, and they can be applied to evaluate independently the impact of applying an individual solution, as well as deciding about the scenarios which has produced the best solutions. The RCC can be used as main evaluation criteria, as well as a decision support tool for existing ROC. An example for the latter is whenever one looks for avoiding the worst case, and after that to classify the remaining solutions, i.e. a two stage evaluation. These criteria provide complementary and useful information for intensification in local search for a given scenario. An example where the intensification can be done is whenever one deals with a robust version of a NP-hard problem which implies to handle a NP-hard problem per scenario.

Let us consider a number of feasible solutions. Then, a way to evaluate the solutions over all scenarios can be done by a classification, as well as to know which scenarios have a higher impact on the solutions. For each known feasible solution, the robust absolute rank denotes the number of times for which the considered solution is the best over all known solutions for a specific scenario. Whenever a solution is the best for a specific scenario, it is assigned one point. At the end, the number of times a solution has a minimal value, is kept. If for a given scenario, two or more solutions draw for best solution, they all count as best and one point is added to its robust absolute rank. Considering a solution, the higher is its robust absolute rank, the better the solution is. Considering a set of scenarios S, the robust absolute rank can also be applied for evaluating S by taking the sum of all robust absolute rank for each known solution of S.

The robust mean rank is computed for every solution considering each scenario. Let r be the position of a solution in a classification over a set of solutions. Then, for a given solution and considering a set of S scenarios, the solution that returns the best result for a specific scenario k receives one point, the one that follows two points, and the one that returns the worst result receives r th points. Whenever several solutions obtain the best result, they are all assigned one point. Whenever two solutions have the second best value, they are both assigned two points. For every solution and every scenario, the corresponding robust mean rank is equal to the mean number of points assigned to each solution. The smaller the robust mean rank, the better the corresponding solution is. Considering a scenario k, the robust mean rank can also be applied for evaluating S by taking the sum of the robust mean rank for each feasible solution of S.

An example for the RSP-D is provided in Figure 1. Tables 1 and2 summarize the corresponding values for some ROC and the proposed RCC. In Table 1, each line corresponds to a possible solution for the graph depicted in Figure 1. The next columns stand for their cost considering respectively, the first, the second and the third scenario. Then, the remaining columns contain respectively the values for the following criteria: minmax, minmax regret, and robust absolute rank. Table 2 presents the classification for each solution in each scenario according to the robust mean rank. The three columns of classification indicate the points assigned for each solution in each scenario. The last column indicates the robust mean rank per solution.

For the solution t-0-2-3-d, the robust absolute rank is set to a value of 2 because this solution is the best for two scenarios out of three scenarios. It can be noticed that the solution t -0 -3 -d stands for the best one using the mean, the minmax and the minmax regret criteria. On the contrary, the best solutions using the robust absolute rank and the robust mean rank are t -0 -2 -3 -d and t -1 -2 -4 -d because their cost evaluation is the best for a higher number of scenarios. In fact, for some applications, the robustness may enclose this idea: "robust solutions are those which are good and could be applied in most of the scenarios considered". Obviously, whenever a decision maker may avoid the worst case, these criteria cannot be applied alone. But, they can be coupled with a criteria from the minmax family considering the complementary information that can be obtained obtain with the proposed RCC (quality of solutions and the impact they have in the scenarios), opening opportunities for sensitivity analysis.

Concluding remarks

In spite of its simplicity, the proposed RCC enclose the idea of better solutions in a higher number of scenarios, as well as, they provide an easy way to identify the scenarios which has produced a higher number of better solutions. Contrary to the minmax family criteria and the lexicographic ROC, the proposed criteria provide a way to quantify a robust solution in a global perspective as the impact of the scenarios over the solutions. The RCC can be used as independent or be coupled with a ROC as a complementary information for the decision-making. A possible direction is to apply these RCC for intensification in local searches.

Figure 1 :

 1 Figure 1: An example of graph with uncertain data represented by a discrete set of values.

Table 1 :

 1 Evaluating solutions for the robust shortest path problem.

			Scenarios				Evaluation
	Solutions	costs C 1 C 2 C 3	Mean minmax	minmax regret	robust absolute rank
	t -0 -3 -d	10	10	7	9.00	10	4	1
	t -0 -2 -3 -d	13	7	7	9.00	13	7	2
	t -0 -2 -4 -d	11	8	9	9.67	11	5	1
	t -1 -4 -d	6	12	10	9.33	12	5	1
	t -1 -2 -3 -d	10	12	6	9.33	12	5	1
	t -1 -2 -4 -d	8	13	8	9.67	13	6	2
	robust absolute rank per scenario	2	2	4

Table 2 :

 2 Applying the robust mean rank.

	Solutions	Classification k = 1 k = 2 k = 3	robust mean rank per solution
	t -0 -3 -d	2	2	1	1.67
	t -0 -2 -3 -d	2	1	1	1.33
	t -0 -2 -4 -d	3	1	2	2.00
	t -1 -4 -d	1	3	2	2.00
	t -1 -2 -3 -d	1	3	2	2.00
	t -1 -2 -4 -d	1	2	1	1.33
	robust mean rank per scenario	1.83	2.00	1.33