Mike Benchimol
email: mike.benchimol@eleves.enpc.fr

Pascal Benchimol
email: pascal.benchimol@polytechnique.edu

Benoît Chappert
email: benoit.chappert@eleves.enpc.fr

Arnaud De

La Taille

Fabien Laroche
email: fabien.laroche@polytechnique.edu

Frédéric Meunier
email: frederic.meunier@enpc.fr

Ludovic Robinet
email: ludovic.robinet@eleves.enpc.fr

Arnaud De La Taille

Balancing the stations of a self-service bike hire system

Keywords:

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

foisonnement", which could be translated by "profusion rate"). Indeed, as it has already been pointed out, if a station becomes empty, potential users won't find bikes; if a station becomes full, a user may to make additional travels in order to find eventually a place to leave the bike. Highly unbalanced situations arise for instance in the morning, when peripherical stations become very quickly empty, and central ones completely saturated.

In the case of Paris, 20 trucks are traveling the city 24 hours a day (except a few hours in the end of the week) in order to maintain the ratio between the total number of places and the number of bikes in each station close to the profusion rate. We call this task, the balancing of the stations.

To our knowledge, such systems have not attracted the attention of the researchers yet. However, more and more cities propose such services; other modes, like cars or vans, or other functions, like freight, are envisaged. All these things makes patently obvious that rules or heuristics (at least elementary) for operating such systems should be designed. In this paper, we will deal with the case when no bike are moving. This situation is not completely a simplification. Indeed, every day, at the end of the night, very few bikes are moving. On the other side, it is precisely in the mornings that there are the most intensive use of the system and that the quality of the balancing is important. To start this study, we assume moreover that there is a unique truck.

Finally, note that problems of similar natures can be encountered in other situations. For instance, the caddies of a supermarket must be moved between different points, at the end of the day, in order to get the right number of caddies at each place the customers can take some.

Results, notations and plan

Previous works and results

The problem encountered is a kind of one-commodity pickup-and-delivery problem with one vehicle. A similar problem has been introduced in [START_REF] Hernández-Pérz | The one-commodity pickup-and-delivery travelling salesman problem[END_REF][START_REF]A branch-and-cut algorithm for a traveling salesman problem with pickup and delivery[END_REF] where there are two kinds of customers: delivery customer, who requires a non-zero amount of the product, and pickup customers, who provides a non-zero amount of the product. Nevertheless, the problem in these papers calls for a minimum distance tour visiting each customer only once. In some case, there is no feasible solution. Hence, it does not suit exactly to the situation described in Section 1.

The swapping problem studied in [START_REF] Anily | The swapping problem[END_REF] has not this drawback: a customer can be visited more than once. But in this case, a single vehicle of unit capacity is available for shipping items among the vertices. The swapping problem is to compute a shortest route such that a vehicle can accomplish the rearrangement of the items while following this route. It solves our problem only in a particular case since here the vehicle has unit capacity. It should be emphasized that the swapping problem deals with items of different types, hence it is not a particular version of ours.

Finally, Chalasani and Motwani consider in [START_REF] Chalasani | Approximating capacited routing and delivery problem[END_REF], among other things, the swapping problem for any capacity and only one type of items. They call this problem "the C-delivery TSP". They give an 9.5-approximation algorithm, which we adapt in Section 5 (this ratio has been improved in [START_REF] Anily | Approximation algorithms for the capacitated traveling salesman problem with pickups and deliveries[END_REF][START_REF] Charikar | Algorithms for capacitated vehicle routing[END_REF]). Nevertheless, their algorithm is polynomial in the capacity C of the truck and in the total number N of items. In our model (Section 3), in our quest of efficiency, we look for a polynomial algorithm in the size of the problem description which is something in O(log C + n log N ) where n is the number of stations.

The objective of the present paper is to adress the problem described in Section 1, and, as a first approach, to adress it from a theoretical point of view. Among other things, we prove complexity results, describe a 9.5approximation algorithm working when the truck must come back at its starting point, by an adaptation of the Chalasani-Motwani algorithm (the adaptation consists in replacing a bipartite matching with a bipartite b-matching somewhere in the algorithm and in checking that everything remains polynomial), and a 2approximation algorithm when the network is a complete graph with unit costs and prove that the problem is polynomial when the graph is a tree. We call our problem STATIC STATIONS BALANCING, because of the motivations, which is interesting for its own sake, but it could have been called "1-commodity swapping problem with capacity".

There are two versions of the swapping problem: the preemptive one and the non-preemptive one. In the preemptive version, the items are droppable, i.e. they can be dropped at temporary locations along the route before being moved to their final destination. In the present paper, we deal with a preemptive version of our problem. Some remarks will be made about the non-preemptive one, mainly in Subsection 8.2, where we prove that the two versions are actually identical in the case of a line.

Notations and tools

Let F be a finite set and H be a additive semi-group. Let w ∈ H F . Then for any subset F of F we denote

w(F ) = f ∈F w(f ).
Let G = (V, E) be a graph. For any subset of vertices U , we denote by δ(U ) the set of edges having exactly one endpoint in U . If v is a vertex, we denote δ(v) instead of δ({v}).

For b ∈ Z V + , a perfect b-matching is a vector m ∈ Z E + such that for each vertex v of G m(δ(v)) = b v . ( 1
)
If there is a capacity u ∈ Z E + on the edges, we can speak of a capacited perfect b-matching m, which requires in addition to Equation (1) that m e ≤ u e for each edge e.

A necessary condition for the existence of a perfect b-matching in a bipartite graph with color classes U and U is of course that b(U ) = b(U ).

Optimization problems on b-matching in bipartite graphs can be reduced to min-cost flow problems, and hence can be solved in strongly polynomial time.

Let D = (V, A) be a directed graph. For any subset of vertices U , we denote by δ + (U ) (resp. δ -(U )) the set of edges leaving (resp. entering) U .

For

b ∈ Z V + , a b-flow is a vector f ∈ R A + such that for each vertex v of D f (δ + (v)) -f (δ -(v)) = b v .

Plan

In Section 3 we present a model of our problem. Its function is mainly to have a clear definition of our problem. This section is followed by the discussion about the complexity of the problem, which is NP-hard in the general case. The following section (Section 5) explains how to adapt the algorithm by Chalasani and Motwani to keep a polynomial time algorithm when the input is not the whole list of bikes and the capacity is not counted in unary basis, but instead when the input is a list of numbers. Section 6 provides an integer linear programming approach, which gives useful lower bounds for our problem. Section 7 deals with the particular case when the graph is a complete graph with unit costs (it can model the case when we only count the loadings and the unloadings of the bikes). In this case, we can solve the problem in polynomial time for fixed capacity C = 1 or C = 2 of the vehicle. There is also an easy (greedy) 2-approximation algorithm in this case. Finally, we describe a polynomial time algorithm solving the problem exactly when the graph is a tree (Section 8). The last section (Section 9) is devoted to several open questions.

The model

We are given a graph G = (V, E) and a capacity C ≥ 0. A state s is a couple (x, p) where x ∈ R V + and p a vertex in V . Two states s = (x, p) and s = (y, q) are said to be adjacent if we have simultaneously

• x v = y v for all v / ∈ {p, q}, • pq ∈ E, • x p -y p = y q -x q and • |x p -y p | ≤ C.
A move consists in going from a state s to an adjacent state s . If the graph is endowed with a cost c ∈ R E + , the cost of a move between two adjacent states s = (x, p) and s = (y, q) is simply c(pq). The cost of a sequence of moves is the sum of the cost of the moves of the sequence.

The interpretation of these definitions is obvious. A state s = (x, p) encodes the position p of the truck and the number of bikes x v on each station v. The number x p can be alternatively seen as the number of bikes on p plus the number of bikes in the truck or as the total number of bikes on p with the additional rule that when the truck arrives on a station, it unloads all its bikes. We are in the preemptive version, whence it doesn't matter.

A move corresponds to a real move of the truck. If the two adjacent states are s = (x, p) and s = (y, q), the number of bikes in the truck during the move is x py p .

The problem we are interested in consists in going from an initial state i = (x, p) to a terminal state t = (y, q), using only moves between adjacent states, with a sequence of moves of minimal cost. A vertex (or a station) is said to be in excess (resp. in default) if x v > y v (resp. x v < y v ). A vertex or a station such that x v = y v is balanced. The set of balanced stations is denoted by B(x, y).

The same notions hold for a subset of vertices: a subset U ⊆ V is said to be in excess, or in default, or balanced, depending on whether x(U )y(U ) is > 0, < 0 or = 0.

We define U ex to be the set of vertices such that x v > y v and U def to be the set of vertices such that x v < y v .

Assumption.

We assume in the sequel that x(V ) = y(V ), otherwise there is no solution.

STATIC STATIONS BALANCING PROBLEM

Instance : A graph G = (V, E), a cost function c ∈ R E
+ , a capacity C and two states i = (x, p) and t = (y, q). Task : Find the minimal cost of a sequence of moves that allows to go from the state i to the state t.

This formulation is apparently innocent, but even before discussing whether it is possible to solve it in polynomial time or not, a remark must be done.

The minimum cost l, solution of the above problem, has necessarily an encoding that is polynomial in the size of the input: indeed, for obvious reasons, we have l ≤ nx(V )c(E). But it is easy to find instances for which the encoding of the sequence realizing the optimum is not polynomial in the size of the input: take the graph G with two vertices u, v and a unique edge connecting these two vertices and define C = 1. Consider the initial state i = (x, p) and the terminal state t = (y, q) with x u = 2α, x v = 0, y u = α and y v = α, for some positive real number α. The minimum number of moves is 2α -1. The size of the input is O(log α) and the size of the sequence of moves realizing the optimum is in O(α), which is exponential in the size of the input. Whether there is always a way to have an encoding of an optimal sequence whose size is polynomial in the size of the input is an open question. See the discussion of Section 9.

If we want to have an explicit solution, a way to circumvent these kinds of problem is simply to ask for an output that, in addition to the length of the optimal sequence, gives its first move. Indeed, the STATIC STATIONS BALANCING PROBLEM (SSBP) has this nice property to remain a STATIC STATIONS BALANCING PROBLEM after a move. Hence, we can restate it under the following form.

STATIC STATIONS BALANCING PROBLEM -research version

Instance : A graph G = (V, E), a cost function c ∈ R E
+ , a capacity C and two states i = (x, p) and t = (y, q). Task : Find the minimal cost of a sequence of moves that allows to go from the state i to the state t and the first move of such an optimal sequence.

Complexity results

The main message of this section is that the SSBP is NP-hard, even in restricted cases. Indeed, the PARTITION PROBLEM and the HAMILTONIAN CYCLE IN BIPARTITE GRAPH PROBLEM can be straightforwardly reduced to it. We give the full details for sake of completness.

Theorem 1. The SSBP is NP-hard even for a complete graph with unit costs and a y constant on V .

Proof. Indeed, the PARTITION PROBLEM can be reduced in polynomial time to the SSBP for a complete graph with unit costs and a y constant on V . Let a 1 , . . . , a n be an instance of the PARTITION PROBLEM. This latter problem is an NP-complete decision problem which asks whether it is possible to find A ⊆ {1, . . . , n} such that j∈A a j = j / ∈A a j ( [START_REF] Garey | Computers and intractability: a guide to the theory of NP-completness[END_REF] for further comments). We describe now the reduction. Take the complete graph K n+1 = (V, E) with n + 1 vertices. The vertices are identified with the integers 1, 2, . . . , n + 1. Define r := 1 + max j∈{1,...,n} a j . Consider the SSBP for the complete graph with unit costs, a capacity C = 1 2 n j=1 a j (w.l.o.g. we can assume that n j=1 a j is even), and an initial and a terminal states such that x j = ra j for j ∈ {1, . . . , n}, x n+1 = r + n j=1 a j , p = q = n + 1, and y j = r for all j ∈ {1, . . . , n + 1}.

If the answer to the PARTITION PROBLEM is yes, the optimal solution to the SSBP requires exactly n + 2 moves. Indeed, in this case, there is a subset A such that j∈A a j = C; the truck starts from vertex n + 1, visits first the vertices j ∈ A, comes back to the vertex n + 1, finishes its tour by visiting the vertices / ∈ A and then goes back to vertex n + 1.

If the optimal solution to the SSBP requires exactly n + 2 moves, the answer to the PARTITION PROB-LEM is yes. Indeed, each vertex ∈ {1, . . . , n} must be visited at least once, and the truck must leave the vertex at least twice (since there are 2C bikes in excess). If it requires exactly n + 2 moves, then each vertex ∈ {1, . . . , n} is visited exactly once, and the vertex n + 1 is left exactly twice, whence inducing a partition of the vertices in {1, . . . , n} in two parts A and B (the vertices visited before the second leaving of vertex n + 1 and the vertices visted after the second leaving of vertex n + 1). We have then necessarily j∈A a j ≤ C and j∈B a j ≤ C since the vertices are balanced with only one visit of the truck. Since j∈A∪B a j = 2C, we have j∈A a j = j∈B a j with A and B providing a partition of {1, . . . , n}.

Theorem 2. The SSBP is NP-hard even for a bipartite graph with unit costs, fixed C (even C = 1) and

y v = 1 for all v ∈ V .
Proof. Indeed, the HAMILTONIAN CYCLE IN BIPARTITE GRAPH PROBLEM can be reduced in polynomial time to the SSBP in a bipartite graph, with unit costs, C fixed and y(v) = 1 for all v ∈ V . Let G = (V, E) be a bipartite graph. The HAMILTONIAN CYCLE IN BIPARTITE GRAPH PROBLEM is an NP-complete decision problem asking whether there is an hamiltonian cycle in a bipartite graph ( [START_REF] Garey | Computers and intractability: a guide to the theory of NP-completness[END_REF] for further comments).

We describe now the reduction. We suppose C ≥ 1 fixed. Set y v = 1 for all v ∈ V . Let A, B be the two color classes of G. Define x v = 2 for all v ∈ A and x v = 0 for all v ∈ B. Define moreover p = q to be any vertex of A. Now if there is an hamiltonian path in G, then the optimal solution to the SSBP is n moves, where n is the number of vertices (each move from A to B consists in removing a bike in excess in a station of A and in putting it on a station of B). Otherwise, the optimal solution needs at least n + 1 moves since each station must be visited at least once (no station is balanced in the initial state) and there is no hamiltonian cycle.

A 9.5-approximation algorithm

In this section, we prove that it is possible to adapt the algorithm by Chalasani and Motwani [START_REF] Chalasani | Approximating capacited routing and delivery problem[END_REF] in order to get a 9.5-approximation algorithm that works in polynomial time for the SSBP when p = q (that is when the truck starts and finishes at the same vertex). Recall that their algorithm was designed for the C-DELIVERY TRAVELING SALESPERSON PROBLEM. The SSBP is the C-DELIVERY TRAVELING SALESPERSON PROBLEM when the number C is a part of the input. Their algorithm is polynomial in C, but not in log C, as it should if we want to have a polynomial algorithm for SSBP.

Fortunately, the algorithm can be easily adapted (mainly, a bipartite matching is replaced by a bipartite b-matching). We get not only a 9.5-approximate value of an optimal balancing tour, but also a polynomial description of a tour that realizes this value (the tour itself has not necessarily a polynomial size since some edges could be traversed a number of times of the same order than C).

+2 +2 +3 -1 -3 -4 -1 A B C D E F G H I +11 -9 Figure 1. An example of input. The number next each vertex is b v if v is in excess, and -b v if v is in default.
To make the adaptation working, we need the following lemma. Recall that an Eulerian graph is a connected graph whose vertices have all an even degree, and an Eulerian tour is a closed walk traversing each edge exactly once. An Eulerian graph has always an Eulerian tour.

Lemma 1. Let H be an Eulerian bipartite graph, with color classes U and U . Consider an input of the SSBP on this graph, with

• a capacity C of the truck,

• q = p ∈ U , • x v = 1 2 C deg(v) if v ∈ U and x v = 0 if not. • y v = 0 if v ∈ U and y v = 1 2 C deg(v) if not.
Then H can be balanced by any Eulerian tour starting and finishing at p = q.

Proof. Take any Eulerian tour starting and finishing at p. Apply the following rule: each time the truck enters a vertex of U , it takes exactly C bikes; each time the truck enters a vertex of U , it delivers exactly C bikes on this vertex. Assuming that there is no problem with the capacity of the truck, this algorithm balances all the vertices, since the truck takes exactly 1 2 deg(v) times C bikes from each vertex of U , and puts exactly 1 2 deg(v) times C bikes on each vertex of U . It remains to check that there is no problem with the capacity of the truck.

We check by induction on the number of traversed edges that each time the truck leaves a vertex of U , it has exactly C bikes, and each time it leaves a vertex of U , it has no bike. This property is true for the first edge of the Eulerian tour. Now, assume it is true at a moment on the tour.

If the truck leaves a vertex of U , it has by induction exactly C bikes. Since H is bipartite, it arrives now on a vertex of U , it delivers exactly C bikes and has now no bike.

If the truck leaves a vertex of U , it has by induction no bike. Since H is bipartite, it arrives now on a vertex of U , it takes exactly C bikes and has now exactly C bikes.

Let us now describe how to adapt the algorithm by Chalasani and Motwani. Recall that we need to suppose that p = q.

We assume that G is the complete graph with a cost function satisfying the triangle inequality. We assume moreover without loss of generality that x(U ex )-y(U ex ) is a multiple of C (it can be achieved with a dummy vertex). Finally, we assume that x p = y p = 0, which is not a restriction, since we can add a dummy vertex at distance 0 of the original p vertex.

Let m be a minimum-cost perfect b-matching of the bipartite graph induced by G when we keep only edges connecting a vertex in default to a vertex in excess, where b v := |x vy v |. On Figure 1, we see an input of the problem, and on Figure 2 an illustration of m.

We first use Christofides' heuristic [START_REF] Christofides | Worst-case analysis for a new heuristic for the Traveling Salesman problem[END_REF] to obtain a 1.5-approximate tour T ex on the set of the vertices in excess. Next, we decompose T ex into consecutive paths P ex 1 , P ex 2 , . . . such that either

• x(P ex i ) -y(P ex i ) = C or +2 +2 +3 -1 -3 -4 -1 A B C D E F G H I +11 -9 1 1 2 2 1 8 3 Figure 2.
A perfect b-matching for the input of Figure 1.

• x(P ex i ) -y(P ex i ) = a ex i C for some integer a ex i if P ex i is a single vertex,
by deleting a set of edges that are spaced along the tour. We proceed as follows.

Start at an arbitrary vertex of T ex and follow the tour in one direction until the sum of the b v of the vertices encountered is equal to or larger than C. These vertices provide then P ex 1 . If the sum of the b v is not a multiple of C, we make a copy of the last vertex v of P ex 1 and insert it just after v in the tour (the new edge has cost 0). This new vertex receives just enough bikes from v in order to get a multiple of C bikes on P ex 1 . We transform accordingly m in order to still have a perfect b-matching (the new vertex 'takes' from each m e with e ∈ δ(v) an arbitrary part, while having the right value for m(δ(v))).

Then we do again the same procedure, starting from the next vertex of the tour (if a copy of v has been done, this copy is this next vertex). And so on, until the whole tour T ex has been decomposed.

We define similarly a 1.5-approximate tour T def on the set of vertices in default, the paths P def 1 , P def 2 , . . . and the integers a def j . Because of the possible splitting of vertices, they may be more than n vertices at the end, but not more than 3n (the 3 comes from the fact that a vertex can be split in 3 copies when it has strictly more than C bikes and when it arrives at the end of a path P ex i ). The whole procedure is illustrated on Figures 3 and4 . Clearly c(m ) ≤ 1 C c(m) (we use the fact that the edges of a C-regular bipartite graph can be partitioned into C perfect matching -it is König's theorem [START_REF] König | Uber Graphen und ihre Anwendung auf Determinantentheorie une Mengenlehre[END_REF]). On Figure 5, we see an example of a b -matching m and how we can build a solution from it on Figure 6.

At this stage we have a collection of connected subgraphs H 1 , H 2 , . . . each consisting of one or several supernodes in excess connected to one or several super-nodes in default. According to Lemma 1, each of this subgraph can be balanced with its own bikes, starting and finishing on one vertex of one of its paths in excess, using 2m e times each edge e in m , and twice the edges of its paths. The lemma can be applied since making 2m e copies of each edge e in any H i makes it an Eulerian graph. The sum of the costs for the balancing of all vertices in the H i is then ≤ 2c(T ex ) + 2c(T def ) + 2c(m ).

To go from one of these subgraphs H i to another one, we can use edges of T ex , which give an additional cost ≤ c(T ex ).

We can balance the whole graph G with a tour of cost SOL such that

SOL ≤ 2c(T ex ) + 2c(T def ) + 2c(m ) + c(T ex ) ≤ 3c(T ex ) + 2c(T def ) + 2 C c(m) ≤ 7.5OPT + 2OPT ≤ 9.5OPT
Here we use that 1 C c(m) ≤ OPT, which is proved in [START_REF] Chalasani | Approximating capacited routing and delivery problem[END_REF]. According to the discussion we have just made Theorem 3. There is a polynomial time algorithm that gives a 9.5-approximate solution for the SSBP when p = q (the truck starts and finishes at the same vertex).

Proof. The only thing that has not be treated in the discussion above concerns the fact that the truck starts and finishes in p. Actually, p (which is assumed w.l.o.g. to be such that x p = y p = 0) can be considered arbitrarily as a vertex in excess. Since, in the proof, we can choose the vertex in excess which we start with (in the definition in P ex 1 ), the above algorithm is definitely a 9.5-approximation algorithm. Remark. If p = q, we can get with the same method another approximation, by replacing the tours T ex and T def by p-q paths on the set U ex ∪{p, q} and U def ∪{p, q}. But this time, the 1.5 ratio of Christofides heuristic does not work and we only get a 5/3-approximation (see [START_REF] Hoogeveen | Analysis of christofides'heuristic: some paths are more difficult than cycles[END_REF]), leading finally to a 31/3-approximation. We do not know if it is possible to do better.

Lower bounds

In this section, we provide a lower bound for the SSBP. It is the optimal value of an integer linear program, whose variables "count" the number of times the truck passes on each edge. The constraints are of three kinds:

• the Eulerian condition: except maybe in p and q, the truck enters and leaves each vertex an even number of times. They are labelled (ii). • "subtour elimination", like for the TSP: if the truck is in p ∈ U ⊆ V and they are unbalanced stations in Ū , then it must necessarily traverse δ(U ) at least once, and maybe more depending on the position of q and the other unbalanced stations. They are labelled (iii). A useful notation to write down these constraints is

µ(p, q, U, x, y) :=                0 if p, q ∈ U and Ū ⊆ B(x, y) 0 if p, q ∈ Ū and U ⊆ B(x, y) 1 if p ∈ U and q ∈ Ū 1 if p ∈ Ū and q ∈ U 2 if p, q ∈ U and Ū \ B(x, y) = ∅ 2 if p, q ∈ Ū and U \ B(x, y) = ∅.
• "capacity constraints", like for the CAPACITED VEHICLE ROUTING problem: if U ⊆ V has too many bikes, the truck must leaves U enough times to remove all these bikes in excess. They are labelled (iv). A useful notation to write down these constraints is

η(p, q, U ) :=        -1 if p ∈ U and q ∈ Ū 0 if p ∈ U and q ∈ U 0 if p ∈ Ū and q ∈ Ū +1 if p ∈ Ū and q ∈ U
The optimal value of the following integer linear program Min z e∈E c e z e s.t.

z e ∈ Z + for all e ∈ E (i) z(δ(v)) is even for all v ∈ V \ {p, q} (ii) z(δ(U )) ≥ µ(p, q, U, x, y) for all U ⊆ V, U = ∅ (iii) z(δ(U )) ≥ 2 x(U )-y(U ) C + η(p, q, U ) for all U ⊆ V, U = ∅ (iv) (2)
is clearly a lower bound for the SSBP.

We will see that it is not at all easy to solve this program. Lower bounds that are easier to compute can be obtained by deleting some of the constraints. Of course, the bounds can then be worse. In Sections 7 and 8, the quality of the solutions will be proved with bounds obtained by deleting constraint (ii). Program ( 2) is an integer linear program: the constraint (ii) can be rewritten in z(δ(v)) = 2y v for a new integer variable y ∈ Z V + . A standard way to solve this kind of program is the branch-and-bound technic, or more precisely here, since the number of constraints is exponential, the branch-and-cut technic. Hence, we must check whether it is possible to separate easily constraints (iii) and (iv). The separation problem for (iii) is: given a map z : E → R + , can we find a subset U ⊆ V with U \ B = and Ū \ B = ∅ such that z(δ(U )) < 1 ? This is simply a min-cut problem, thus there is no problem.

Unfortunately, for the constraint (iv), it is not clear whether there is a polynomial time routine that can separate it. In the classical formulation of the CAPACITED VEHICLE ROUTING PROBLEM -or for short CVRP -there is a similar constraint and its complexity status is open (see [START_REF] Augerat | Seprating capacity constraints in the CRVP using tabu search[END_REF] ; the same paper proposes an efficient heuristic to separate this constraint). The similar constraint of the CVRP is

x(δ(S)) ≥ 2 d(S) C for all S ⊆ V, S = ∅,
where x ∈ R E + is the variable, d ∈ R V + is the demand function and C the capacity of the truck. Instead of separating

z(δ(U )) ≥ 2 x(U ) -y(U ) C + η(p, q, U ) for all U ⊆ V,
we can separate a weaker constraint (and thus have a weaker bound) in polynomial time

z(δ(U )) ≥ 2 x(U ) -y(U ) C + η(p, q, U ) for all U ⊆ V.
This latter constraint can be separated in polynomial time, for it can be reformulate as a min-cut problem as well.

If an optimal solution for the program (2) can be transformed in an optimal solution of the SSBP, then the number of bikes transferred by each move is a b-flow of the digraph obtained from G while replacing each edge e by z e arcs oriented according a p-q Eulerian walk, with a capacity C on each arc, and b v = x vy v for all vertices v ∈ V . Such a flow always exists since constraint (iv) implies that the cut condition is satisfied everywhere in the digraph. But it is not clear, even if an optimal solution for the program (2) can be transformed in optimal solution of the SSBP, that any b-flow can be such a solution.

At least, solutions of program ( 2) can be used in heuristics to build reasonably good solutions.

Complete graph with unit costs

The case of a complete graph with unit cost can model the case when we only want to count the number of times we load or unload bikes on a station.

A 2-approximation algorithm

We show in this subsection that a greedy algorithm provides to the SSBP for unit costs on the complete graph a 2-approximation algorithm.

Consider the following algorithm.

Repeat these two tasks until all stations are balanced:

• While the truck is not full and it remains at least one vertex in excess, repeat: go to a station v in excess, take as many bikes as possible without exceeding the capacity of the truck and while leaving at least y v bikes on the station. • While the truck is not empty, repeat: go to a station v in default and put as many bikes as possible while leaving at most y v bikes on the station.

When they are all balanced, add a move to reach the terminal station.

Theorem 4. The greedy algorithm described above provides a solution SOL such that SOL ≤ 2OPT + 1, where OPT denotes the optimal value of the SSBP.

Proof. Inside the proof, we call the quantity v∈V |x vy v | the total imbalance. We assume first that we start on a station in excess. We prove by induction on the total imbalance that

SOL ≤ 2 v∈V |x v -y v | C -2. ( 3
)
If v∈V |x v -y v | = 2, the inequality (3) is satisfied. Now, suppose that v∈V |x v -y v | ≥ 3.
Denote by s 1 , . . . , s g the first g stations in excess followed by the first h stations t 1 , . . . , t h in default when we apply the greedy algorithm above. Let α i := x siy si and

β j := y tj -x tj . Note that if g ≥ 2, we have g-1 i=1 α i < C, (4)
and a similar property holds for h and the β j .

The truck strats at a vertex is excess, visits g -1 more stations in excess, h stations in default, goes to a station in excess and then is in a situation similar to the one it faced at the beginning, but with a stricly smaller total imbalance (hence induction can be used). Each station s i for i ≤ g -1 has now the right number of bikes. The station s g has now x sg -(C -g-1 i=1 α i ) bikes. Each station t j for j ≤ h -1 has now the right number of bikes. The station t h has now

x t h + (C - h-1 j=1 β j ) bikes.
Using induction, after the visit of the g stations in excess and the h stations in default, the trucks balances the remaining with a cost smaller than 2

  v∈V \{s1,...,sg,t1,...,t h } |x v -y v | C   +2 |x sg -(C - g-1 i=1 α i ) -y sg | C +2 |x t h + C - h-1 j=1 β j -y t h | C -2. Thus SOL ≤ g + h + 2   v∈V \{s1,...,sg,t1,...,t h } |x v -y v | C   + 2 g i=1 α i -C C + 2 h j=1 β j -C C -2.
We have

g + 2 g i=1 α i C ≤ 2g + 2 α g C .
Indeed, for g = 1, it is obvious, and for g ≥ 2, it is a consequence of (4). A similar inequality is satisfied for h and the β j . Hence,

SOL ≤ 2   v∈V \{s1,...,sg,t1,...,t h } |x v -y v | C   + 2 α g C + 2 β h C + 2(g -1) + 2(h -1) -2,
which proves equation (3). To conclude, note that according to program (2)

OPT ≥ v∈V |x v -y v | C (if q is in default, add a -1 on the right-hand side),
which prove that SOL ≤ 2OPT. Add a move to deal with the general case.

Although SOL is computable in linear time once we have fixed any order on the vertices, the algorithm itself is not polynomial, for the reasons explained in Section 4.

Polynomial algorithms for fixed C

The SSBP is polynomial for a complete graph with unit costs and fixed C = 1, 2. Note if we remove the condition of unit costs the problem is NP-hard again since the problem on a bipartite graph, which is NP-hard according to Theorem 2, can be translated into a problem on a complete graph where the costs on an edge uv is the minimal number of edges of a path between u and v in the bipartite graph.

v 1 v 2 v 3 v 4 (0, 1) (0, 3) (2, 0) (2, 0) Figure 7
. An example for which the optimal strategy requires the transportation of a bike several times between stations in default and stations in excess when C = 3, p = v 1 and q = v 3 : the couples (x, y) near each vertex indicates the number x of bikes in the initial state and the number y of bikes in the terminal state.

If z is an admissible solution of program (5), we get

2 e∈E z e = v∈V z(δ(v)) ≥ 2 v∈V |x v -y v | 2 + v∈U ex η(p, q, v) - v∈U def η(p, q, v).
Since η(p, q, v) = 0 if v / ∈ {p, q}, η(p, q, p) = -1 and η(p, q, q) = +1, and assuming that p and q are unbalanced at the beginning of the algorithm, we have v∈U ex η(p, q, v) -v∈U def η(p, q, v) = 2η(p, q, U ex ) (just check all possibilities). Therefore

v∈V |x v -y v | 2 + η(p, q, U ex )
is a lower bound for our problem. The conclusion is straightforward.

The complexity status for the SSBP is open for a complete graph with unit costs and fixed C ≥ 3 (this question is restated in Section 9). We conjecture that there is polynomial time algorithm.

If C = 3 an optimal solution can require the transportation of a bike several times between stations in default and stations in excess, a fact that does not occur when C = 1 or C = 2. Consider example in Figure 7. The optimal solution consists in the following sequence v 1 , v 4 , v 2 , v 3 , with 1 bike in the truck during the travel along edge v 4 v 2 .

8.

A linear time algorithm in the case of a tree

The general case

In this section, we prove that the SSBP can be solved in polynomial time (actually linear time) in the case of a tree. Again, this means that we can compute the exact cost of an optimal balancing sequence, and not that the time to execute the sequence is polynomial. Nevertheless, the sequence can be described in a polynomial way, since we can write the optimal algorithm in this case.

We describe now the algorithm. Actually, we give an explicit solution to the research version of the SSBP in the case of a tree, that is, we give the optimal cost of an optimal sequence and the first move of an optimal sequence, which in a sense solves completely the problem since, as we have already noted, after a first move, we have again a problem of same nature.

Denote by K 1 , . . . , K h the connected components of G -{p}. Now, we will see that there is a rule depending only on the excess or default status of p and the h components that gives a first move of an optimal sequence.

We describe the rule.

(1) All stations are balanced (a) p = q move along the edge steming from p in direction of q. (b) p = q don't move (it is finished). ( 2) There are unbalanced stations (a) There is a component K i in excess take no bike and enter the component K i in excess. (b) There is no component in excess (i) There are several components K i such that we have simultaneously x(K i ) ≤ y(K i ) and at least one unbalanced station in K i choose such a K i such that q / ∈ K i , take min(C, y(K i )x(K i )) bikes enter K i and put the bikes on the first vertex of the component. (ii) There are only one component K i such that we have simultaneously

x(K i ) ≤ y(K i ) and at least one unbalanced station in K i take min(C, y(K i )x(K i )) bikes enter K i and put the bikes on the first vertex of the component.

We emphasize that to apply this rule, the truck must be empty. Since, after having applied it, the truck is again empty, we can apply it as many times as necessary to balance the whole tree.

In case 2b, the truck takes min(C, y(K i )x(K i )) bikes. In this case, it is always feasible since the truck is empty and since we have

x p = y p + h j=1 y(K j ) - h j=1 x(K j ) ≥ y(K i ) -x(K i ) bikes on vertex p (no component is in excess).

Now define

• U e denotes for an edge e the subset of vertices such that δ(U e ) = e and x(U e ) ≥ y(U e ) (if there is equality, make an arbitrary choice), and • for each edge e ∈ E z e (p, q, x, y) := max 2

x(U e )y(U e ) C + η(p, q, U e ), µ(p, q, U e , x, y)

Theorem 5. The rule described above provides a first move of an optimal sequence for the SSBP on a tree (and hence, if repeated, provides an optimal sequence) and the optimal cost is:

e∈E c e z e (p, q, x, y).

Note that the rule is independent from the costs. This theorem solves the preemptive case. The nonpreemptive case is NP-hard [START_REF] Lim | The capacitated traveling salesman problem with pickups and deliveries on a tree[END_REF]. See Subsection 9.4 for further discussions on this point.

Proof of Theorem 5. Define γ(p, q, x, y) := e∈E z e (p, q, x, y).

We will first prove by induction on the value of γ(p, q, x, y) that each edge e is traversed exactly z e (p, q, x, y) times when we apply the algorithm described above. Then according to Equation (2), it implies then that the sequence of moves is optimal.

If γ(p, q, x, y) = 0, then µ(p, q, U e , x, y) = 0, x(U e )y(U e ) = 0 for each edge e, p = q and all stations are balanced (for this second point, prove it by induction on the size of the tree, starting with a leave). Hence, we are in case 1b, and each edge is traversed exactly z e (p, q, x, y) = 0 times, as required. Now, suppose that γ(p, q, x, y) > 0. Let (x , p ) be the state reached after the first move of the algorithm. Assume that we have proved that z e (p, q, x, y) = 1 + z e (p , q, x , y) if e = pp z e (p , q, x , y) if not,

Then, we have γ(p , q, x , y) < γ(p, q, x, y), whence induction can be applied for the state (x , p ), aiming to reach (q, y). By induction, we know that the algorithm applied to (x , p ) leads to a traversing of each edge e exactly z e (p , q, x , y) times. Since the state (x , p ) is obtained just after the move along edge pp , we get that each edge e is traversed z e (p, q, x, y) times when we apply the algorithm. Hence, we only have to prove that ( 7) is correct, and it is what the remaining of the proof is devoted to. Actually, it is easy to see that if e = pp , then x(U e ) = x (U e ), η(p, q, U e ) = η(p , q, U e ) and µ(p, q, U e , x, y) = µ(p , q, U e , x , y). Hence, it is enough to prove Equation [START_REF] Garey | Computers and intractability: a guide to the theory of NP-completness[END_REF] only for e = pp .

Case 1a

We have z e (p, q, x, x) = 1 and z e (p , q, x, x) = 0. Indeed η(p, q, U e ) = µ(p, q, U e , x, x) = 1 and η(p , q, U e ) = µ(p , q, U e , x, x) = 0. Equation ( 7) is satisfied.

Case 2a

We have U e = K i . Note that after the move pp , the subset U e remains the same since x(U e ) remains greater than y(U e ). If q ∈ K i , we have η(p, q, U e ) = 1, η(p , q, U e ) = 0, µ(p, q, U e , x, y) = 1 and µ(p , q, U e , x, y) = 2. Using the fact that x(U e ) > y(U e ), we get that z e (p, q, x, y) = 2

x(U e )y(U e ) C + η(p, q, U e ) = 1 + 2 x(U e )y(U e ) C + η(p , q, U e ) = 1 + z e (p , q, x, y), as required. Hence Equation ( 7) is satisfied. If q / ∈ K i , we have η(p, q, U e ) = 0, η(p , q, U e ) = 1, µ(p, q, U e , x, y) = 2 and µ(p , q, U e , x, y) = 1. Hence Equation ( 7) is satisfied for similar reasons.

Case 2(b)i

We have η(p, q, Ki ) = 0, η(p , q, Ki ) = 1, µ(p, q, K i , x, y) = 2 and µ(p , q, K i , x , y) = 1.

• If y(K i )x(K i ) = 0, Equation ( 7) is clearly satisfied.

• If 1 ≤ y(K i )x(K i ) ≤ C: U e = Ki before the move and we have

2 x( Ki ) -y( Ki ) C + η(p, q, Ki ) = 2 y(K i ) -x(K i ) C = 2 = 1 + 2 x( Ki ) -y( Ki ) -y(K i ) + x(K i ) C + η(p , q, Ki ).
Hence Equation ( 7) is satisfied.

• If y(K i )x(K i ) > C: U e = Ki before and after the move and we have 2

x(U e )y(U e ) C + η(p, q, U e ) = 1 + 2

x(U e )y(U e ) -C C + η(p , q, U e ).

Thus Equation ( 7) is satisfied.

Case 2(b)ii

The study is similar to the previous case (with the additional checking whether q is in or not in K i ).

The case of a line

In this case, the preemptive and non-preemptive version of the SSBP on the line are identical, at least if p is an endpoint of the line and q is not fixed.

Define d v := x vy v and denote by D(v j ) := j i=1 d vi . To make the discussion simpler, we suppose that d v ≤ C for all vertices v (it is easy to see that the algorithm described below can be adapted). If D(vi) C and D(vi+1) C are different and in an increasing order, call v i a positive step. If they are different and in a decreasing order, call v i a negative step. Now, start from p (assumed to be the left endpoint) and go to the right. If a positive step is followed by a negative step, it is possible to balance all stations strictly between them by a simple move from left to right. At the end of this move, the two steps have disappeared. Then, if there is still a positive step on the left of the truck, go back to the positive step, and then go again in the right direction till you reach a positive step followed by a negative step. Repeat these operations until all negative steps are on the left side and all the positive steps on the right side. Now, if a negative step is followed by a positive step, it is possible to balance all stations strictly between them by a simple move from left to right till the positive step without moving any bike and then by coming back to the negative step, this time wile moving the bikes. At the end of this move, the two steps have disappeared. Repeat these operations until all stations are balanced.

By induction on the number of steps, we can prove the optimality of this algorithm.

In general, there may be a difference, even in the case of a tree. Indeed, consider the example of Figure 8. The cost c(e) are all equal to 1 and the capacity of the truck is C = 3. We can balance all the stations in 8 moves. But we necessarily put bikes on station v and then later, we take them again in the truck and put them on stations w and q. If we want to avoid such situations, the minimal number of moves is 10.

Polynomial encoding of an optimal sequence of move

We have seen that it is not clear whether it is always possible to have a polynomial encoding of an optimal sequence balancing the stations. This can be an important issue not always because we want to be able to describe compactly an optimal strategy, but also if we want to explore the set of possible solutions (to implement a local search for instance). 9.4. A cost for the loading/unloading ?

In the same spirit of the distinction between the preemptive version and the non-preemptive one, we can consider the case when there is a cost for the load and the unload of bikes (proportional to the number of bikes for instance). In this case, we can try to optimize according both the distance and the total cost of loading and unloading. A more general model, and maybe more realistic, would include these issues.

As we have seen, in the particular case when the graph is a line, there is no difference but in general for a tree, there may be a gap.

Dynamic stations balancing

In the real situation, the bikes are moving between the stations while the truck tries to keep the stations balanced. We have justified the static version by the situation encountered at the end of the night, just before the morning rush, when there are few bike moves, but when there is a real need of a correct balanceness of the stations.

Nevertheless, there is a real need of a good heuristics in the dynamic case. Such heuristics could depend on the current situation (the number of bikes per stations is the only quantity known about the state of the system at any instant -at least for the system designed in Paris), but also on the dynamic OD-matrix (which tells, in average, at any time of the day, how many bikes go from one station to another one).

.

  The paths P ex i and P def j are seen as "super-node". We now overlay m. We get a bipartite graph with integers m e on each edge e such that m(δ(P ex i )) = C for all i, m(δ(P def j)) = C for all j, except when P ex i or P def j is a single vertex in which case m(δ(P ex i )) or m(δ(P def j )) can be any multiple of C. We pick a minimal cost perfect b -matching m of this bipartite graph, where b P ex i := 1 if P ex i has at least two vertices, or b P ex i := a ex i if P ex i is a single vertex. The same holds for the P def j

Figure 3 .Figure 4 .

 34 Figure 3. Construction of the paths in the 9.5-approximation algorithm for C = 3.

Figure 5 .

 5 Figure 5. A b -matching m as used in the 9.5-approximation algorithm (the numbers next the super-nodes are the b v ).

Figure 6 .

 6 Figure 6. A solution for the SSBP induced by the b -matching m of Figure 5.

Figure 8 .

 8 Figure 8. An exemple for which a cost for the load/unload operation is penalizing: the couples (x, y) near each vertex indicates the number x of bikes in the initial state and the number y of bikes in the terminal state.

Case C = 1.

Repeat this two tasks alternately until all stations are balanced:

• Choose a station v in excess and take 1 bike from it.

• Choose a station v in default and put 1 bike on it.

Case C = 2.

Repeat this two tasks alternately until all stations are balanced:

• Choose a station v in excess with x vy v ≥ 2 and take 2 bikes; if there is no such station choose two stations v and w in excess with x vy v = 1 and x wy w = 1 and take these two bikes; if there is no such stations, take the last bike in excess if there is one. • Choose a station v in default with y vx v ≥ 2 and put 2 bikes on it; if there is no such station choose two stations v and w in default with y vx v = 1 and y wx w = 1 and fill in these two bikes; if there is no such stations, fill in the last bike in default if there is one.

Proposition 1. Assume without loss of generality that p and q are unbalanced (otherwise, it is easy to add the right number of moves to an optimal solution with p or q balanced). The (non-polynomial but greedy) algorithms described above solve the SSBP for fixed C ∈ {1, 2} on the complete graph with unit costs. The number of moves required by them are

Note that the SSBP in its research version can be solved in polynomial time, for we just have to compute one of the formulas and to give the first step of one of the algorithms described above.

Proof. The case C = 1 is obvious.

Proof of the case C = 2. Define respectively U ex 0 and U ex 1 to be the set of vertices v ∈ U ex such that x vy v = 0 mod 2 and x vy v = 1 mod 2. Define also U def 0 and U def 1 to be the set of vertices v ∈ U def such that x vy v = 0 mod 2 and x vy v = 1 mod 2.

The number of moves generated by the algorithm is

which can be rewritten more compactly

The algorithm balances all the stations: indeed, except maybe for the last move or the last two moves, when the truck enters U def , it carries 2 bikes, and when it leaves U def , it is empty.

The following program is program (2) with constraints missing (the last one is obtained formally by letting U := V \ δ(v) in (iv) of ( 2)), Min z e∈E z e s.t. z e ∈ Z + for all e ∈ E z(δ(v)) ≥ 2 xv-yv 2 + η(p, q, v) for all v ∈ U ex z(δ(v)) ≥ 2 yv-xv 2 η(p, q, v) for all v ∈ U def [START_REF] Charikar | Algorithms for capacitated vehicle routing[END_REF]


C Albea

D Puschini

S Lesecq

E Beigné

Optimal and robust control for a small-area FLL

Keywords: Nano systems, FLL, robust control, optimization, disturbance rejection, LMIs

Fine-grain Dynamic Voltage and Frequency Scaling (DVFS) is becoming a requirement for Globally-Asynchronous Locally-Synchronous (GALS) architectures. However, the area overhead of adding voltage and frequency control engines in each voltage and frequency island must be taken into account to optimize the circuit. A small-area fast-reprogrammable Frequency-Locked Loop (FLL) engine is a suited option, since its implementation in 32nm represents 0.0016mm 2 , being 4 to 20 times smaller than classical techniques used such as a Phase-Locked Loop (PLL) in the same technology. Another relevant aspect with respect to the FLL is the control design, which must be suited for low area hardware. In this paper, an analytical model of the system is deduced from accurate Spice simulations. It also takes into account the delay introduced by the sensor. From this model, an optimal and robust control law with a minimum implementation area is developed. The closed-loop system stability is also ensured.

I. INTRODUCTION

The continuous increase in clock frequency together with technology scaling has generated the distribution of a single global clock over a large digital chip tremendously difficult. A Globally Asynchronous Locally Synchronous (GALS) design alleviates the problem of clock distribution by having multiple clocks, each one being distributed on a small area of the chip. A system with different clock frequency domains appears as a natural enabler for fine-grain power-aware architectures. Actually, power consumption is a limiting factor in VLSI integration, especially for mobile applications. Dynamic Voltage and Frequency Scaling (DVFS) [START_REF] Choudhary | Hardware based frequency/voltage control of voltage frequency island systems[END_REF] has proven to be highly effective to reduce the power consumption of the chip while meeting the performance requirements [START_REF] Horowitz | Lowpower digital design[END_REF]. The key idea behind local DVFS is to control at fine grain the supply voltage and the frequency of an island at runtime to minimize the power consumption of the considered island while satisfying the computation/throughput constraints [START_REF] Choi | Fine-grained dynamic voltage and frequency scaling for precise energy and performance tradeoff based on the ratio of offchip access to on-chip computation times[END_REF].

The DVFS techniques mainly rely on two 'actuators'. These actuators need to be dynamically controlled in order to reduce the power consumption while maintaining the required performance. More precisely, the control policy must be carefully designed in order to achieve high power efficiency at low area cost. The voltage actuator fixes the supply voltage of the Voltage and Frequency Island (VFI). It can be a classical buck converter [START_REF] Liu | A dynamic buck converter with ultra fast response and low voltage ripples designed for DVS systems[END_REF] or a discrete Vdd-hopping converter [START_REF] Albea | Control and stability analysis for the Vdd-hopping mechanism[END_REF][START_REF] Miermont | A power supply selector for energy-and area-efficient local dynamic voltage scaling[END_REF]. On the other side, the frequency actuator is a Clock Generator. Its frequency control is related to the supply voltage control in order to avoid timing faults [START_REF] Zhai | The limit of dynamic voltage scaling and insomniac dynamic voltage scaling[END_REF]. This Clock Generator CEA LETI-MINATEC Campus, 17 rue des Martyrs, 38000 Grenoble, France. carolina.albea-sanchez, diego.puschini, suzanne.lesecq, edith.beigne@cea.fr is classically based on a Phase Locked Loop (PLL) or a Frequency Locked Loop (FLL).

Another consequence of technology scaling is the in-die and die-to-die process variability (P-variability). From a practical viewpoint, it is becoming increasingly difficult to manufacture integrated circuits with tight parametric values [START_REF] Miermont | A power supply selector for energy-and area-efficient local dynamic voltage scaling[END_REF]. As a consequence, in-die process variation means that the optimum functional and energetic point of the whole circuit can be found if VFI number i has its functioning frequency in the range [F min,i , F max,i ] [START_REF] Tretz | An all digital frequency-locked loop immune to hysteresis effects for power management of multicore processors[END_REF]. If the clock is generated for the whole circuit, and distributed in each VFI, the maximum acceptable frequency (i.e. the one that will ensure no timing fault for any VFI) will be F max,i = min{F max,i ∀i}, leading to a suboptimal circuit functioning, some VFI being underclocked. Therefore, in order to obtain the best possible circuit performance, the clock must be locally generated and controlled according to Process, Voltage and Temperature (PVT) variations. Recently, control techniques have been applied to the problem of DVFS (for instance, see [START_REF] Albea | Control and stability analysis for the Vdd-hopping mechanism[END_REF][START_REF] Bui | A generic method for embedded measurement and compensation of process and temperature variations in SOCs[END_REF]). However, these works address the closed-loop control of the voltage actuator, this latter implementing a Vdd-hopping technique.

In the context of the industrial French project LoCoMoTiV 1 circuit, an FLL is selected as second actuator due to the area constraint: in a fine-grain GALS context, the FLL can indeed be replicated in each VFI of the size of a processor in a manycore architecture. The FLL has been implemented in a 32nm STMicrolectronics technology. The layout presented in Fig. 1 is fully compatible with the standard cell methodology, to be easily integrated at GALS System on Chip (SoC) level. Its area is about 0.0016mm 2 ; it is 4 to 20 times smaller than a classical PLL in the same technology. The main objective of this paper is to design a control law for the FLL (see Fig. 2) taking into account the following objectives:

• closed-loop stability;

• robustness with respect to PVT variations;

• suited performance (no overshoot, no static error, short transient period);

• low area cost and • exogenous disturbance rejection. Therefore, the designed controller must not only guaranty the set-point stabilization, but also other criterions.

From accurate Spice simulations, it has been seen that the DCO can be modeled with a linear model. Moreover, the sensor introduces a delay that must be taken into account and it is remarked that the system characteristic can change due to PVT effects.

A simple integral controller that requires a minimum implementation area is proposed for this system. For the tuning of the control gain, a robust and optimal control problem is formulated, for which a functional must be minimized. In order to solve this problem some Linear Matrix Inequalities (LMIs) are defined. Satisfying these LMIs within the optimal problem, all objectives above are fulfilled by the closed-loop system. Consequently, an optimal and robust control law for the FLL is reached. Some simulations under the Matlab/Simulink environment show the powerfulness of the proposed controller. Moreover, the closed-loop system was implemented in RTL, obtaining similar simulation results to the ones obtained by Matlab/Simulink. The resulting layout (shown in Fig. 1) was implemented in the LoCoMoTiV circuit in CMOS 32nm.

The rest of this paper is organized as follows: in Section II, the circuit model of the FLL is presented as well as their properties and the error equation. An optimal and robust problem formulation is stated in Section III. Likewise, in Section IV, this problem is solved by providing an approach to tune the control gain. In Section V, the control gain is computed, being tested and implemented in Section VI. The paper ends with conclusions and future work.

Notation. For a given S, the notation Co(S) denotes the convex hull of the set S. ∆η η + -η -, where η + and η - respectively are η(k + 1) and η(k), i.e., the value of η in two consecutive sampling times. Finally, L 2 is the space of {x k } with the norm:

x k 2 2 ∞ k=0 x T k x k < ∞.
II. FLL CONCEPT The main blocks of a FLL are modeled through design considerations and accurate simulations. The main blocks are a Digitally-Controlled Oscillator (DCO) that provides a frequency, a sensor (i.e. a counter) to measure this frequency and a controller that contains a frequency comparator between the targeted frequency and the output frequency and some 'intelligent controller'. In Fig. 3, a sketch of the FLL is shown.

Controller DCO Sensor e k-1 u k f (t) f r f k-1 K s f k K DCO K + - z -1 K s Fig. 3: FLL architecture.
Digitally-Controlled Oscillator. In order to obtain a DCO model some accurate simulations were performed in Spice. From accurate Spice simulations, it can be assumed that the DCO has a linear model, that evolves with respect to Process variation but also to Temperature and Voltage changes (PVT) over time.

The DCO model is

f k = b + K DCO u k + B w w k f k ∈ R 1
is the analog frequency output, u k ∈ N is coded over 8 bits between 0 and 255, respectively. b is the DCoffset, K DCO is a gain. w k is an energy-bounded signal to take account any disturbance, and B w is a constant that defines the disturbance magnitude. In order to take into account the PVT variation effects, it is assumed that parameters K DCO , b and B w can change in the interval

• K DCO ∈ [K m DCO , K M DCO ], • B w ∈ [B m w , B M w ] , • b ∈ [b m , b M ].
Sensor. The sensor, which is a counter, measures the DCO output frequency. This sensor introduces a delay of onesampling period. The delay is present in the feedback loop

M k K s f k-1 .

Control. Define e k

K s f r -f k , where f r is the signal reference and K s is a positive constant that represents the sensor gain. Then, the error equation is

e k = -b -K DCO u k -B w w k + K s f r . (1)
In order to limit the Silicon area and taking into account the control objectives given above, a simple digital integral controller is defined

u k = u k-1 + K(K s f r -M k ) = u k-1 + KK s e k-1 (2)
where K is a the controller constant gain to be tuned. From Eq. (1), it follows

u k-1 = -e k-1 -b -B w w k-1 + K s f r K DCO
which gives the closed-loop system

e k = e k-1 -K DCO K s Ke k-1 + B w w k-1 -B w w k
This can be rewritten in the following linear form:

e k+1 = Ae k + B ūk+1 + B w w k -B w w k+1 , (3)
where

A = 1, B = -K DCO K s and ūk+1 = Ke k . (4)
Note that b does not change the system response.

III. PROBLEM STATEMENT Equation (3) can be rewritten in the following explicit closed-loop form, in such a way that a H ∞ problem can be formulated:

e k+1 = Ae k + BKe k + B w w k -B w w k+1 , (5)
z k+1 = e k+1 . ( 6
)
Problem 1: The problem is to find the optimal gain K, such that the control law ( 2) is robust and the system response is the shortest possible without overshooting. Besides, there exists a Lyapunov functional V k > 0, such that V k+1 -V k along the solution of (5) fulfills

V k+1 -V k < 0, (7)
and for any disturbance input, there exists a minimum disturbance attenuation γ * ≥ 0, such that, for all γ ≥ γ * , the L 2 gain between the disturbance vectors w k and w k+1 , and the output vector z k+1 is less or equal to γ, i.e.

z k+1 2 2 -γ 2 ( w k 2 2 + w k+1 2 2 ) < 0, ∀w k , w k+1 ∈ L 2 . ( 8
)
The solution to this problem guarantees a suited performance as well as a robust stability and robust disturbance rejection for system (5)-( 6).

IV. OPTIMAL H ∞ CONTROL DESIGN

In order to cope with Problem 1 a mathematical manipulation of Eq. ( 5) is performed via a variable change. This allows obtaining feasible LMIs for a robustness problem [START_REF] Fridman | An LMI approach to stability of discrete delay systems[END_REF].

A. Model transformation

Consider

y k e k+1 -e k .

Then, Eq. ( 5) is rewritten in the form [START_REF] Fridman | A Descriptor System Approach to H ∞ Control of Linear Time-Delay Systems[END_REF]:

e k+1 0 = y k + e k -y k + Ae k -e k + BKe k + B w w k -B w w k+1 .
This system can be compactly written as:

Eē k+1 = Āē k + 0 B w w k - 0 B w w k+1 ,
where

Ā 1 1 A + BK -1 -1 , E diag{1, 0}, ēk e k y k .

B. Control design

Problem 1 can be formulated in terms of Linear Matrix Inequalties (LMIs) [START_REF] Fridman | Delay-dependent H inf control of uncertain discrete delay systems[END_REF].

Assumption 1: There exists a Lyapunov function V k , with condition (7) and a γ, such that,

V k+1 -V k +z T k+1 z k+1 -γ 2 (w T k w k +w T k+1 w k+1 ) ≤ ζ T Γζ < 0. (9) where ζ [ē k w k w k+1 ]
T is an augmented state vector and Γ ∈ R 4×4 is a symmetric matrix.

V k is defined by the Lyapunov function

V k = ēT k EP Eē k , (10)
where P P 1 P 2 P T 2 0 , being P ∈ R 2×2 , P 2 = 0 and P 1 > 0.

Next, a sufficient condition for asymptotic stability and disturbance rejection is derived.

Theorem 1: Consider system ( 5)-( 6) with K ∈ R 1×1 and energy-bounded w k and w k+1 . If the following LMIs are satisfied:

P 1 > 0 (11) Γ < 0 ( 12
)
where Γ is defined in Eq. ( 13) found at the top of the next page, then the equilibrium of the closed-loop system ( 5)-( 6) is asymptotically stable and there exists a value γ * , such that for γ < γ * condition ( 8) is fulfilled.

Proof: The goal is to satisfy

V k+1 -V k + z T k+1 z k+1 - γ 2 (w k T w k + w k+1 T w k+1 < 0)
for both disturbance rejection and asymptotic stability of the equilibrium for system ( 5)- [START_REF] Fridman | Delay-dependent H inf control of uncertain discrete delay systems[END_REF].

Lyapunov method yields:

V k+1 -V k = ēT k+1 EP Eē k+1 -ēT k EP Eē k = ēT k ĀT + w k [0 B T w ] -w k+1 [0 B T w ] × P × Āē k + 0 B w w k - 0 B w w k+1 -ēT k EP Eē k = ēT k [ ĀT P Ā -EP E]ē k +ē T k ĀT P 0 B w w k -ēT k ĀT P 0 B w w k+1 +w k [0 B T w ]P Āē k -w k+1 [0 B T w ]P Āē k ,
This developed expression is applied to inequality [START_REF] Liu | A dynamic buck converter with ultra fast response and low voltage ripples designed for DVS systems[END_REF], in such a way that the LMI ( 13) is obtained.

C. Robust control

Now, the uncertain parameters given in Section II are taken into account in order to guarantee the system robustness, at the same time that the closed-loop stability as well as disturbance rejection for the FLL system are also ensured. This means that a robust control under parameter uncertainties is designed For this reason, Theorem 1 is extended in the case of polytopic uncertainties.

Denote

Ω [BK B w ]
and assume that Ω ∈ Co{Ω j , j = 1, 2, 3, 4} namely

Ω = n j=1 λ j Ω j , for some, 0 ≤ λ j ≤ 1, n j=1 λ j = 1
being the vertices of the polytope described by

Ω j = [B (j) K B (j)
w ] for j = 1, 2, 3, 4. Pre-and post-multiplying the LMI [START_REF] Tretz | An all digital frequency-locked loop immune to hysteresis effects for power management of multicore processors[END_REF]

by Q = diag{Q 1 , Q 1 , 1, 1} and taking Q 1 = P -1 2 > 0 and P1 = Q 1 P 1 Q 1 ,
the following sufficient condition is achieved.

Theorem 2: Consider system ( 5)-( 6) with energy-bounded w k and w k+1 , and

K ∈ R 1×1 . If there exist T ∈ R 1×1 and Q 1 ∈ R 1×1 with K = T Q -1 1 and ∈ R 1×1 such that P1 > 0 Γ(j) =     Γ(j) 1 Γ(j) 2 B (j) w Q 1 -B (j) w Q 1 * P1 -2Q 1 B (j) w Q 1 -B (j) w Q 1 * * -γ 2 0 * * * -γ 2     < 0, where Γ(j) 1 2Q 1 (A -1) + 2B (j) T + 1 Γ(j) 2 P1 + Q 1 A -2Q 1 + T B (j) , j = 1, 2, 3, 4,
then, in the vertices j, the equilibrium is asymptotically stable as well as the disturbances are rejected in the entire polytope.

Proof: This is an extension of Theorem 1 for polytopic uncertainties with some mathematical manipulations. Therefore, this theorem proof is straightforward.

D. Optimal and robust control

In order to satisfy all items of Problem 1, some assumptions are performed.

Assumption 2: For w k ≡ 0 and w k+1 ≡ 0, the poles of the closed-loop system (5) are

Z = 1 + BK.
If Z > 0 is chosen, overshoots are avoided. In addition, if K is maximized, the response time is the shortest possible one [START_REF] Ogata | Discrete-time control systems[END_REF]. Remind the control structure (2).

Assumption 3: There exists a functional cost

J u k+1 2 2 + z k+1 2 2 -γ 2 ( w k 2 2 + w k+1 2
2 ) (14) The first term on the right hand side quantifies the response time. Likewise, the other terms (on the right hand side) quantify the disturbance attenuation.

Lemma 1: Suppose that Assumptions 1, 2 and 3 are fulfilled and

Z(i) Q T 1 Z (i) Q 1 .
Then the optimal controller gain K for Problem 1 can be found by: Minimize -J subject to:

Γ(j) < 0 j = 1, 2, 3, 4. Z(i) > 0 i = 1, 2
where

Z(i) = Q 1 + B (i) i = 1, 2.
Proof: The optimal Problem 1 is solved by Lemma 1 if condition (8) is fulfilled [START_REF] Millan | An optimal control L 2 -gain disturbance rejection design for networked control systems[END_REF].

For w k = 0 and w k+1 = 0 and under zero initial conditions

V k+1 -V k ≤ -z T k+1 z k+1 + γ 2 (w T k w k + w T k+1 w k+1
). The summation of both sides is

V k+1 -V 0 ≤ - k k=0 z T k+1 z k+1 +γ 2 k k=0 w T k w k +γ 2 k k=0 w T k+1 w k+1 .
For k → ∞, under the zero initial condition V 0 = 0 and the positive definitiveness of the Lyapunov function, it is proved

∞ k=0 z T k+1 z k+1 ≤ γ 2 ∞ k=0 w T k w k + γ 2 ∞ k=0 w T k+1 w k+1 z k+1 2 2 ≤ γ 2 ( w k 2 2 + w k+1 2
2 ).

Corollary 1: The optimal gain K obtained applying Lemma 1 guaranties both robust stability and robust disturbance rejection. It also provides a short transient period without overshoots.

Γ     ĀT P Ā -EP E + diag{1, 0} ĀT P 0 B w -ĀT P 0 B w * -γ 2 0 * * -γ 2     < 0, (13)
V. OPTIMAL ROBUST CONTROL RESULT

In this section, an optimal and robust control is computed for the FLL by employing the approach presented above.

Digitally-Controlled Oscillator. The DCO parameters can change within the following intervals:

K DCO ∈ [10, 30] • 10 -3 GHz/LSB
The disturbance parameter is given by

B w ∈ [0.1, 0.4]
Sensor. The maximum frequency at the input of the sensor is supposed equal to 5GHz and K s = 85 (LSB/GHZ).

The optimal control problem (Problem 1) is solved, dealing to

K = 0.392, (15)
together with γ = 1.8 and P 1 = 0.2663.

VI. SIMULATION AND IMPLEMENTATION RESULTS

In this section, some simulations in the Matlab environment show the robustness of the control law proposed for the FLL. For these simulations, the data above are reported and a sampling period of 60ns is taken.

Remind that the FLL characteristic curve can change due to PVT variations as shown in Fig. 4. In order to validate the system robustness with respect these changes, three different models are considered (see Fig. Figure 6 shows the closed-loop response of 'syst 1', 'syst 2' and 'syst 3' to a change in the reference frequency, f r . These tests show that the equilibrium is robust with respect to the uncertainty in the characteristic curve. Note that the response time at 5% is achieved before the 7 th sampling time. Figure 7 shows the frequency output, when the characteristic curve changes ('syst 1', 'syst 2' and 'syst 3') and when there is some exogenous disturbances in the output of the system. This example shows the great robustness of the system when the optimal robust control tuning is employed. The FLL with the controller was implemented in VHDL, obtaining the layout shown in Fig. 1. The signal evolutions are presented in Fig. 8. Note that u k presents a delay with respect to f r , this is due to asynchronous issues of the chip, and it is not relevant in the closed-loop system. The delay presented by the sensor is seen in f k-1 . The system response is consistent with Fig. 6, and the real output, f , is also reported.

VII. CONCLUSION

In this paper, a small-area Frequency-Locked Loop (FLL) engine is employed to implement a DVFS in GALS architecture. The use of a simple control law has allowed a fully digital implementation in standard cells, attaining a small area. Implemented in a 32nm technology, the proposed design represents 0.0016mm 2 , i.e. from 4 to 20 times smaller than classical techniques used such as a Phase-Locked Loop (PLL) in the same technology. Likewise, this control law is optimal with respect to system performance (short transient period and no overshoot) and disturbance attenuation. Another suited property offered by the control law is the robustness with respect to PVT variations. In addition, the closed-loop system stability is guaranteed. Some simulations under Matlab show the closed-loop system robustness. Likewise, the FLL with the controller was implemented in VHDL in order to obtain the implementation layout.

First version of the FLL (included the control law proposed in this paper) has been implemented in a 32nm technology. The circuit is currently under founder and performance attained on the real chip will be show during the oral presentation.

Fig. 1 :

 1 Fig. 1: FLL layout. 1 Local Compensation of Modern Technology Induced Variability (LoCo-MoTiV) is a CEA-Leti Minatec Project

Fig. 2 :

 2 Fig. 2: FLL block diagram.

  Figure 4 shows the frequency characteristics of the postlayout DCO (with extracted R & C parasitcs) in function of the input 8-bits binary word. The Y-axis corresponds to the measured raw frequency: this frequency must be divided by 2 to obtain a usable clock frequency with a 50% duty ratio. The 'nominal' case (curve in the middle) is measured at 25 o C with a 1.1V supply voltage. The 'best' case (top curve) is obtained with best case parasitic extract (minimum R, C), 'FastFast' transistors, a supply voltage of 1.2V and a temperature of 125 o C. The 'worst' case simulation is performed with worst case parasitic extract (maximum R, maximum C), 'SlowSlow' transistors, at 1.0V supply voltage and a temperature of 0 o C.

Fig. 4 :

 4 Fig. 4: DCO characteristics (measured raw vs. input word)

5 ): syst 1 :Fig. 5 :

 515 Fig. 5: Variation of the characteristic curves.

Fig. 6 :

 6 Fig.6: Evolution of the output frequency for three different systems (blue), reference frequency (red) and response time at 5% (green).

Fig. 7 :

 7 Fig. 7: Evolution of the output frequency with disturbance and for three different systems.

Fig. 8 :

 8 Fig. 8: VHDL Simulation of syst 1.

ACKNOWLEDGMENT

This research has been supported by the POLLUX Artemis project 100205. The authors want to thanks ST-Microelectronics for his valuable comments.


Juliette Dumont
email: juliette.dumont@univ-paris3.fr

From intellectual cooperation to cultural diplomacy :

the Brazilian and Chilean experiences Before European supremacy was challenged after World War I, exchanges between intellectuals, scientists, and physicians in particular, were already increasing between Latin American countries. This dynamics reached a climax in the 1930's with a growing number of university exchanges, notably between the Southern Cone's countries, but also towards the United States.

At first these exchanges were launched by scientists and academics, and they were meant to become both a medium and an instrument for countries like Brazil and Chile to develop tools for cultural diplomacy. Over the course of a decade Brazilian and Chilean governments had indeed become aware that intellectual cooperation could benefit their national propaganda. Thus they decided to get involved into multilateral organizations: the International Institute of Intellectual Cooperation and the Pan-American Union. The IICI, prior to the UNESCO, was linked to the League of Nations and mostly European-rooted, when the Pan-American Union was closely dependant on the United States. These two institutions enabled Brazil and Chile to create a national image that they could promote worldwide.

This paper intends to show how these two countries built an international identity thanks to two types of networks: informal networks created by the exchanges between Latin American countries

and formal networks set up by the IICI and the Pan-American Union. We will first picture these two dynamics dealing with intellectual cooperation, and then present the structuring process of the multi-faceted Brazilian and Chilean cultural diplomacies. Finally we will study more specifically the academic exchanges. Over the course of our presentation, we will try to identify who the involved actors were and which countries were the main targets of Brazil's and Chile's cultural policies.

Questioning these issues will lead us to define what Brazil's and Chile's diplomatic objectives were so as to establish where they would stand on the international scene.

The transnational character of intellectual cooperation led us to analyze two specific countries, Brazil and Chile. Our research project -a comparative study -will deal with networks, exchanges and movements of men and ideas. Although these countries were thoroughly different, given their geographical dimensions and their (contrasted) political objectives, both Brazilian and Chilean governments aimed at improving their international status. It seems therefore interesting to study how those two governments used soft power to support their national interests.

I. Informal and formal networks

In 1937, at the second meeting of the national commissions of intellectual cooperation which took place in Paris, Miguel Osório de Almeida, delegate of Brazil, presented a report entitled "The inter-American intellectual cooperation. Its beginnings, evolution and organization". On the one hand, he pointed out the difficulties Latin American countries had to face in terms of economic, social and politic issues to explain that intellectual cooperation was not a priority in their agenda. On the other hand, he insisted on their interest for the question, even before the League of Nations created the International Commission of Intellectual Cooperation in 1922. He declared: "We began, thus, in many parts of America, to do intellectual cooperation before everyone. Journeys, meetings, congresses, general conferences, recommendations, resolutions, all means were employed to achieve this goal" 1 . In other words, America had got ahead of Europe. The speech of Miguel Osório de Almeida also challenged an idea that still prevails today, according to which intellectual, scientific and cultural exchanges between Latin-American countries were (and are) non-existent.

A few Latin American researchers, such as Hugo Suppo or Marta de Almeida 2 , tried to demonstrate that the Brazilian delegate was not mistaken. For that purpose, they studied the Medicine congresses that have taken place since the beginning of the 20 th century. There were two types of congresses:

the Latin American congresses of medicine, first set in Buenos Aires in 1898, and the Pan-American congresses of medicine, the first edition of which took place in Washington in 1891. Marta de Almeida notices that the latter attracted countries of both Central-and North America, while the first gathered countries from the South Cone. It was a fact that the Pan-American congresses of medicine played a prominent part in setting the dynamics of the Latin-American congresses of medicine:

Argentina, Chile, Uruguay and Brazil provided for both the meeting's places and the majority of the participants.

According to their general settlement, the Latin American Congresses of Medicine were meant to achieve five objectives : 1) to contribute to the progress of medical sciences; 2) to spread the scientific knowledge that could be of interest for the Latin American nations; 3) to favour the adoption of uniform measures in the field of international sanitary protection; 4) to create and maintain solidarity bonds between institutions, associations and medical personalities in Latin America by favouring the intellectual exchanges; and 5) to pursue only scientific goals. We can say that these objectives match the definition of intellectual cooperation perfectly. The corollary is the creation of networks: we often find the same actors in the committees in charge of the organization This is how we can explain why Brazil, despite its withdrawal from the League of Nations, never questioned its membership of the intellectual cooperation organization.

In the meantime, in 1917, the Pan-American Union created a Service of Intellectual Cooperation, and favoured many scientific encounters. Besides, after the war, intellectual cooperation became a topic of discussion in the Inter-American conferences.

Chile and Brazil took part in this dynamics. A Brazilian project was at the origin of the creation of the Inter-American Institute of Intellectual Cooperation at the time of the Habana conference in 1928.

And Chile organized the first American meeting of national committees of intellectual cooperation in Santiago in 1939.

Thanks to these formal and informal networks, the practice of intellectual cooperation became more usual in America, particularly in the southern half of the continent. It led to a real "pactomania" in this field, especially in the 1930's. Treaties, agreements, covenants were signed, either between two countries or on a continental scale. The social and political contexts of those years can also explain the multiplication of such treaties: the Good Neighbor Policy launched by Roosevelt, the fear of a new war, the feeling of a certain decadence of Europe can be evoked.

The agreements used to deal with three types of matters:

1) Artistic and cultural cooperation;

2) Teaching and education (particularly with the exchange programs offered to professors and students);

3) The exercise of liberal professions.

In the scope of this paper, we will focus on the second topic. As for the continental covenants, we will only mention those related with this subject. The first was a resolution approved in 1910 at the 4 th Inter-American conference and was meant to encourage university exchanges. The fact that a similar resolution was also approved in 1933 at the Montevideo Conference, shows how difficult it was to launch such a dynamics in a continent where the elites were mostly attracted to Europe.

The way countries like Brazil and Chile structured their cultural diplomacy departments in the 1930's, the national interest they had in being part of this movement are some keys to understand why this type of agreement was more successful than in the previous period.

II. Structure and goals of the Chilean and Brazilian cultural diplomacy

This paper, as my PhD work, is based on the idea that Brazil and Chile (and Argentina) used cultural relations to build their cultural diplomacy. These two terms are often used as though they were synonymous. In fact, the differences between them are fundamental. As JM Mitchell wrote, "the purpose of cultural relations is not necessarily (…) to seek one-sided advantage. At their most effective, their purpose is to achieve understanding and co-operation between national societies for their mutual benefits" *1986, p.5+. Whereas "cultural diplomacy is narrower in scope. It is essentially the business of governments" *idem, p.3+, and "seeks to impress, to present a favourable image, so that diplomatic operations as a whole are facilitated" *idem, p.5+.

Cultural diplomacy can be undertaken in a large variety of ways, and this is the reason why we chose to compare the Brazilian and Chilean experiences. If the structure of government and social institutions differs in these two countries, their goals in terms of image on the international scene were quite similar. In 1927, Gabriela Mistral, the Chilean delegate at the IICI, wrote an article in the diary El Mercurio to encourage the participation of Latin American countries to this institution because "Spanish America needs to be better known by Europe where so many superficial opinions can be heard about this part of the world. Spanish America has to promote information about its schools, its classics and its press." 5 An undated Chilean report gave the same analysis: "the work of the international intellectual cooperation (…) could be for us a propaganda tool in order to publicize our intellectual production." 6 The Brazilian discourse was not different: "For us the intellectual cooperation must mean propaganda of Brazil" 7 . Both Chilean and Brazilian actors of cultural diplomacy pointed out the need to transform their country's image abroad. And abroad meant

Europe. These individuals wanted to fight the New World clichés and the patronizing opinions of Old Europe. Ildefonso Falcão, a Brazilian diplomat involved in the setting up of the Brazilian cultural diplomacy, was deeply aware of this challenge when he wrote: "It is time that we get known abroad through our achievements so that Brazil stops being considered as a vast area populated by savage Indians and illiterate half-breed". 8 For these two countries, whose governments aimed at gaining legitimacy on the international scene, this type of image had to be erased and replaced. Political and intellectual elites were anxious to prove that their countries deserved a seat among the circle of the modern and civilized nations. For that purpose, the informal and, more and more, the formal network would appear as relevant instruments. The IICI, in this context, seemed to be the most efficient, since it had "the biggest influence" 9 . This is the reason for which the cultural diplomacy of Brazil and Chile was built around the Institute's network. Nevertheless, institutionally speaking, different paths were chosen.

As far as Brazil is concerned, the Ministry of Foreign Affairs -also called Itamaraty -became the core of such politics. We've seen that Rio Branco was acutely aware that intellectual cooperation could benefit the national propaganda. In the 1920's, the Itamaraty favoured the participation of Brazilian personalities in inter-American and international congresses, supported Xavier de Oliveira's project order. In this text it was stipulated that this Service would be "an organ of connection with the International Institute of Intellectual Cooperation"10 . In fact, it was much more than this. According to Ildefonso Falcão, who ran it in 1935-1936, "it is a service meant to present Brazil in all its cultural aspects This service will publicize every Brazilian cultural achievement and will thus foster intellectual cooperation with the modern world educated community".11

Ribeiro Couto, whose action had been decisive for the creation of the Service, made its goals even clearer: "The purpose is to set the basis for a discreet propaganda of Brazilian intellectual values abroad, avoiding, as much as possible, that these endeavours should be perceived as an ostentatious official propaganda"12 .

In the case of Chile, the Ministry of Foreign Affairs did not play such a prominent part, but it was not entirely absent either. The main actor was no doubt the University of Chile.

In the 1920s, the Chilean government took little part in the IICI's work. Its main contribution was the nomination of Gabriela Mistral as a delegate to this institution. But her many other activities as a diplomat did not enable her to fulfil this mission, even though her reputation was a trump card for the image of Chile in European circles. She nevertheless remained connected to the Institute until 1939, as a member of the Ibero-American committee in charge of the edition in French of works from this part of the world.

The relations between the IICI and the countries members were not only undertaken by their governments: a national committee of intellectual cooperation was founded, bringing together the representatives of the intellectual life of the country. Such a committee was founded in Brazil in 1925, officially independent from the government, but in fact closely linked to it. In Chile, the national committee was first created in 1930 by Francisco Walker Liñares, the Chilean delegate to the League of Nations. Because of the political troubles that shook the country at that time, the committee did not start its work until 1935, when the University of Chile reactivated it. Even if the Ministry of Foreign Affairs and the Ministry of Education provided for its financial needs, and even if representatives of theses ministries were part of it, the Chilean committee was quite independent from the government bodies. Its goal was to "establish contacts and coordination between the different cultural activities of the country, and to create spiritual bonds with foreign countries, so as to publicize the Chilean culture abroad and the foreign cultures in Chile" 13 . In 1936, an Office of Intellectual Cooperation was created within the university, thereby demonstrating a will to make the university the very core of Chilean cultural politics. Where the Brazilian organization was entirely designed for the international scene, the structure chosen for the Chilean cultural politics illustrates an opposite goal: its target was mostly national. This is not surprising when we consider the fact that two of its main actors were Juvenal Hernandez and Amanda Labarca. The first was the university rector from 1933 to 1953, and many authors refer to this period as "one the most brilliant, stable and prestigious stage of the University of Chile" 14 . They insist on the effort made by Juvenal Hernandez to spread culture through the university among all social classes. As for Amanda Labarca, her commitment in the area of education was well known: she had been head of the secondary school system of in 1931, and of the Study Department of the University of Chile from 1933 to 1956.

III. Academic exchanges: a tool for the Brazilian and Chilean cultural diplomacies

Until the 1930s, academic exchanges in America were quite rare, although not inexistent. The numerous agreements signed in the course of the decade, and the increasing interest for intellectual cooperation, not only in Brazil and Chile, but also in Argentina, Uruguay, Bolivia and Peru, led to a change.

13 Comisión chilena de Cooperación Intelectual, 22 años de labor : 1930-1952, Santiago de Chile, 1953, p.5 14 Rolland Mellafe, Maria Teresa Gonzalez, El Instituto Pedagogico de la Universidad de Chile (1889Chile ( -1981) ) : su aporte a la educación, cultura e identidad nacional, Monografías de Cuadernos de História, n°2, 2007, p.147 As far as Brazil is concerned, the exchanges of professors and students with the other American Republics started acquiring some importance from 1937 on, and in 1945, the Service of Intellectual Cooperation was in charge of exchanges with twelve American countries: Canada, Argentina, Paraguay, Uruguay, Venezuela, Bolivia, Chile, Peru, Colombia, Ecuador, the Dominican Republic and Costa Rica. The agreements with the United States were quite different and were not undertaken by the Service. We know that professors and scientists from this country came to Brazil to take part in conferences and that students from the latter went to the United States. The relationship between both countries was rather asymmetrical, one delivering the knowledge and the other receiving it15 .

The Itamaraty helped, as much as possible, send professors in countries with under-developed educational bodies, as was the case with Bolivia for example.

In 1944 the Service provided for 90 grants for foreign students in Brazil. They were distributed as such: Bolivia (10), Chile (12), Colombia (1), Ecuador (2), Peru (1), The Dominican Republic (2), Costa Rica (1), Uruguay (3), Argentina (2) and Paraguay (56). We can note the disparity in favour of Paraguay, which can be explained by the role this country played in the rivalry between Argentina and Brazil for the leadership of South America. These two countries also organized numerous multiple student exchange towards Uruguay. It is also interesting to point out the increasing academic and intellectual exchanges between Argentina and Brazil. From the 1930s to 1950s, the Argentine and Brazilian governments encouraged the creation of many delegations, poetry or writing contests between schools in the two countries, and grants were offered so as to promote research on topics related the neighbour nation. This dynamics implied a commitment of actors from both the State and the civil society. In this case, intellectual cooperation, and the way it became a tool for cultural diplomacy, appears clearly as a means to strengthen the manoeuvres of the traditional diplomacy.

Whereas academic exchanges were managed by the Ministry of Foreign Affairs in Brazil, it was the University of Chile that undertook the whole organization in this country.

In 1936, when the National Committee of Intellectual Cooperation began to manage academic exchanges, 13 grants were allocated to Chilean students. In 1949, the number of grants came to 187.

The committee did not provide for the grants: they were allocated by the Ministry of Education, the Ministry of Foreign Affairs, and by the partner countries of the exchanges. Apart from the grants, the university favoured academic exchanges by the organization of visits of groups of Chilean students to other countries. For example, in 1936, a group from the Faculty of Commerce and Industrial Economy visited Ecuador, Peru and Colombia. These visits used to be a real exchange for the visited country would send later students or professors: also in 1936, a Chilean group went to the Medicine School of Buenos Aires, and the next year an Argentine group visited its counterpart in Santiago16 .

The other side of the exchanges was the welcoming of foreign students. In 1941, for example, they

were distributed as such : Argentina (6), Bolivia (1), Brazil (1), Colombia (2), Costa Rica (2), Ecuador

(2), United States (2), Guatemala (1), Haiti (1), Honduras (1), Mexico (2), Santo Domingo (1), San

Salvador (1), Panama (2), Paraguay (2), Peru (2), Uruguay (2), and Venezuela (2)17 . 18 countries were concerned, which can be considered as a will from the University of Chile to attract students from the whole of America. That was a means to make Chile appear as an educational centre in the continent.

The reception of the foreign students was particularly important during the Summer Courses that began to be organized in 1935. The initiative was taken by Juvenal Hernandez and Amanda Labarca, who undertook their organization, following the model of the North-American Universities where both of them had taught 18 . The Summer courses were not only designed for foreign students; they also aimed at attracting Chilean professionals. Once more, we can see that the cultural politics of the university were addressed to both a national and an international public. Between 1935 and1959, 119 Summer courses were organized, were attended by 79 000 students, of which 5000 came from

Latin-American countries.

The question is: can national-focused policies created by a single university be called "cultural diplomacy"? We can say that the work of the university was a part of it. If the Ministry of Foreign Affairs never created, as Brazil did, a special service dedicated to this field, it did not despise the benefits of a cultural expansion. This is not the purpose of this paper to detail the other actions of that ministry in terms of cultural diplomacy. This is why we will only focus on the use that was done of the university's work. The Ministry used to publish documents of "Information and propaganda" aimed at being distributed among the Chilean diplomatic network so as to provide elements that could be divulgated to improve Chile's image abroad. One of these documents is dedicated to the University of Chile 19 . Here is a quotation from the introduction: "When we consider Chile's history, the civilizing and leading part played by the University of Chile can be considered as a permanent feature; this institution was at the origin of the Republic, had formed the generations who headed the country, who gave Chilean public life the principles of law and civilization; and these principles had prevailed both in the Chilean society and in Chile's relations with the other people" 20 .

We can notice the image of Chile the Chilean governments and intellectuals wanted to publicize abroad was that of a civilized and modern country, whose strength lied in its educational system. A country that, therefore, could be considered as a model.

18 Jorge Caceres VALENCIA, La Universidad de Chile y su aporte a la cultura tradicional, 1933-1953, Santiago, Ed. Esparza, 1998, p.44 19 Ministry of Foreign Affairs, Información y propaganda, Boletín de divulgación, n°1, 6 pages, no date 20 Idem, p.1

Conclusion

We can draw many conclusions from what has been said. First of all, the participation of Chile and Brazil in the intellectual cooperation networks and their setting up of a cultural diplomacy couldn't have been possible without the commitment of a great number of intellectuals who played a decisive part. It's undeniable in Chile, where the university is at the core of the system. In Brazil, it stems from the general politics of Getúlio Vargas. Even before the proclamation of the Estado Novo in 1937, Vargas had converted the State into "the superior representative of the idea of Nation" 21 and arranged things so as to make intellectuals develop their thought within the scope of the state.

He succeeded quite easily since there was a convergence of interests between a state that proclaimed itself as the true mainspring of society, and intellectuals who used to consider themselves as "the most enlightened group of the society", and tended to "educate the Nation" 22 .

The interest of my research on cultural diplomacy lies therefore not only in its consequences for the foreign policy of these two countries: the development of their international image began at a time when national identity was being debated, and when intellectuals were being summoned to clarify what "brasilianity" and "chileanity" actually meant. Our PhD project will compare what is presented as the "true" Chile and Brazil on the international scene, and what is considered as the core of their national identity inside their frontiers.

We also want to demonstrate that, although they were considered as secondary powers in terms of geopolitics, both Brazilian and Chilean governments aimed at playing a relevant part in the world that emerged after World War I. Cultural diplomacy can be seen both as an alternative and a support to traditional diplomacy. For example, Brazil's participation to the IICI's work allowed this country to appear on the European scene although its government had left the League of Nations in 1926. Moreover, the presence of Chilean and Brazilian intellectuals in international organizations and 21 VELLOSO Mônica Pimenta, Os intelectuais e a política cultural do Estado Novo, Rio de Janeiro, Centro de Pesquisa e Documentação de História Contemporânea do Brasil, 1987, p.3 22 Idem, p.4 networks gave their country an aura and a legitimacy that could be exploited by diplomats. It helped them to be considered as "serious", "modern" and "cultivated" nations. We must add that the recognition they could get from Europe through the IICI gave them legitimacy among the other Latin American nations, where the European reference was still powerful.

A new dynamics was set in this period: Latin American countries were eager to bond more on the sub-continental level. And for that purpose, intellectual cooperation, and in particular academic exchanges, constituted a privileged path. The role of the Good Foreign Policy was certainly an element worth mentioning as we've seen with Brazil and Chile, where the United States had become a major partner. Nevertheless, the main lesson we can draw from their activity in the field of academic exchanges, is their will to be integrated into a Latin American dynamics. As for Brazil, the challenge was to modify the perception its neighbours had of a Portuguese-speaking country, which used to be an Empire when the ancient Spanish colonies became republics. In the case of Chile, it is a question of breaking its geographical isolation and draw attention away from its conflicts with Peru, Bolivia or Argentina. As the organizer of the first Conference of the American Committees of International Cooperation in Santiago in 1939, Chile had become, for the time of the meeting, the very centre of the continent, instead of one of its fringes.

Academic exchanges made one thing possible: continental solidarity stopped being a matter of diplomats and politics only to start involving parts of the civil society as well.

  of Inter-American Institute of Intellectual Cooperation, and nominated a delegate, Elyseu Montarroyos, to the IICI. Montarroyos was very active and spoke very soon in favour of the development of Brazil's activities in the field of intellectual cooperation. However it is mostly under Getúlio Vargas' regime, from 1930, that this conviction led to a formal organization. A Service of Intellectual Cooperation was finally created in 1934, but formally instituted in 1937 by a ministerial

7 Arquivo Histórico do Itamaraty (AHI), 542,6, 1045/18392, 26/03/1939 8 AHI, 542,6, 995/16141, 02/02/1936, Diario de Noticias, Rio de Janeiro 9 AHI, 542,6, 1045/18392, 26/03/1939

Quoted by Hugo Rogélio SUPPO, « Ciência e relações internacionais. O congreso de 1905 », in Revista da SBHC, n°1/2003, Ciência e relações internacionais, p.28

Rio Branco's speech at the opening of the third congress, quote by HugoSUPPO [2003, p.9].

UNESCO, A I 83, 13/07/1927

UNESCO, A III 46

UNESCO, A I 86, 23/06/1937

AHI, 542,6, 995/16141, 02/02/1936, Diario de Noticias

AHI, 542,6, 995/16141, 01/03/1934

See Roberta LIMA, Maria Ferreira, A Política brasileira de expansão cultural no EstadoNovo (1937Novo ( -1945)), mestrado em história,UERJ, 2006

Boletín Bimestral de la Comisión Chilena de Cooperación Intelectual, Nov.-Dec., Año I, n°6

Ministry of Foreign Affairs, Chile, Circulares ordinarias 1936-1943, n°33, 24/09/1941.