Ravi Kiran

The Theory of Braids and Energetic Lattices II -Constrained Optimization by Disseminated Energy

The Theory of Braids and Energetic Lattices II -Constrained Optimization by Disseminated Energy 1 Notation

E : space under study; x, y points of E; P(E) : set of the subsets of E, also called classes; S, A : classes of E; T j the sibling classes of S π = π(E) : partition of E; π(S) : partial partition ( in short p.p.) of support S ∈ P(E)); the notation τ (S) is also used for p.p.

{S} p.p. with unique class S (when there is no ambiguity, {S} is just written S) ; D(E) set of all p.p. for all supports S ∈ P(E); ≤, ∧, ∨: when applied to partitions, are relative to the refinement ordering; : concatenation of classes and p.p. i.e. π(S) = S 1 S 2 ⇔ S 1 ∪ S 2 = S and S 1 ∩ S 2 = ∅; H = {π i , i ∈ I}: hierarchy, i.e. family of increasing partitions; cut π: partition of E into classes taken in H; Π(≤, H): set of all cuts of H, viewed as a lattice for the refinement ordering ω: energy, i.e. scalar function on D(E);

ω , ω , ω : ω-energetic ordering, infimum, and supremum, w.r.t. energy ω; Π(ω, H): ω-energetic lattice on the cuts of H; π * minimal cut in an energetic lattice; π * ϕ (resp. π * ∂ ) minimal cut in the energetic lattice of energy ω ϕ (resp. ω ∂ ).

Introduction

Two questions:

1/ How to introduce localization in constrained optimization (compare Everett with and without localization) 2/ Lagrange approach for hierarchies gives upperbounds only Lines of thought (history of the ideas) and plan of the paper 1 3 Two reminders 3.1 Hierarchies, climbing energies, and energetic lattices

We denote a partition of space E by π and a partial partition (p.p.) of subset S ⊆ E by π(S) [START_REF] Ronse | Partial partitions, partial connections and connective segmentation[END_REF]. The family of all partial partitions of E is D(E). A hierarchy of partitions (HOP) is a finite chain of partitions H = {π i , i ∈ [0, n]}, with π i ≤ π j , i < j, where ≤ stands for the refinement ordering. The minimal element π 0 of H is called the leaves partition, while the maximal element is the one class partition {E}, called the root. A cut of hierarchy H is a partition of E whose elements are composed of classes in H. The set of all cuts of H is Π(≤, H).

An energy ω : D → R + is a non-negative function that is defined on the family of partial partitions. The energy of a partial partition π(S) is often obtained by composition comp of the energies of its constituent classes T j . If the composition is the addition, we have

ω[π(S)] = comp{ω(T j ), T j S} = ω(T j ), T j S
The additive composition law is the most investigated one, but some problems require other laws, as supremum [START_REF] Soille | Constrained connectivity for hierarchical image partitioning and simplification[END_REF], [START_REF] Akcay | Automatic detection of geospatial objects using multiple hierarchical segmentations[END_REF], or infimum (e.g. composition of distances functions, in Ch. 4 of [START_REF] Kiran | Energetic-Lattice based optimization Phd thesis[END_REF]).

In [START_REF] Breiman | Classification and Regression Trees[END_REF], [START_REF] Salembier | Binary Partition Tree as an Efficient Representation for Image Processing, Segmentation, and Information Retrieval[END_REF], and [START_REF] Guigues | Scale-Sets Image Analysis[END_REF], where the composition law is the addition, one introduces the cut π * * = π * * (E) of minimal energy. This cut is calculated by aggregating, over all classes S ∈ H, the local minima π * * (S) which choose between the parent S and its children according to their energies, i.e.

π * * (S) = {S}, if ω(S) ≤ comp{ω(T j ), T j S} {T j , T j S} otherwise (1)
Cut π * * (E) is obtained by scanning the classes of H following a lexicographic order, and taking the provisional minimum in equation ( 1) according to a dynamic program.

As it is presented, this dynamic program does not extend to non linear energies. Take for example the hierarchy of figure 1a. The indicated energies hold on classes, and one goes to the p.p. by supremum composition. Algorithm (1) yields the cut π * * , whose energy 5 is indeed the lowest one, but the three other cuts in dotted lines have the same energy.

If we want to extend the dynamic program to non linear energies, it has to be presented differently, from the two notions of singularity and h-increasingness [START_REF] Serra | Hierarchy and Optima, in Discrete Geometry for Computer Imagery[END_REF] [12]: Definition 1. A energy ω is said to be singular when for all p.p. π(S) we have either ω({S}) < ω(π(S)), or ω({S}) > ω(π(S))

S ⊆ E.

It is said to be h-increasing when where the symbol indicates the concatenation of any p.p π 0 with support that is disjoint with S). A singular and h-increasing energy is said to be climbing. It is strictly climbing when the ≤ relations become < in implication [START_REF] Noyel | A New Spatio-Spectral Morphological Segmentation For Multi-Spectral Remote-Sensing Images[END_REF].

ω(π(S)) ≤ ω(π (S)) ⇒ ω(π(S) π 0 ) ≤ ω(π (S) π 0 ), ∀S ⊆ E. (2)
The energies composed by addition, by supremum, by infimum, and many other laws are are climbing [START_REF] Kiran | Global-local optimizations by hierarchical cuts and climbing energies[END_REF] [START_REF] Kiran | Braid of partitions[END_REF].

In algebra, a classical way to ensure the existence and the unicity of a minimum element in a set consists in providing the set with a lattice structure. For the set of cuts Π(≤, H) [START_REF] Kiran | Global-local optimizations by hierarchical cuts and climbing energies[END_REF] of hierarchy H we can proceed as follows. Given H and an energy ω, the cut π 1 ∈ Π(≤, H) is said to be less energetic than π 2 ∈ Π(≤, H), and one writes π 1 ω π 2 when in each class S of π 1 ∨ π 2 the energy of the partial partition of π 1 is smaller or equal to that of π 2: :

π 1 ω π 2 ⇔ {S ∈ π 1 ∨ π 2 ⇒ ω(π 1 {S}) ≤ ω(π 2 {S})} (3)
When the energy ω is climbing, the relation ω turns out to be an ordering, and we can state [START_REF] Kiran | Global-local optimizations by hierarchical cuts and climbing energies[END_REF] [14]:

Proposition 2.
The set of all cuts of H forms a complete lattice Π(ω, H) for the energetic ordering ω if and only if the energy ω is climbing.

When the energy ω is not climbing the property disappears as shown by the counter example of figure 1b andc. The minimal element π * of lattice Π(ω, H) is unique, and coincides with the cut of minimal energy π * * only when ω is strictly h-increasing.

Proposition 2 provides a theoretical background to dynamic programming since [START_REF] Breiman | Classification and Regression Trees[END_REF], [START_REF] Salembier | Binary Partition Tree as an Efficient Representation for Image Processing, Segmentation, and Information Retrieval[END_REF], [START_REF] Guigues | Scale-Sets Image Analysis[END_REF] speak of cut of minimal energy, but their algorithm calculates the minimal cut π * in the sense of the energetic lattice. Figure 2 depicts energetic order and lattice on a toy example.

The domain of validity of this approach encompasses the hierarchies and applies to the more general class of the braids, i.e. to families of partitions of E which is monitored by H, in the following sense [START_REF] Kiran | Braid of partitions[END_REF]:

∀π 1 , π 2 ∈ B ⇒ π 1 ∨ π 2 ∈ Π(E, H) \ {E} (4)

inf-modularity

Inf-modularity is the concern of a monotonicity condition on energies [START_REF] Kiran | Energetic-Lattice based optimization Phd thesis[END_REF]:

Definition 4. An energy ω ∂ : D(E) → R + on partial partitions is said inf-modular when for each p.p. π(S) of support S ∈ P(E) we have

ω ∂ ({S}) ≤ ω ∂ [π(S)],. (5)
which implies ω ∂ ({S}) ≤ ∧ω ∂ [π(S)] when π(S) spans the set of all p.p. of support S.

Super-modularity is defined by replacing ≤ by ≥ in the inequality [START_REF] Everett | Generalized Lagrange Multiplier Method for Solving Problems of Optimum Allocation of Resources[END_REF].

Examples of inf-modular energies For each energy, we define some functional on sets S, plus a law of composition which extends the functional to p.p.. We consider also a numerical function f on the space E inf-modular ω perimeter, Euler constant of S sum composition super-modular variance of

f in S sum composition (sup f -inf f ) in S sup composition
The area of S, and the integral of f α (x) over S, for any real number α, with sum composition, are both inf-and super-modular.

inf-modularity Vs subadditivity Inf-modularity is to be compared with subadditivity. Remember that a set-wise energy ω : P(E) → R is subadditive when ω(A∪B) ≤ ω(A)+ω(B), A, B ∈ P(E). This property, and more generally the sub-modularity, serves as substitute for the convexity when dealing with the subsets of E [4], .

For comparing inf-modularity versus subadditivity we must match sets and partial partitions in some sense. In particular, if T j , 1 ≤ j ≤ p are the classes of the p.p. π(S) and if ω ∂ [π(S)] is ≤ to the sum of the ω ∂ (T j ) then the inf-modular ω ∂ is also subadditive.

For example, in a hierarchy of partitions of the Euclidean plane, the perimeters ω ∂ of the classes generate an inf-modular and subadditive energy on the partial partitions. Unlike, the super-modular energy ω ∂ =(sup f -inf f ) is neither subadditive nor superadditive.

Constrained minimization by Lagrangian

In this section we present the classical Lagrangian based approach [START_REF] Everett | Generalized Lagrange Multiplier Method for Solving Problems of Optimum Allocation of Resources[END_REF] applied to constrained minimization in hierarchies [START_REF] Salembier | Binary Partition Tree as an Efficient Representation for Image Processing, Segmentation, and Information Retrieval[END_REF], [START_REF] Guigues | Scale-Sets Image Analysis[END_REF], and we show by means of a counter example that it does not result in the expected minimal cut [START_REF] Kiran | Energetic-Lattice based optimization Phd thesis[END_REF] [START_REF] Serra | Constrained optimization on hierarchies and braids of partitions submitted to[END_REF]. The need for a constrained minimal cut appears when the cuts are subject to conditions. Suppose for example that one wishes to transmit an image f at a given cost (defined by an upper-bound C of the number of transmitted bits), but with the best possible quality [START_REF] Salembier | Binary Partition Tree as an Efficient Representation for Image Processing, Segmentation, and Information Retrieval[END_REF]. A hierarchy H of segmentations of f has been performed, so that the question comes down to extract the minimal cut w.r.t. a so called objective energy ω ϕ among a set of cuts π which satisfy the cost constraint ω ∂ (π) ≤ C for some constraint energy ω ∂ .

Consider the hierarchy H of Figure 3, where the objective energy ω ϕ and the constraint energy ω ∂ are depicted for the classes. Their extensions to p.p. are obtained by addition of the classes, i.e. ω(π(S)) = T j π(S) ω(T j ). Further when we have equal parent and child energies, we pick the parent. Both ω ϕ and ω ∂ are climbing, and ω ∂ is also inf-modular (they have the same features as in [START_REF] Guigues | Scale-Sets Image Analysis[END_REF], [START_REF] Salembier | Binary Partition Tree as an Efficient Representation for Image Processing, Segmentation, and Information Retrieval[END_REF]). We want to find the cut π * ϕ of minimal energy ω ϕ which satisfies ω ∂ (π * ϕ ) ≤ C, where C is a cost here set to 7.5.

Introduce the family of Lagrangians {ω(λ) = ω ϕ + λω ∂ , λ ≥ 0}. The minimal cut of the energetic lattice (ω(λ), H) is denoted by π * (λ). For the chosen features of ω ϕ and ω ∂ , the energy ω ϕ [π * (λ)] increases with λ, and ω ∂ [π * (λ)] decreases [START_REF] Serra | Constrained optimization on hierarchies and braids of partitions submitted to[END_REF]. We have:

λ min cut π * (λ) ω[λ, π * (λ)] ω ϕ [π * (λ)] ω ∂ [π * (λ)] 0 ≤ λ < 2 (a, b, c, d, e, f ) 6 + 9λ 6 9 2 ≤ λ < 3.5 (a, b, c, d, i) 8 + 8λ 8 8 3.5 ≤ λ (g, h, i) 15 + 6λ 15 6
As a result, ω ∂ is never equal to the cost C = 7.5 at any time. Finally, the λ-cut π

* (λ * ) which minimizes ω ϕ (π * (λ) ) while satisfying ω ∂ (π * (λ)) ≤ C, is (g, h, i).
Consider now the two other cuts π = (g, c, d, i), and π = (a, b, h, i) which are not minimal cuts π * (λ). Cut π obviously provides a better minimum than the minimal λ-cut (g, h, i) since ω ∂ (π) = 7 (still below the cost C = 7.5), for an energy ω ϕ (π) = 11.5 (also smaller objective ω ϕ (g, h, i) = 15). And it is the same for π , since ω ∂ (π ) = 7 and ω ϕ (π ) = 11.5. There are thus several constrained minimal cuts for the energy ω ϕ , and none of them belongs the sequence {π * (λ), λ ≥ 0} of λ-minimal cuts! And we cannot take their infimum π ∧ π = (a, b, c, d, i) because ω ∂ (π ∧ π ) = 8, which is above the constraint C = 7.5. Uniqueless is lost even when the ω(λ) are strictly ioncreasing. We could bring the minimal λ-cut (g, h, i) closer to one of the optimal solutions π or π by techniques of small perturbations, but we cannot, by no mean, reduce the number of these optimal solutions 1 A similar trouble also arises in convex optimization [START_REF] Boyd | Convex optimization[END_REF], where the dual Lagrangian serves only as an upper bound on the optimum corresponding to the primal Lagrangian. In our words, π * (λ * ) provides only an upper-bound of the constrained minimal cuts.

Optimization by Disseminated Energy (ODE ?)

The above Lagrange type approach fails in finding the minimal cut, because the problem is not defined enough . It is implicitly assumed that a cut is characterized by its energy. Now we saw that the two different cuts may have the same conditional minimal energy (e.g. π and π in figure 3).

The initial intuition of Lagrange and Euler was to substitute an absolute minimum to the conditional one by changing the space. When dealing with numerical functions in Euclidean spaces, the Lagrangian is the tool which translates this intuition (and it works!), but it is not well adapted to a space of partitions. Can we express the same intuition by different means?

The energetic lattices offer an alternative approach, where both constraint and minimization can directly be defined on partitions and no longer on partitions via their energies. In 1 The lack of unicity, observed here on a toy example, becomes catastrophic for larger partitions. One easily proves that a binary hierarchy, with p levels and connected classes has more than 2 2 p-1 classes [START_REF] Serra | Exercices de probabilité[END_REF]. Even for a range of energies of 10 6 the correspondence "energy-partition" is far from being one-to-one. To give an idea, the number of cuts of a hierarchy with six levels only equals one hundred times the number of the humans on the earth (which was 7, 125 billions in 2013) this alternative method, we keep the same types of energies as in Lagrange formulation: an objective energy ω ϕ and a constraint energy ω ∂ , both climbing, with ω ∂ inf-modular. But the other inputs are different:

• the energy ω ϕ holds on a braid the cuts of a braidB, and the energy ω ∂ holds on the cuts of a hierarchy H, possibly different from B but with the same leaves;

• the previous scalar cost C is replaced by a cost cut π C , i.e. by a partition of the space Π(ω ϕ , B).

The families Π(B) and Π(H) of all cuts of B and H are the matter of three different lattices which interact:

• Π(B) = Π(≤,
). The minimal cut of Π(ω ϕ , B) is written π * ϕ = ωϕ {π, π ∈ Π(ω ϕ , B)}.
The following two problems will be treated separately: Note that the constraint condition is stated in the energetic lattice Π(ω ∂ , H), though the minimization occurs in the lattice Π(ω ϕ , B). Unlike, in the classical Lagrange approach, the same lattice of numbers is used for both constraint condition and minimization.

Problem 5

The problem 5 concerns the relations between the two lattices Π(≤, H) and Π(ω ∂ , H). It does not involve either the energy ω ϕ or the energetic lattice Π(ω ϕ , B), but uniquely ω ∂ .

An equivalence between energetic ordering ω ∂ and refinement ordering

In H, the energetic ordering w.r.t.

π(E) ≥ π C (6)
Conversely, if the inequality ( 6) is true, then each class S of π(E) contains a p.p. π C (S) of π C and by inf-modularity of ω ∂ , we have ω ∂ (S) ≤ ω ∂ (π C (S)), hence π ω ∂ π C . We can state: Proposition 7. When energy ω δ is inf-modular, then the set Π C of the cuts of H which are ω ∂ than π C is identical to the family of all cuts of H coarser than π C for the refinement ordering:

π ω ∂ π C ⇔ π ≥ π C π ∈ Π(H) (7)
Proposition 7 answers Problem 5. The key equivalence [START_REF] Mumford | Boundary Detection by Minimizing Functionals[END_REF] suggests to interpret the classes of π C as the set of leaves of a new hierarchy H , identical to H above and on π C , but where all classes below π C are removed (see Figure 4). The cuts π of H are exactly those of H that satisfy the constraint π ω ∂ π C . The set Π C = Π(≤, H ) turns out to be a complete lattice for the refinement order, with π C and E as extremal elements, hence a (pseudo) sub-lattice of Π(≤, H)2 . In the sub-lattice Π(≤, H ) absolute minimizations replace the constrained ones of lattice Π(≤, H) 3 .

Dualities The canonical dualities inherent to lattices lead to three variant of Proposition 7. Introduce the hierarchy H which is identical to H below and on π C , but where all classes above π C are removed. We have the following truth table:

π ω ∂ π C π ω ∂ π C inf-modular ω ∂ H H super-modular ω ∂ H H (8)
ω ∂ (π) = ∨{ω ∂ (T j ), T j π} + ε π ∈ D(E).
The arbitrary small number ε > 0 serves to ensure singularity. The energy ω ∂ is climbing and super-modular. Take the leaves partition for cost cut π C . According to Proposition 7, and to table [START_REF] Ronse | Partial partitions, partial connections and connective segmentation[END_REF], the infimum ω ∂ , obtained by dynamic program, is also the largest cut (for the refinement) whose non leave classes contain one type of marker only. [START_REF] Salembier | Binary Partition Tree as an Efficient Representation for Image Processing, Segmentation, and Information Retrieval[END_REF]. We find Problem 5 again, and the family Π C is thus equivalent to:

Scalar cost for classes

Π C = {π ≥ π C } = Π C
Note that one can make variable the cost parameter C, in accordance with the inf-modularity condition [START_REF] Kiran | Energetic-Lattice based optimization Phd thesis[END_REF].

An example of Problem 8 is proposed by P. Soille in [START_REF] Soille | Constrained connectivity for hierarchical image partitioning and simplification[END_REF] for the super-modular variant. A non negative function f is defined on E, in association with H. The energy ω ∂ at each node S is given by ω

∂ (S) = max[f (x), x ∈ S] -min[f (x), x ∈ S] (11)
and extended to p.p. by supremum. The mapping ω ∂ : D(E) → R + is obviously supermodular, and the largest π ω ∂ π C is given by π = ∨{π ≤ π C , π ∈ Π(≤, H)}. For Soille, H is generated by a condition on | f (x) |which is more and more relaxed along the increasing levels. He thus maximizes a gradient feature subject to the constraint of a bounded variation of the function on each class. But one can apply the super-modular energy ω ∂ of Relation [START_REF] Serra | Hierarchy and Optima, in Discrete Geometry for Computer Imagery[END_REF] to any hierarchy.

7 Problem 6

Case of a hierarchy

We firstly treat the case when the braid B is identical the the hierarchy H. Then, owing to the equivalence [START_REF] Mumford | Boundary Detection by Minimizing Functionals[END_REF], the problem 6 amounts to find the minimal cut of H w.r.t. ω ϕ , a question that we already know how to treat. The minimization is understood in the ω ϕenergetic lattice Π(ω ϕ , H ) relative to hierarchy H . This minimal cut π * ϕ is unique, since the energy ω ϕ is climbing, and its energy ω ϕ (π * ϕ ) is minimal in the energetic lattice Π(ω ϕ , H), conditional upon π ω ∂ π C . Proposition 9. When ω ϕ and ω ∂ are climbing energies, and in addition ω ∂ is inf-modular, then the minimal cut π * ϕ (π C ) of the ω ϕ -energetic lattice Π(ω ϕ , H), subject to be ω ∂ π C , is also the minimal cut in the energetic lattice Π(ω ϕ , H ).

(similar statements for the three other cases of table [START_REF] Kiran | Energetic-Lattice based optimization Phd thesis[END_REF]. The optimal cutπ * ϕ (π C ) is computed by a dynamic programing where the climbing process is restricted to the regions of H which are above π C .

The particular case when, in addition, ω ϕ is super-modular is somehow trivial. It suffices to apply Proposition 7 by replacing "ω ϕ sup-modular" by "ω ∂ inf-modular" since then the constrained minimal cut π * ϕ (π C ) coincides with π C (Proposition 7). As an example, we can revisit the counter-example of figure 3. The two cuts π and π are minimal, in Lagrange sense, for the scalar cost C = 7.5, with ω ∂ (π) = ω ∂ (π ) = 7 though ω ∂ (π ∧ π ) = 8 (i.e. above the cost). If now the scale cost is replaced by the cut π C = (a, b, c, d, i), then both π and π belong to Π(≤, H ) as well as their refinement infimum π ∧ π , which turns out be π C .

A constraint ω ∂ for describing proximity

The spatialization brought by the partition constraint π C may serve to express proximity criteria such as an image segmentation close to some ground truth, or a population who whishes to live near cities, or near the sea, etc.. Denote by A this pole of attraction, hence a set, and by f A a convex numerical function which decrease rapidly near A and more slowly with the distance to A. For example, one can take f A = [1 -d(x,A) dmax(x,A) ] α where d(x, A) stands for the distance from point x ∈ E to set A [START_REF] Kiran | Fusions of Ground Truths and of Hierarchies of Segmentations[END_REF]. The exponent α ≥ 0 which appears in f A modulates the importance of the pole A. For α = 0 the optimal cut π * ϕ (π C ) is ∂A itself, for 0 < α < 1, the positive influence of the proximity reduces as α increases, and for α > 1 the close classes are disadvantaged.

The continuation is exactly that described in section 6.2 with the energy ω ∂ of relation [START_REF] Serra | Hierarchy and Optima, in Discrete Geometry for Computer Imagery[END_REF] for f = f A , and with a given upper-bound C. The parameter C represents the largest variation of f A acceptable in each class S. Therefore, for 0 < α < 1 the minimal cut π C of the energetic lattice Π(ω ∂ , H) has small classes near the pole A, and larger ones as moving away from A.

Two examples

Here are two examples of optimization by disseminated energy which involve constraints of proximity.

Minimization subject to ground truth It happens that some manual drawing A accompanies an image to segment, and indicates some essential features to preserve [START_REF] Kiran | Fusions of Ground Truths and of Hierarchies of Segmentations[END_REF]. Suppose that a hierarchy of segmentations H has been computed on the image (by increasing watersheds, or by connected filters, etc.), and that one seeks the optimal the cut w.r.t. Mumford and Shah energy, denoted here by ω ϕ . We want to improve the optimization by tacking the drawing A into account.

The process comprises two steps:

1. Calculate the minimal cut π C of Π(ω ∂ , H) for the super-modular energy ω ∂ defined by [START_REF] Serra | Hierarchy and Optima, in Discrete Geometry for Computer Imagery[END_REF] and for a given upper-bound C,

calculate the minimal cut π

* ϕ (π k ) of the lattice Π(≤, H ) of the cuts ≤ π C .
Space distribution of a service The administrative structure of France comprises seven levels. This hierarchy H is composed of the quarters (in cities), the communes, the communes communities, the counties, the departments, the regions, and the country itself. Because of their climate, or the proximity of the sea, some regions attract retired persons, a phenomenon which leads to some distortions. For example, the distribution of the physicians is concentrated around the cities, whereas the recent retired populations live in housing estates, usually created in the countryside (see C. Voiron's works). How to find an optimal matching? Consider an attractive region R. Some statistical surveys to the physicians allow us to allocate a quality index ω ϕ (S) to each class S of H. This index is a positive number which depends on the proximity to the city center, to services (schools, entertainment), to the sea, to the highways, etc.. Some of these parameters are defined at the level of the quarter, other for larger classes. In addition, the index takes into account the tax advantages given by some communes or some departments. All in all, the energy ω ϕ can increase or decrease when going up in the administrative hierarchy. We admit that the quality index of each p.p. is the sum of the indexes of its classes: this makes sense and permit to interpret ω ϕ as an energy on H.

The constraint energy ω ∂ is defined like in the previous example, from the convex function f A of the distance to the housing estates A, with C as maximal acceptable distance. The minimization process is then led in two steps as in the previous example.

Logical combinations of the constraints

In the multi-constraints situations, the minimization of ω ϕ becomes subject to p constrained energies ω ∂j and p cost partitions π Cj , 1 ≤ j ≤ p. We draw from Relation (7) that, for ω ∂ inf-modular, the logical intersection (resp. union) of p constraints π ω ∂j π C i is equivalent to the unique condition π ≥ ∨{π Cj , 1 ≤ j ≤ p} (resp. π ≥ ∧{π Cj , 1 ≤ j ≤ p}), which brings us back to the scalar case. Note that the situation when one constraint at least is satisfied cannot be solved by a Lagrangian based approach.

Multi-constrained situations occur with multi-spectral images [START_REF] Noyel | A New Spatio-Spectral Morphological Segmentation For Multi-Spectral Remote-Sensing Images[END_REF], [START_REF] Valero | Hyperspectral image representation and processing with binary partition trees[END_REF] or also with color images. One seeks the largest partition into classes where each color of f varies at most by C 1 for the reds, C 2 for the greens, and C 3 for the blues. A solution can be the following. A hierarchy H of segmentations of the image color f has been obtained from the luminance. It yields the refinement lattice Π(≤, H). The energy ω ϕ to minimize is climbing, e.g. Mumforf and Shah functional, and holds on the luminance. The constraints are three sup-modular functions ω ∂j (S) = max[f j (x), x ∈ S] -min[f j (x), x ∈ S] j ∈ [START_REF] Akcay | Automatic detection of geospatial objects using multiple hierarchical segmentations[END_REF][START_REF] Noyel | A New Spatio-Spectral Morphological Segmentation For Multi-Spectral Remote-Sensing Images[END_REF][START_REF] Breiman | Classification and Regression Trees[END_REF] (

which must be ≤ kj respectively. These three conditions yield to three constraint partitions π Cj of refinement supremum π C = ∨π Cj . The problem amounts now to find the minimal cut in the energetic lattice Π( ϕ , H ) where H is the partial hierarchy identical to H below and on π C , and where all classes above π C are removed.

Conclusion

An alternative solution to the constrained optimization problem has been proposed. The classical technique, which goes back to Lagrange, consists in 1. giving a numerical value to each element (e.g. in giving an energy to each partition), and minimizing this numerical function, 2. setting the problem in a new space, where the constrained optimization becomes an absolute one.

We have shown, by the toy example of figure 3, that in case of partitions, the first point was not sufficient. A partition should not be equivalent to a significant energy. Indeed, Lagrange method works if we introduce some additional constraint which restricts the domain of the solutions.

In the proposed alternative, the partitions are not compared via their energies, but by an ordering relation which diretcly holds on these partitions, and generates the so called energetic lattice. In the energetic lattice perspective, the second point, above, is expressed by the creation of a new hierarchy, where the energetic minima become absolute.

The two methods do not exactly address the same family of applications. If the numerical value (energy, cost) is the dominant parameter of the problem, then lagrange approach is probably better adapted, though it remains under-determined. If the spatial dissemination of the energy is the most important feature of the problem, then the proposed altenative by energetic lattices will be more adapted.

Figure 1 :

 1 Figure 1: a)In case of ∨-composition, there is a unique minimal cut π * and its energy is minimal, but other cuts can have the same energy. b) and c) depict a non h -increasing energy ω(π) which depends on the number of classes of the p.p. π. The two cuts surrounded by ellipses are minimal (hence no energetic lattice here), but none of them is obtained by dynamic program, which gives the cut in grey.

Figure 2 :

 2 Figure 2: Three cuts of a hierarchy. The energies ω are indicated above the classes are composed by sum. We have π 3 ω π 2 and π 3 ω π 1 , but π 1 and π 2 are not comparable.

Figure 3 :

 3 Figure 3: Bottom left, a hierarchyH . The two trees of the top row indicate the two energiesω ϕ and ω ∂ , written in the corresponding classes. π and π are two cuts of H. Bottom right, the values indicated in the nodes are the energies obtained by equating parent and child energies. Their level sets give the minimal cuts w.r.t. ω(λ). They are drawn in dotted lines for λ = 1, 3, 4 as π * 1 , π * 3 and π * 4 .

Problem 5 .Problem 6 .

 56 Characterize the family Π C of cuts of H which are ω ∂ than π C , Find the minimal cut in the energetic lattice Π(ω ϕ , B) subject to be ω ∂ π C .

  ω ∂ and that by refinement are linked. We can see it by comparing π = π(E) ∈ Π C to π C . Consider the class S C of π C . As H is a hierarchy, S C is 1. either the support of a p.p. π(S C ) of π(E), i.e. π(S C ) = π(E) S C 2. or a class of a p.p. π(S) of π C whose support is the class S of π, i.e. π(S) = π(E) S, with S C ⊆ S.

Figure 4 :

 4 Figure 4: Left: initial hierarchy H; Right:new hierarchy H , formed by all classes above π C , and completed by the leaves.

Figure 5 :

 5 Figure 5: Example of marker & propagation strategy (by courtesy of Ph. salembier). Top: hierarchy of partitions where two markers are indicated. Bottom: result of the propagation process.

Let us go back to Problem 5 .Problem 8 .

 58 Can we replace, the cost partition π C by a numerical cost C acting on the classes? A model of this type is studied in[START_REF] Kiran | Energetic-Lattice based optimization Phd thesis[END_REF] section 2.40, and stated as follows: Let H be a hierarchy on E, and C a non negative cost. Given the inf-modular energy ω ∂ , with ω ∂ (E) ≤ C, find the family Π C of cuts π of H:π = {S | ω ∂ (S) ≤ C}(10)whose each class S has an energy ≤ C.

Figure 6 :

 6 Figure 6: Minimal cut π C . The + classes S satisfy ω ∂ (S) > C, and the -classes ω ∂ (S) ≤ C .

  B), lattice w.r.t. the refinement ordering ≤, with the leaves as minimal cut and E as maximal one. The set Π(H) = Π(≤, H) is usually a sub-lattice of Π(≤, B)• Π(ω ϕ , B) (resp. Π(ω ∂ , H)),lattice w.r.t. the energetic ordering w.r.t. ω ϕ , of order ϕ and infimum ωϕ (resp. the energetic ordering w.r.t. ω ∂ , of order ∂ and infimum ω ∂

("pseudo" because ΠC and Π(≤, H) have not the same leaves

Lagrange's intuition is met again, but differently!


Lucas Nussbaum
email: lucas.nussbaum@loria.fr

Towards Trustworthy Testbeds thanks to Throughout Testing

Keywords: experimentation, testbeds, automated testing, regression testing, reproducible research

When using testbeds in the context of experimental computer science, the ability to produce trustworthy and reproducible experiments results depends greatly on the trustworthiness of the infrastructure itself. Unfortunately, several factors many issues such as software misconfiguration, hardware heterogeneity, or service failures, can remain undetected and affect the quality of experimental results. This paper presents the design and implementation of an automated testbed testing framework. This framework was deployed in the context of the Grid'5000 project, and uncovered more than one hundred of issues.

I. INTRODUCTION

Reproducibility has been the focus of a lot of interest over the recent years, in science in general, and in computer science specifically. But most of this focus has been targeted at the reproducibility of data analysis, which is usually handled by a pipeline [START_REF] Peng | Reproducible research[END_REF] of several steps involving various tools, starting from measured data and going up to figures and tables included in an article. The various steps of that pipeline involve code for pre-processing the measured data, data analysis, and data presentation. However, this focus on reproducibility of data analysis ignores the important question of how measured data is produced.

Experimental computer science generally involves two main methods to acquire data about systems under test: simulation, and experimentation on testbeds. Experimenting on a testbed is a challenging task, and usually involves many different tools: the testbed itself, of course, but also experiment orchestration solutions [START_REF] Buchert | A survey of general-purpose experiment management tools for distributed systems[END_REF] ranging from shell scripts to complex frameworks, load or failure injectors, emulation solutions, measurement tools, etc. Each of those components has a huge impact on the experiment and the results that will be obtained from it. In theory, experimenters should include a qualification and calibration phase in their experiments, and confirm that this whole stack meets its specification. But unfortunately this is very rarely done in practice, probably due to lack of time or adequate tools.

Still, assessing the correctness of software, e.g. with software testing techniques, is a relatively well-understood process [START_REF] Myers | The art of software testing[END_REF]. But the bottom layer of the stack, that is, the testbed itself, raises specific challenges: testing infrastructure is an entirely different story. The complex mix of software and hardware, deployed at scale, provides potential for many difficult-to-detect issues, such as hardware misconfigurations or failures, or software bugs that happen randomly or only at scale. This paper describes work that was carried out in the context of the Grid'5000 testbed in order to systematically test the infrastructure and its services, with the goal of increasing the reliability and the trustworthiness of the testbed by uncovering problems that would otherwise harm the repeatability and the reproducibility of experiments.

The paper is structured as follows. Section II provides the necessary context about the Grid'5000 testbed. Section III details motivations for this work, and specific challenges that were encountered. Then, Section IV describes the solution that was implemented, before some results are discussed in Section V. Finally, related work is presented in Section VI before the paper is concluded in Section VII.

II. CONTEXT: THE GRID'5000 TESTBED

This section provides some background information about the Grid'5000 testbed, and about the way it is being operated, in order to support the design choices explained later.

The Grid'5000 project was initiated in 2003 with the goal to provide a testbed to experiment on Grid computing. The focus later moved to become a versatile testbed serving other areas of distributed computing (P2P, HPC, Cloud, Big Data, networking). The testbed itself was open to users in 2005. Each year, the testbed sees about 550 active users (users making at least one resource reservation) that produce about 100 publications.

Grid'5000 is currently composed of 8 sites (Figure 1) located in France and in Luxembourg. Each Grid'5000 site is composed of one or more sets of homogeneous machines called clusters. All machines from the same cluster are usually bought at the same time. At the time of writing, Grid'5000 has a total of 32 clusters, composed of a total of 894 nodes. At the networking level, all sites are interconnected with a dedicated 10 Gbps backbone network. Some specific hardware is also available on Grid'5000: various generations of HPC networks (mostly Infiniband), The main Grid'5000 features and services are:

Grenoble

• Resources description and discovery: a REST API (called the Reference API) provides detailed information about all resources in the testbed. Each time a node boots, its description is verified by a tool called g5kchecks that collects information using various inventory tools [START_REF] Margery | Resources Description, Selection, Reservation and Verification on a Large-scale Testbed[END_REF], to ensure that the Reference API contains correct and up-to-date information.

• Resources reservation: a resource manager (OAR [START_REF] Capit | A batch scheduler with high level components[END_REF]) is used by users to reserve resources for a specified duration. A rather complex Usage Policy 1 ensures fair sharing of resources between users during the day, while large reservations (generally made in advance) can use all resources at night and during weekends. • Nodes reconfiguration: the testbed provides a default (called standard ) environment where users do not have root access, similarly to what is available on traditional HPC clusters. On top of that, bare-metal deployment using Kadeploy [START_REF] Jeanvoine | Kadeploy3: Efficient and Scalable Operating System Provisioning for Clusters[END_REF] provides users with the ability to run custom operating system images and get root access. The Grid'5000 team provides a number of images (called reference environments), and users can also create custom environments. Out-of-band consoles to nodes are also available to users. • Network reconfiguration: the KaVLAN tool provides the ability to reconfigure the network. Each node's network interface (and nodes have up to four network interfaces) can be put in a different VLAN, which are reserved using OAR. This is typically used for 1 https://www.grid5000.fr/w/Grid5000:UsagePolicy cloud experiments [START_REF] Balouek | Adding virtualization capabilities to the Grid'5000 testbed[END_REF] or networking experiments. Additionally, those VLANs can also be propagated inside the backbone links, providing isolation for multi-site experiments.

• Network and power monitoring: the Kwapi tool [START_REF] Clouet | A Unified Monitoring Framework for Energy Consumption and Network Traffic[END_REF] provides an API, a live visualization interface and an archive of measurements of network traffic and power consumption of all nodes of the testbed, captured at high frequency. While the testbed is distributed, the Grid'5000 engineers work as a single team that manages all sites in a single administrative domain. Each site is still assigned to a specific engineer (mainly in order to build knowledge about local specificities, and to perform maintenance in machine rooms), but the configuration of services is managed centrally, through the use of a configuration management system (Puppet).

III. MOTIVATIONS

A. Very few bugs are reported

Reporting bugs or asking technical questions correctly is a difficult process [START_REF] Tatham | How to report bugs effectively[END_REF], [START_REF] Raymond | How to ask questions the smart way[END_REF]. Typical users of testbeds (PhD students or post-doctoral students) rarely have that skill, or lack the confidence to report a bug about an infrastructure that they do not fully understand. In the context of Grid'5000, the fact that the team is geographically distributed also makes it hard to talk to a local contact that could confirm the problem informally. As a result, we receive very few bugs from users, despite, as we will show later, a large number of issues that could and should be reported.

Testbed operators would be in a good position to find and report such issues, as they clearly have the expertise about how the testbed should behave. But they often have limited experience of using the testbed, especially of the large variety of services that are offered to users, and as a result they are unlikely to face all the problems that users encounter.

B. But many bugs should be reported

Testbeds such as Grid'5000 can produce a large number of different and interesting issues.

A first obvious factor is its scale: 8 sites, 32 clusters and 894 nodes provide plenty of potential for subtle problems. Also, while methods to standardize software configuration at scale are reasonably well understood (e.g. configuration management), hardware is much more difficult to deal with: its configuration sometimes requires manual steps (inside BIOS for example), it tends to fail much more randomly than software (for example, due to aging), and exhibits silent and subtle failure patterns (as a real example: vibrations causing screws attaching hard disk drives to become loose, causing additional vibrations, that can have a performance impact [START_REF] Gregg | Visualizing system latency[END_REF]).

Another, less obvious factor is the software stack and the ecosystem of services deployed on the testbed. Some core services are heavily used, but next to them, testbeds are always trying to design new services to address new experimentation needs. When they are first made available to the public, they rarely immediately pick up a strong user base, able to detect issues as soon as they occur. As a result, it is not unusual for a new service to be broken for a long period of time without testbed operators being aware, which is, of course, detrimental to attracting users.

C. And bugs can have dramatic consequences

In a testbed where most of the users are interested in measuring performance, subtle bugs can have a huge impact. For example, a misconfigured service or node could reduce performance by 5% or 10%, and thus lead experimenters to wrong conclusions about the solutions they are comparing, which could result in the need to retract a paper. Example cases where this could happen, all based on real facts, are:

• Different CPU settings, such as power management (Cstates), hyperthreading, or turbo boost; • Different disk firmware version;

• Different cache settings in a disk drive;

• Cabling issue that would cause wrong measurements by testbed-managed monitoring services (e.g. measuring the power consumption of another one). In addition, there are also many problems that can be found at the software side, causing services to be unreliable and making it much harder to automate experiments.

IV. DESIGN OF OUR TESTBED TESTING FRAMEWORK

In order to design a testbed testing framework, we leveraged the Jenkins automation server to run testing scripts. But we had to work around several limitations of Jenkins through external developments, most notably for tests scheduling, and analyzing and summarizing results. The following paragraphs explore each of those aspects.

Overall, we tried to build on the widely accepted best practices in software engineering about test suites, continuous integration (CI) and continuous delivery (CD), but had to adjust because of specifics of the context, and of our goals.

A. Jenkins automation server

Jenkins [START_REF]Jenkins -build great things at scale[END_REF] is the de facto standard for automating processes. In a nutshell, it can be seen as the cron Unix service on steroids. Using Jenkins, one can define jobs (tasks) that are executed in a specified environment, started by various means. The result and output of jobs are stored by Jenkins (as well as historical data).

Jenkins can be extended through plugins. A central plugin for our work was the Matrix Project Plugin, that adds support for defining jobs as matrices of several options. We used that for most tests in order to cover all possible configurations. For example, the test_environments job is in charge of testing the deployment of each of the 14 reference environments provided by the technical team, on each of the 32 clusters, resulting on 448 configurations for that test alone. Another related useful plugin was the Matrix Reloaded Plugin, that adds support for restarting a subset of configurations in a Matrix job.

Several other plugins also proved useful, such as the Build Timeout Plugin (to work around unexpected problems in some test scripts).

However, Jenkins alone proved insufficient for our needs, mainly for two aspects: fine-grained job scheduling, and analyzing and summarizing results. How we addressed those is detailed in the following sections.

B. Job scheduling

The scheduling of test jobs on the testbed was difficult to design (and a challenge that caused a previous iteration of work on this topic to fail). The requirements are fairly complex. First, different kinds of tests need to be addressed: some that focus on software, and only require one node per cluster; other that focus on hardware, and require all nodes from a cluster. Second, the scheduling must handle the fact that the resources might not be available (because of resources already reserved, or resources reservations made in advance for the future, that will prevent the allocation of resources for the required duration). Third, the scheduling must avoid disrupting other usages of the testbed.

Submitting test jobs as normal resources reservations, and waiting until resources are allocated, is not an option because: (1) Jenkins has a limited number of workers (job slots), and a pending reservation would use such for slot, possibly for days; [START_REF] Buchert | A survey of general-purpose experiment management tools for distributed systems[END_REF] The test jobs would compete with usermade resources reservations, and possibly block resources when users would want to use them.

Also, submitting jobs at the same time every day or week is not an option either, because it would be unlikely that the resources would be available.

The solution that was implemented was a tool external to Jenkins that would, for each configuration of each test job, and on a regular basis (every 10 minutes): (1) query the status of the configuration, and make a decision about whether a new run should be attempted, based on the current state of the test (successful, failed) and on a per-job delay between attempts; (2) evaluate the status of the testbed to determine, using a basic analysis, if the job could start immediately; (3) start the job, and if it ends up not being scheduled by the testbed's resource manager after a few minutes (due to conditions that were not considered in step 2, cancel it (and mark it as unstable in Jenkins).

As a result, test jobs are only scheduled when resources are available, and as frequently as possible.

To further reduce the impact on users, two additional rules have been implemented. First, the scheduler avoids starting test jobs during peak hours (8 am-9:30 am, 12:30 pm-2:30 pm), that is, when most users are likely to start working on Grid'5000 and reserving resources. Second, the scheduler never starts two test jobs simultaneously on the same site.

On the busiest sites, this policy sometimes caused test jobs to be delayed for several days as resources were permanently reserved by users. For some jobs where partial results where particularly useful, specific test configurations for running the test on a single node or on all available nodes were added.

C. Analyzing and summarizing results

Another need that was not well served by Jenkins alone is the ability to provide a useful summary of the results. There are several different requirements: (1) per test status (for all sites or clusters); (2) per-site or per-cluster status (for all tests); (3) historical perspective.

A per test status is reasonably well provided by Jenkins, but is unfortunately made rather unusable due to the unstable status for jobs that were started but could not be scheduled. Jenkins does not provide a way to build a per-site status. Jenkins provides some historical perspective, using weatherlike icons for each job, but it was insufficient for our needs.

To meet those needs, we designed an external status page by exporting data from Jenkins using its REST API 2 . That page (Figure 2) provides a table summarizing the status (current success percentage) for each site and test, and then a list of all failures that can be filtered using basic Javascript. Each failure can be annotated by engineers, for example to mention the corresponding bug.

Using the same method, we wrote a plugin for the Munin monitoring tool to keep historical data about each job and each site (Figure 3).

D. Why Jenkins, after all?

Due to the large number of Jenkins limitations that were worked-around, one could wonder if using Jenkins as a basis was really a good choice in the first place. We still believe it is, because (1) Jenkins provides a clean execution environment for scripts, with a queue to avoid overloading, the ability for users to trigger manual builds through a web interface; (2) Jenkins provides a storage system for test logs (and optionally, to store artifacts about test runs, such as raw data files, that could be useful in the future), the history of build results, and the ability to browse those test logs through a web interface.

Re-developing those features could have been an option, but would have resulted in significant development work. Additionally, Jenkins is also used for more traditional continuous integration tasks, and it makes sense to keep those CI tasks and testbed testing in the same tool in order to combine them. For example, there are CI tasks that build development 2 Which, it is worth noting, is extremely well designed: it provides a way to get data about all jobs with a configurable level of detail in just one HTTP request. versions of software, and then run testbed tests with those development versions installed, in order to evaluate whether those versions are suitable for release.

E. Test scripts

The goal of test scripts should be to exhibit issues, but also to provide sufficient information to testbed operators to understand and fix the issue. One important limitation of bug reports submitted by users is that issues are described as the users see them, and usually not with all the information that testbed operators would like to have. This problem can be avoided using an automated testing framework only if the scripts are carefully designed in a way that provides that information.

For that reason, we wrote the test scripts using rather simple tools, and performing steps that would be close to what one would use when trying to reproduce a problem manually (which is considered a good practice for automation [START_REF] Limoncelli | Automation should be like iron man, not ultron[END_REF]).

As Grid'5000 is documented through a series of tutorials, an option that was considered was to use the content of those tutorials as the list of actions that would be automated and tested. If successful, it would have ensured that tutorials continue to work over time (which has been a problem in the past). However, this idea was rejected because (1) tutorials are designed with pedagogy in mind, not with test coverage;

(2) most tutorials have several options (paths) at one point or another, making it difficult to automate. Therefore, for now we focused on simpler tests that cover the features of the testbed that are known to fail the most frequently, independently from how they are used in tutorials.

At the time of writing, the following tests have been developed and are in production:

• refapi : Check (1) the conformance of the description of each node in the Reference API compared to a schema;

(2) That nodes of each cluster are homogeneous in terms of hardware configuration, according to their description in the Reference API. Overall, this currently results in a total of 751 test configurations. Other tests will be added in the future. The kwapi test should be extended to cover network traffic measurements. Other aspects of the testbed's network configuration could be tested, such as MTU settings or support for multicast. Also, at the software level, the tools for automated deployment of OpenStack and Ceph should be tested on all testbeds.

V. RESULTS AND DISCUSSION

During the course of this work, 118 bugs were filed in the Grid'5000 bug tracking system, of which 84 have already been fixed. This includes issues that were directly found by the tests, but also problems that were discovered while writing tests, as writing scripts that should run on every cluster and site proved to be a good way to uncover various usability issues (e.g. differences between sites that are not described in the Reference API).

Here are a few examples of issues that were found in the process3 : ). Specifically, the out-of-band consoles service, which was thought to be reliable, was actually failing frequently (bugs 7770, 7362, 7570, 7325, 7466, 7574, 7575, 7411, 7576). • Some configuration problems were detected in the images that we provide. The network configuration was invalid on one cluster for two images (bug 7342, 7302). The Infiniband stack was randomly failing to start on boot due to an interesting bug (Figure 4). • A hardware issue causing random reboots on one of the older clusters (the Grenoble adonis cluster). As the warranty had expired, the cluster was shut down. Many of the above issues are either issues that are difficult to detect as they do not cause nodes or services to stop functioning, but rather affect experiments in subtle ways; or issues that include an amount of randomness. Very few of those kinds of issues were reported by users.

Two issues in particular are worth explaining in more details.

Boot failures due to a race condition in the kernel (bug 7347): Our work also uncovered bugs that affected more critical pieces of software. While analyzing test failures, we noticed that nodes were taking much longer to boot in about 5% of cases. The problem was tracked down to LVM2 initialization waiting for systemd-udev-settle execution, which is a command in charge of waiting for all physical devices to be initialized that is included as a dependency for LVM2 in the Debian 8 boot sequence. However, due to a race condition in the kernel, a CPU core initialization was hanging, causing systemd-udev-settle to also hang until it reached a timeout. This has been reported to Debian 4and will be fixed in a future update of the 3.16 branch of the kernel (it was already fixed in Linux 3.19, but Linux 3.16 is the version in Debian 8). This kind of issue shows that the devil is in the detail, and that no piece of software should be considered bug-free.

Heterogeneous disk performance on supposedly identical hardware (bug 7658): The Nantes Grid'5000 site hosts the econome cluster, composed of 22 Dell PowerEdge C6220 nodes (a single 2U chassis hosts four servers) with the exact same hardware configuration. On this cluster, the disk test showed lower performance on four nodes (from the same chassis): the test workload exhibited an average sequential read bandwidth of 79.3 MB/s on the slow nodes, vs 87.7 MB/s on the fast nodes (a 10% performance difference). Also, the SATA rate advertised by the disk was different (SATA 2.6 on the slow nodes, SATA 3.0 on the fast nodes). It turns out that the slow chassis was bought five months before the rest of the nodes (June 2012 vs November 2012), and, while it was indeed the exact same hardware configuration, it shipped with a different set of BIOS and firmware versions. Due to the lack of tests, this was not detected at the time of the cluster installation. Upgrading the BIOS version on the older nodes did not solve the problem, but upgrading the disk firmwares did.

Obviously, for all experiments performed on this cluster where storage performance had an impact, this puts into question the results that were obtained (as the heterogeneous performance might create results that depend on the placement of data on specific nodes), the repeatability of results (as different nodes from the same cluster would provide different results) and overall, the reproducibility of experiments.

VI. RELATED WORK

There has been very little work on testbed testing, verification and quality control.

In the context of the Fed4FIRE project, a monitoring system [START_REF]Fed4fire -monitoring[END_REF], [START_REF] Vermeulen | Fed4fire d2.8 -third integration and testing roadmap[END_REF] was designed and later extended [START_REF]Fed4fire federation monitor[END_REF], but it focuses on API-level compliance testing and authentication testing for testbeds members of the Fed4FIRE federation.

local apps="opensm osmtest ibbs ibns" for app in $apps do if ( ps -ef | grep $app | grep -v grep > /dev/null 2>&1 ); then echo "Please stop $app and all applications running over InfiniBand" echo "Then run \"$0 $ACTION\"" exit 1 fi done Figure 4. Excerpt of the openibd script (part of the OFED Infiniband stack, and responsible for starting it during boot). the use of grep $app caused random failures to start, as any unrelated process with e.g. libnss in this command line would cause the test to succeed, and the service to abort start up. The image was updated to a newer version of the OFED script, which switched to using pgrep for more reliable process matching.

Similarly, GENI developed a test suite to verify AM API compliance [START_REF]Geni am api acceptance tests[END_REF].

On Grid'5000 itself, it was already mentioned in Section II that each time a node boots, a tool called g5kchecks downloads the node's description from the Grid'5000 Reference API, and then verifies using various inventory tools that the visible hardware configuration on the node matches the description from the Reference API [START_REF] Margery | Resources Description, Selection, Reservation and Verification on a Large-scale Testbed[END_REF]. This is complementary to the work described in this paper, as g5kchecks is not in a position to verify properties at the cluster, site or testbed level (e.g. that clusters are homogeneous). Also, the fact that it runs when the node boots make it timecritical, and thus it cannot run longer performance measurements or tests requiring the collaboration of several nodes. The Emulab-based testbeds (e.g. CloudLab) use a tool that is similar in scope to g5k-checks called CheckNode [START_REF]Emulab -checknode[END_REF].

Also on Emulab, LinkTest [START_REF]Emulab -linktest[END_REF] can validate the network characteristics of an Emulab experiment (connectivity, latency, bandwidth, link loss, routing).

More generally, this work builds on the products of good practices in software engineering, like software testing [START_REF] Myers | The art of software testing[END_REF], continuous integration (CI), continuous delivery (CD) and automation in general. It is similar in some ways to performance regression testing, which is more and more advocated in various communities, e.g. in the Linux kernel development community [START_REF] Bueso | Performance monitoring in the linux kernel[END_REF].

VII. CONCLUSIONS AND FUTURE WORK

In this paper, we presented the automated testing framework 5 that was designed in the context of the Grid'5000 testbed. This framework is in production and helped to identify 118 issues so far, with more to be found. It will serve as a basis for future work: the 15 tests that have been implemented could be extended to cover more cases; and additional tests will be added to cover additional services.

One limit of the current architecture is the scheduler. It currently schedules jobs on a per-cluster basis, and thus requires all nodes to be available. While the Grid'5000 Usage Policy makes this an acceptable compromise, it is still a problem with the busiest clusters. It would be better if the scheduling could be done on a per-node basis, with nodes being re-tested on a regular basis, when they are available. Unfortunately this would mean tracking the status of nodes outside of Jenkins, as Jenkins would not scale to a one-jobper-node model (which would also not make sense for the nodes provisioning, which is more efficient when done using groups of nodes).

The number of detected problems might seem important. It should be put in perspective with the fact that Grid'5000 sees a lot of users, and that those users are generally satisfied about the testbed. Many of the problems are corner cases that only affected some experiments, some nodes, or could stay unnoticed for a long time. Also, until one does not actually start looking for problems in a systematic way, it is difficult to estimate the number of problems that will be detected on a given testbed.

Generally, this work raises the question of the respective roles of testbed operators and experimenters. Shouldn't experimenters assume that the testbed needs to be verified or qualified before their experiments? Based on the number of uncovered issues, not many of the Grid'5000 users have been doing so. on the other hand, doing some amount of verification at the testbed level makes sense, of course, but it will never be exhaustive and cover all users' needs. Also, designing these kinds of solutions as part of a given infrastructure makes them testbed-specific, and makes them more difficult to port an experiment to another testbed, where guarantees will not be identical.

Figure 1 .

 1 Figure 1. Grid'5000 sites and interconnection network

Figure 2 .Figure 3 .

 23 Figure 2. Status page for all tests and sites

  Check that the properties of nodes in the OAR resource manager match what would be generated based on the information in the Reference API.

	• oarstate: Check the current state of nodes in the OAR
	resource manager (in particular, check that disabled
	nodes -due to hardware failure -are correctly doc-
	umented).
	• cmdline: Perform basic operations using command-line
	tools (reservation, deployment). All other tests rely on
	the Grid'5000 REST API.
	• sidapi : Perform basic operations using the development
	branch of the Grid'5000 REST API. All other tests use
	the stable branch.

• oarproperties: • environments: Check that each environment maintained by the Grid'5000 team can be provisioned on each cluster, and further check functionality of various features after provisioning (e.g., Internet access from the node).

The corresponding bugs are available in the Grid'5000 bug tracker (https://intranet.grid5000.fr/bugzilla/). A Grid'5000 account is required, but could be obtained through the Open Access program.

https://bugs.debian.org/841171

Due to the large amount of hardcoded Grid'5000-specific things, the framework code itself is of little value for other testbeds, and thus we did not make the effort of making it publicly available. However, we are totally open to sharing it (or parts of it) if this is considered useful.

ACKNOWLEDGEMENTS

We would like to warmly thank the Grid'5000 technical team for fixing many of the issues that were discovered during the course of this work, thus providing an extremely valuable feedback loop.

The work presented in this paper were carried out using the Grid'5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (see https://www.grid5000.fr).


Keywords:

L'hypothèse d'une demande de soins induite par l'offre repose sur le constat de l'existence d'une asymétrie d'information entre le médecin et son patient. Cette asymétrie confère au médecin un pouvoir discrétionnaire qu'il utilise dans son propre intérêt. Cet effet d'induction est identifié et distingué des autres effets pervers -risque moral et sélection adverse-qui sont également conséquences de l'existence d'asymétries d'information dans le système de santé. L'hypothèse d'induction est à l'origine d'un débat très controversé en raison de la remise en cause de l'hypothèse, chère aux néoclassiques, d'indépendance entre l'offre et la demande. Les enjeux des études empiriques sont donc, dans ce contexte, très importants. Un test empirique de la théorie de la demande induite a été réalisé d'après des données françaises de la médecine générale. Les résultats de cette étude sont statistiquement robustes et ils corroborent l'hypothèse d'induction. MOTS-CLES Induction de la demande par l'offre -Sélection adverse -Risque moral -Marché d'assurance maladie. Marché des services médicaux -Test économétrique.

The recent conflicts between the French government, health insurers and medical trade unions are due to the government choices concerning the health policy : medical staff and health care expenditure increases are forcing the French government to adopt "supply" regulations for those expenditures.

On the one hand, the number of surgery is restricted in cities where medical density is already high (Besson's law, July 1989).

On the other hand, new practitioners can no more choose the second medical convention which implies that fees are freely fixed by the physician (December 1989J1.

Those choices concerning the health care policy may be legitimated if the supplier induced demand hypothesis is corroborated by empirical findings. The informational asymmetry which exists between physicians and their patients conf ers a discretionary power on practitioners. Through price increases or quantity inducement, they can avoid the expected decline in workload and income brought about by increasing competition2.

If the French government restricts competition in big cities in order to keep an average workload, it will not provide incentives to quantity inducement. In the same way, if the number of free pricing practitioners is restricted, inducement by price hikes is limited.

Supplier induced demand is relative to one kind of informational 1Since 1980, there are two kinds o f professional agreements in France between "social security" and private physicians : in both cases, practitioners are paid on a fee-for-service basis. In "sector 1", fees are fixed on the agreement basis and are paid by the patient. In "sector 2", physicians can choose free pricing, in counterpart, they pay a higher social insurance contribution, but the patient is refunded on the basis o f "sector 1" fixed fees. Consequently, he has to pay the co-insurance part himself (as a patient o f a "sector 1" physician) and the difference between free and fixed prices, i.e. overpricing. Since December 1989, the second agreement has been forbidden to be chosen by the new practitioners, 2 It should be noticed that supplier-induced demand is different from revealed demand which exists whenever there is excess demand on the market. In this case, increasing competition implies a rise in consumed quantities and this is identified as revealed demand. Whenever there is no excess demand, an increase in consumed quantities is identified as supplier induced demand.

asymmetry : the physician has medical knowledge as opposed to the patient who is ignorant, not only of the health care market characteristics but also of his own needs.

In the relationship between three protagonists -patient, physician and insurance-other types of information asymmetries can be distinguished : the patient's health state cannot be observed by insurance ; adverse selection is a consequence of this asymmetry between insurance and the insured patient. Another kind of asymmetry between those same actors comes from the insured patient's health care use that cannot be observed by insurance. This asymmetry implies a moral hazard effect.

In the first section, this paper offers an analysis of these information asymmetry effects and an identification of the supply inducement among those effects.

In the second section, a test of induced demand on the French market is set out. A controversy is generated by the induced demand hypothesis, first developed by R.G. Evans (1974), which contradicts standard neoclassical predictions and the assumption of the independence of supply and demand. Empirical studies play a prominent part : if a lot of these studies are published in the Anglo-Saxon literature, only a few are relative to the French health care system.

INFORM ATION ASYMMETRIES AND HEALTH CARE SYSTEM

Different kinds of information asymmetries can be distinguished within the health care system. These asymmetries have to be differentiated by actors (patient/physician as well as insured/insurance) but, also by the nature of information.

When information is relative to the characteristics of goods, services or health state, the consequence of asymmetry and of liberal market mechanism is adverse selection. When the actors' behaviour cannot be observed, moral hazard effect is the consequence of asymmetry.

When specific knowledge brings about an asymmetry between the consumer and the provider of services, a principal-agent relationship can be defined. Between the patient and the physician, information asymmetry may cause an induced demand effect.

* The adverse selection concept, mainly applied to the health insurance market was first analysed for the secondhand car market. This well-known example, developed by G.A. [START_REF] Akerlof | The Market for "Lemons" : Quality Uncertainty and the Market Mechanism[END_REF], shows that the competitive market mechanism is not efficient when the goods characteristics, especially quality, cannot be observed by consumers. In this case, good cars and bad cars (which are known as "lemons" in the United States) must still be sold at the same price. This price is lower than the true value of a good car which may not be traded at all. The owner of a good automobile knows but cannot prove its relative quality advantage. "The good cars may be driven out of the market by the lemons" (G.A. Akerlof, 1971, p. 492). As a result, there is a reduction in the average quality of traded cars in spite of the welfare of both parties.

* Analysing the market for physicians services (not yet the market for health care insurance) shows that the existence of doctors licensing counteracts the effect of quality uncertainty. It ensures the patient of some normal expected quality and adverse selection may not be observed in this market.

* The adverse selection principle fits especially well the market for medical insurance. The insured medical condition is the hidden information. The insurer cannot observe the probability of the event of illness.

Whenever insurance policies may be f reely chosen by the individual, the insurer applies an average price level because of the informational asymmetry between himself and the insured, so that people who insure themselves will be those who are certain that they will need the insurance. The result is a reduction in the average medical condition of insured people. In this case, insurance companies cannot balance their budget and the liberal market mechanism is inefficient.

Adverse selection is counteracted by

The principle of social insurance

The existence of doctors* licensing

Moral hazard

In the hospital sector, managers and practitioners behaviour cannot be observed by Public Authorities. This brings the former to behave strategically : this strategical behaviour can be analysed with the concept of moral hazard as well as the insured patients' behaviour in the medical insurance market.

Moral hazard and medical insurance market

On the medical insurance market, implications of the adverse selection principle become complicated when one takes into account that the insured cam behave strategically about the information he knows to be asymmetric.

The insured can either modify his preventive behaviour, or consume more health care with insurance than without. R.J. [START_REF] Arrow | The Economics of Moral Hazard : Further Comments[END_REF] point of view is that moral hazard is a result of information asymmetry and of individuals' "moral perfidy".

According to M. V. [START_REF] Pauly | The Economics of Moral Hazard : Comment[END_REF], moral hazard is only a result of rational economic behaviour : demanding more health care at a zero price (with insurance) rather than at expenses (without insurance) is not a moral or ethical problem whenever it is assumed that the price elasticity of demand for health care is (in absolute value) above zero.

Potential moral hazard, in opposition to adverse selection, arises when contracting an insurance policy becomes obligatory.

Moral hazard and hospital management

The economic theory of bureaucracy applied to the hospital * Public Authorities represent the holders of property rights (politicians exert those rights for public goods) but their targets differ from the ones of an individual firm manager : for instance, profit search 3See X. [START_REF] Greffe | Analyse économique de la bureaucratie[END_REF], W.A. [START_REF] Niskanen | Bureaucracy and Representative Government[END_REF], R.J. [START_REF] Launois | La théorie de la bureaucratie à l'hôpital[END_REF].

is excluded because "it is inevitably grievous to think that one might 4 speculate on human suffering" .

Profit search is turned into balance budget search and potential profits are turned into new expenditures. The amount defined by these expenditures, which are not absolutely necessary, constitutes the discretionary budget in the hospital.

All actors in the hospital sector will seek to take over a part of this budget : the inf ormation about the assessment of hospital activities is held by practitioners and managers. Their behaviour cannot be observed by Public Authorities.

Analysing inf ormation asymmetries and using the moral hazard concept shows that the major part of discretionary budget will be taken over by the information holders. Managers get more important allocations from Public Authorities whenever they manipulate the information ;

practitioners modif y the inf ormation about technical equipment needs ; they also induce quantities of medical services and of days spent in the hospital by patients5 in order to increase budget allocations.

The analysis of moral hazard shows that inf ormation holders behave strategically according to the information they hold ; their behaviour cannot be observed by Public Authorities and this entails an increase in expenditure.

. 1.3. Supplier-induced demand Within the context of the neoclassical theory, analysing relationships between patient and physician brings one to consider the patient as a consumer, the physician as an individual manager and the medical operation as a service.

In all specialized operations, an information asymmetry exists between the consumer and the provider of services. However, the patient's

4

"Il y a fatalement malaise à l'idée que l'on puisse spéculer sur la souffrance humaine", R.J. Launois (1981, p. 7).

SThe ''per diem price" system was criticized because it brought practitioners to increase the length of stay, as hospitals were financed according to the number o f days spent in the hospital by patients. Not-for-profit hospitals are now (since 1984) financed by the "global budget" and such quantity inducement is no more expected in public hospitals.

ignorance is greater than that of a simple consumer of services : it is relative to the characteristics of medical goods and services and, just as well, to the patient's needs.

It has been shown by S. [START_REF] Darbon | La micro-économie des soins médicaux doit-elle nécessairement être d'inspiration néoclassique[END_REF] that the patient's ignorance is also greater than the ignorance of a principal facing his agent (or of a layman facing an expert) : a specialized operation is usually constituted by an evaluation of the initial state (diagnosis in case of health care services), some technical acts and, as a result, a change in the initial state.

The patient, as any consumer of specialized services, does not know anything about the two first components. On the contrary, the result of most specialized services can be objectively appreciated by a layman.

It is not the case for a medical operation : the improvement of health condition expected as a result might not be objectively appreciated by a layman because of inherent difficulties in health measurement. When psychical and social dimensions are taken into account, health measurement becomes not only complex but also subjective : the individuals' behaviour related to unhealthy symptoms constitutes the psychical dimension of the health state. The individual's feelings about it change according to his place on the social scale and this implies a social dimension within the health state6.

The improvement of health condition is a subjective issue and it implies difficulties in consensus between patient and physician about the result of the medical operation.

In the medical sector, the costs of information research become prohibitive especially in emergency cases. On the contrary, in case of chronic diseases, the information asymmetry between patient and physician disappears : a chronically ill person, a diabetic for instance, learns to recognize the symptoms of his disease and to use the appropriate treatment.

*

As we have seen previously, this information asymmetry confers a discretionary power on practitioners. The physicians' target is assumed to be utility maximisation, the arguments of their utility function being income, leisure, power and prestige... This discretionary power would let them create demand either to adjust their real income to their desired one or to cancel the effects of the expected decline of both their workload and their income in the event of increasing competition.

* In practice, they modify the perception that patients have of their own needs in order to induce quantities or to increase fees (when fees are freely fixed).

* This last possibility presupposes that price elasticity of demand is less than one in absolute value : without this assumption, a rise in fees would be replaced by a decline in consumed quantities and it would not allow physicians to increase their income. The more price elasticity is close to zero, the more physicians would be able to adjust their real income to their desired one.

1.4. Compatibility, cumulation and interaction of moral hazard and inducement eff ects

On ambulatory care

The assumption about price elasticity makes one wonder about compatibility of moral hazard and inducement effects : the moral hazard concept assumes that price elasticity of demand for health care is above zero in absolute value. On the contrary, inducement assumes that price elasticity is closer to zero.

The problem of compatibility has to be discussed according to the procedure of supplier inducement. On the one hand, the physician using his discretionary power modifies the perception that the patient has of his own health care needs in terms of quantity, therefore the patient considers that the induced acts are necessary for the improvement of his health condition whatever his price sensitivity.

In that case the assumption of a low price elasticity of demand is not necessary as a preliminary to quantities inducement. On the other hand, inducement can be expressed by a rise in fees. The problem of compatibility exists only in this last case of inducement by fee rising.

When fees are administratively fixed, as for "sector 1" in France, practitioners can only induce quantities. Thence, inducement and moral hazard can be observed simultaneously.

When fees are freely fixed, as in the U.S.A. or in France for "sector 2", the compatibility of moral hazard and inducement is at issue.

In the hospital sector

It has been shown (see section 1.2.2) that the hospital actors' behaviour can be analysed through the moral hazard concept. However moral hazard and inducement have to be distinguished because they can be observed simultaneously and because they interact. The moral hazard effect is characterized by strategical behaviour adopted by physicians and managers which cannot be controlled by Public Authorities for lack of information. One among those behaviours is a quantity inducement which is a result of incentives : * In the private hospital sector, the "per day price" and fee-for-service system provide incentives to induce the length of stay and the services quantities. This is only possible if practitioners use their discretionary power in order to induce demand . * In the public hospital sector, the "global budget" replaces the "per diem price" system and it allows Public Authorities to control better the practitioners' behaviour, as there are no more incentives to induce quantities8.

7 This presupposes that there is no excess-demand for services provided by the hospital.

TESTING SUPPLY INDUCEMENT ON THE FRENCH MARKET FOR MEDICAL SERVICES

Even if there is a consensus about the existence of discretionary power, there is a controversy about its use and limits. The positive correlation between the increase of medical staff and the fee rise is identified here by an inducement effect and differently interpreted by authors.

Some of them, J.P. [START_REF] Newhouse | A Model of Physician Pricing[END_REF][START_REF] Kessel R | Price Discrimination in Medecine[END_REF], interpret the market f or medical services as a market based on monopolistic competition, explaining the fee rise as being a consequence of new physicians coming into the market.

The increasing monopoly theory developed by M.V. [START_REF]The Pricing of Primary Care Physician Services[END_REF], constitutes another explanation of this correlation (the increasing search costs, which are a consequence of rising medical staff, would confer a monopoly power to physicians).

Comparing those different theories , empirical studies of the correlation between the physician population ratio and the per capita utilization of medical services are relevant to choose between the theory of supplier induced demand and the other ones.

Numerous empirical studies are published in the Anglo-Saxon literature10 but only a few are relative to the French market for medical services. This second part sets out an empirical test of inducement on the French market for general practitioners services. First of all, it would be proper to consider the implications of empirical studies.

Stakes in empirical studies

The implications of empirical studies on the physicians induced demand theory have important stakes (U.E. [START_REF] Reinhardt | The Theory of Physician Induced Demand : Reflexion After a Decade[END_REF] which explain vigor in debate.

From a theoretical point of view, challenging the assumption of the independence of supply and demand is assaulting "one of the crucial 9 See S. Be jean (1989) and L. Rochaix (1986 a).

10For a synthesis o f the results and the methodological problems o f these empirical studies, see S. Be jean ( 1989), E. Levy (1989) and L. [START_REF] Rochaix | Testing Supply Inducement : A Guided Tour Through the Jungle[END_REF]. pillars of the neoclassical framework" (U.E. Reinhardt, 1985, p. 188).

With no surprise, the guardians of that framework are reacting with vigor.

The choices concerning the health policy rely on the previous issue : the state control over the medical staff and more generally government imposed limtations on the supply of medical manpower may be legitimated whenever the induced demand hypothesis is corroborated by empirical findings.

As to the political ideology, the individual economists' point of view about the state intervention conditions "their more or less important reluctance towards econometric studies"11.

The debate among these different theories reflects their philosophical underpinning : the increasing monopoly theory emphasizes the responsability of the patient-consumer while the induced demand hypothesis sets out the responsability of physicians f or the increasing medical expenditures.

Test

Agregate data, the choice o f a geographical area and the choice o f a medical sector

Choosing the sector of General Practitioners (GPs) to test the induced demand hypothesis is justified by the fact that services provided are more homogeneous for GPs than for specialists. In the same search for homogeneity, the medical population is constituted only by active liberal 12 GPs excluding GPs following a specific type of practice .

In the health care sector one cannot work with individual data :

the medical secret prevents the connection between data concerning the physician and data concerning his patients. Therefore empirical studies are set out according to data aggregated by geographical areas. The choice of departments (main administrative divisions in France) as geographical areas is justified in the case of GPs : it allows to eliminate bordercrossing linked with the physicians reputation.

11"Leur plus ou moins grande sévérité à l'égard des travaux économétriques"; E. Lévy, 1989, p. 472. 12 It means GPs who are practicing in an alternative way such as acupuncturists, homeopaths...

It is assumed that the average quality per department of GPs'

services is constant : a study developed by F.A. Sloan and F.H. Lorant (1977) shows that the quality elasticity of demand for medical services is very low (quality is assessed by the patient's waiting time and the physician's visit duration).

The Anglo-Saxon empirical studies are usually specified on a demand-supply model. In our study, only the demand function is tested.

Demand is a function of health care use variables and of variables which are revealing supply levels. The influence of the latter on utilization rates is tested. * Fees, assessing the price of medical services are divided into the average overpricing per act (OP) and the average fee without overpricing per act (P). The distinction is made according to the assumption that patient sensitivity to overpricing may be the greatest as overpricing is not reimbursed.

The choice o f variables

* In order to take into account travelling costs, the average distance (DIS) to reach the physician's surgery is introduced as an explanatory variable14.

* The explanatory variables which are revealing supply levels 13 It means that it is assumed that demand is equal to consumption. W e 'll come back to this assumption later.

14 Those distances were assessed by F. Faure, C. Le grain and F. Tonnelier (1987).

are :

DENSG : GPs' density DENS : Density of alternative practitioners and specialists.

Estimation and results

The empirical relationships to be estimated and tested is a linear function which explains per capita utilization of health care in terms of the explanatory variables and an error term e (C is a constant).

[ has been estimated by OLS, on a linear form and on a log linear form basis. Table 3 gives the results of both regressions. The variables SSB and P are eliminated because their parameters are not significant (individual tests and one simultaneous test).

The test of parameters stability and the test of global linearity give positive results.

Finally, the simultaneous test of the parameters of DENSG and DENS allows us to reject the assumption of independence between supply and demand.

The sample of ninety-five cross-section data points has been divided into two samples. In sample one, the level of physicians workload (i.e. the number of acts per GP) is less than the average workload. In sample two, the level of physicians workload is above the average. The division into both samples would allow us to distinguish revealed demand from induced demand15 ;

-whenever there is excess-demand on the market, physicians workload is expected to be high. Then, a positive correlation between health care utilization and GPs density can be defined by revealed demand ;

-whenever there is excess supply on the market, physicians workload is expected to be low. Then ,the same positive correlation between health lsThis distinction has been made thanks to relevant discussions with M.O. Carrere.

care utilization and GPs density can be defined by induced demand (and not revealed demand).

The results of the regressions on sample one are given in table 4 (only the results on sample one are interesting in this respect).

Analysis o f empirical results

The expected influence of the demographic factors (age, sex) is confirmed.

The income elasticity of acts consumption is low (0,296) :

primary care supplied by GPs is that for which demand changes least according to the income level. This low income elasticity might also reflect the social legislation which helps successfully the most disadvantaged sections of the population reach health care.

The distance to the GPs' surgery does not influence so much the health care consumption and his parameter sign is positive : it is disturbing but it could be explained by a substitution of consultations (at the GPs' surgery) to home visits . It cancels the influence of the distance which dissuades from consuming health care at the GPs' office (see A. [START_REF] Mizrahi | Offre de soins et consommations médicales[END_REF].

The non significance of the SSB shows a misassessment of the patient's social insurance level.

The variable P does not influence health care utilization either. Fees without overpricing do not represent real costs to the patient as this amount is completely or partly reimbursed. The non significance of variable P may reflect the absence of patient's sensitivity to reimbursed fees.

The overpricing elasticity of demand is very low (-0,092). This result confirms a low patient sensitivity to health care prices, according to the assumption that the discretionary power is all the more used by physicians since price elasticity of demand is close to zero.

The estimated parameter of GPs' density is positive and it corroborates the supplier induced demand hypothesis. An increasing competition brings practitioners to induce quantities : whenever GPs density rises by 10 per cent, the consumption of GPs services rises by 8,73 per cent.

The results of the regressions on sample one (where physicians workload is low so that it can be assumed that there is no excess demand on the market) also corroborate the induced demand hypothesis as they allow to distinguish induced demand from revealed demand : in sample one, whenever GPs density rises by 10 per cent, the consumption of GPs services rises by 9,3 per cent and it is defined by induced demand. As a conclusion, the results of this study bring up a choice for a "supply" regulation of the health care expenditures, all the more because the costs of inducement are not only measured by the number of induced acts but also in terms of medecines and technical tests prescribed during these induced visits.

Furthermore, this econometric study does not take into account the potential inducement by fee rising in "sector 2" where fees are freely fixed.

However, the theoretical impact of this study is limited because of different causes :

-first of all, additional research on data construction has to be made, especially in order to elaborate on a satisfactory index of the social insurance level ;

-the framework assumptions about the quality of medical services are at issue because the corroboration of the induced demand hypothesis is dependent on those assumptions ;

-finally, it should be mentioned that hypotheses about the individual behaviour of the patient, or the physician, cam be firmly corroborated only when empirical studies are completed on individual data basis.

3

  sector shows the existence of a discretionary budget. Each actor -Public Authorities, managers and practitioners-will seek to take over a part of it.Goods under State supervision, such as hospitals, do not have any properties -transferability and exclusivity of property rights-which can be observed for an individual firm. This implies an opposition between the interests of each actors group. * Hospital managers' utility depends on income but also on other arguments such as power and prestige, linked to the importance of the budget they bear. * The arguments for practitioners utility are similar. Their prestige is especially linked to the range of medical services supplied by the hospital and to the technical equipment they use.

13*

  Demand is assessed by per capita utilization of health care , i.e. the average number of per capita GPs' acts (D). * The explanatory variables are constituted by demographic components such as age and sex : because of their biological nature, they influence health care use. P15 : ratio of under fifteen year old population, P65 : ratio of over sixty-five year old population, PW : ratio of over fifteen and under sixty-five year old women. * Socio-economic components are the average income (Y) and the average amount of social security benefits paid to health care (SSB).