F R Éd

Éric Meunier

Bertrand Neveu

COMPUTING SOLUTIONS OF THE PAINTSHOP-NECKLACE PROBLEM

Keywords: combinatorial optimization, integer programming, local search, paintshop problem, pathfollowing method, splitting necklace, TFNP problem

How to assign colors to occurrences of cars in a car factory ? How to divide fairly a necklace between thieves who have stolen it ? These two questions are addressed in two combinatorial problems that have attracted attention from a theoretical point of view these last years, the first one more by people from the combinatorial optimization community, the second more from the topological combinatorics and computer science point of view.

The first problem is the paint shop problem, defined by Epping, Hochstättler and Oertel in 2004. Given a sequence of cars where repetition can occur, and for each car a multiset of colors where the sum of the multiplicities is equal to the number of repetitions of the car in the sequence, decide the color to be applied for each occurrence of each car so that each color occurs with the multiplicity that has been assigned. The goal is to minimize the number of color changes in the sequence.

The second problem, highly related to the first one, takes its origin in a famous theorem found by Alon in 1987 stating that a necklace with t types of beads and qau occurrences of each type u (au is a positive integer) can always be fairly split between q thieves with at most t(q -1) cuts. An intriguing aspect of this theorem lies in the fact that its classical proof is completely nonconstructive. Designing an algorithm that computes theses cuts is not an easy task, and remains mostly open.

The main purpose of the present paper is to make a step in a more operational direction for these two problems by discussing practical ways to compute solutions for instances of various sizes. Moreover, it starts with an exhaustive survey on the algorithmic aspects of them, and some new results are proved.

Introduction

The paintshop-necklace problem. There is a beautiful combinatorial problem, which, depending on the point of view, appears as an hard optimization problem or as one of the most beautiful applications of algebraic topology in combinatorics.

The optimization version of the problem is called the paint shop problem, and was defined by Epping, Hochstättler and Oertel [START_REF] Epping | Complexity results on a paint shop problem[END_REF]. The origins of the model lie in car manufacturing with individual demands, which is reported to occur often in Europe. Given a sequence of cars where repetition can occur, and for each car a multiset of colors where the sum of the multiplicities is equal to the number of repetitions of the car in the sequence, decide the color to be applied for each occurrence of each car so that each color occurs with the multiplicity that has been assigned. The goal is to minimize the number of color changes in the sequence. If cars are considered to be letters in an alphabet, the following is a formalisation.

Paint shop problem

INPUT: A finite alphabet Σ whose elements are called letters, a word w = (u 1 , . . . , u n ) ∈ Σ * , a finite color set C and a requirement r : Σ × C → Z + .

TASK: Find a coloring c = (c 1 , . . . , c n ) ∈ C n , such that for all u ∈ Σ and c ∈ C, we have |{i ∈ {1, . . . , n} : u i = u and c i = c}| = r(u, c), and the number of color changes within c is minimized.

We say that we have a color change in c whenever c i = c i+1 . The minimum of the number of color changes is denoted γ = γ(w; r).

The paint shop problem has a solution only if c∈C r(u, c) is exactly the number of occurrences of u in w.

A special case has received a special attention: the binary paint shop problem, which is the case when |C| = 2 and r(u, c) = 1 for the two elements c in C and for all u ∈ Σ. In this case, we have n = 2|Σ|.

The other version of this problem is the necklace splitting problem, which found its motivation in a theorem of Alon [START_REF] Alon | Splitting necklaces[END_REF] (for a didactic proof, see [START_REF] Matoušek | Using the Borsuk-Ulam theorem[END_REF]). q thieves have stolen a precious necklace, which has n beads. These beads belong to a set Σ of t different types. Assume that the number of beads of each type is a multiple of q, say qa u beads of type u ∈ Σ, where a u is a positive integer. Remark that we have q u∈Σ a u = n.

As we do not know the exact value of each type of beads, a fair division of the necklace consists in giving the same number of beads of each type to each thief. The number of beads of each type is a multiple of q, hence such a division is always possible: cut the chain at the n -1 possible positions. Isn't it possible to do the division with less cuts? The answer is yes, as shown by the following theorem proved by Alon: Theorem 1. [START_REF] Alon | Splitting necklaces[END_REF] A fair division of the necklace with t types of beads between q thieves can be done with no more than (q -1)t cuts.

It was first proved by Goldberg and West in 1985 [START_REF] Goldberg | Bisection of circle colorings[END_REF] when q = 2 (this last theorem got a simpler proof in 1986, found by Alon and West and using the Borsuk-Ulam theorem [START_REF] Alon | The Borsuk-Ulam theorem and bisection of necklaces[END_REF]).

Note that this theorem tells nothing about the way of finding such cuts. Given a necklace satisfying the condition of the theorem, the necklace splitting problem requires to find the (q -1)t (or less) cuts giving a fair division.

To make the parallel with the paint shop problem, the necklace can be seen as a word w where the letters are the types of beads and the colors are the thieves. A formalisation is (only to respect the symmetry with the presentation of the paint shop problem)

Necklace splitting problem

INPUT: A finite alphabet Σ of size t whose elements are called letters, a word w = (u 1 , . . . , u n ) ∈ Σ * in which each letter u is present qa u times where a u is a non negative integer.

TASK: Find a coloring c = (c 1 , . . . , c n ) ∈ {1, . . . , q} n such that for each u ∈ Σ, we have |{i ∈ {1, . . . , n} : u i = u and c i = 1}| = . . . = |{i ∈ {1, . . . , n} : u i = u and c i = q}|, and such that the number of color changes is less than or equal to (q -1)t.

An instance of the necklace splitting problem is a special instance of the paint shop problem where each letter must occur a multiple of q times, where the set C of colors has cardinality q and r(u, 1) = . . . = r(u, q) = a u for all u ∈ Σ. c i indicates which thief (numbered 1, . . . , q) gets the ith bead. Theorem 1 states that in this case γ(w, r) ≤ (q -1)t.

Finding solutions for the necklace splitting theorem, in addition to the motivation from a complexity point of view explained below, has applications for instance in VLSI circuit design [START_REF] Bhatt | How to assemble tree machines[END_REF]18] or for hashing problems [START_REF] Alon | Algorithmic construction of sets for k-restrictions[END_REF].

Plan. The paper starts with a survey of known algorithmic approaches and complexity properties (Section 1); new results are also proposed in this section. In the second section (Section 2), we describe a linear programming formulation, and discuss some variants. The computation of solutions for the necklace splitting problem through a pivoting scheme on cubical complexes of [START_REF] Meunier | Discrete splittings of the necklace[END_REF] is described in Section 3. For large instances, local searches can be tried (Section 4). Finally, all these approaches are evaluated and compared in Section 5.

1. What is known from the algorithmic point of view 1.1. The paint shop problem. The paint shop problem is hard.

Theorem 2. [START_REF] Bonsma | Complexity results on restricted instances of a paint shop problem for words[END_REF][START_REF] Meunier | Paint shop, odd cycles and splitting necklace[END_REF] The paint shop problem is APX-hard, even if |C| = 2 and r(u, c) = 1 for all c ∈ C and u ∈ Σ (the binary case). Theorem 3. [START_REF] Epping | Complexity results on a paint shop problem[END_REF] The paint shop problem is NP-hard even if |Σ| = 2.

An exact algorithm is proposed by Epping, Hochstättler and Oertel in [START_REF] Epping | Complexity results on a paint shop problem[END_REF] using a dynamic programming approach. The algorithm runs in O |C|n (|C|-1)|Σ| where n is the length of w, hence it seems unlikely to be applicable in practice.

1.2. The binary paint shop problem.

1.2.1. Polynomial time solvability. For the binary case, which is APX-hard according to Theorem 2 a little more is known. In [START_REF] Bonsma | Complexity results on restricted instances of a paint shop problem for words[END_REF], the problem is translated into the matroid framework : the binary paint shop problem becomes the problem of finding a minimum size circuit containing a special element in a binary matroid. The authors note that finding the minimum number of changes for the binary paint shop problem is polynomial when the binary matroid satisfies the strong maxflow-min-cut property. In [START_REF] Meunier | Paint shop, odd cycles and splitting necklace[END_REF], it is explained how to find a minimum coloring itself in this case. Nevertheless, the strong max-flow-min-cut property for the binary matroid does not translate easily in terms of paint shop. In [START_REF] Meunier | Paint shop, odd cycles and splitting necklace[END_REF], some attempt is made in this direction and for instance, the following corollary is derived : Proposition 1. [START_REF] Meunier | Paint shop, odd cycles and splitting necklace[END_REF] The binary paint shop problem is polynomially solvable if the graph whose vertices are the letters and the edges are the pairs of crossing letters (that is, letters a, b, which occur in the order a, b, a, b) is bipartite.

In the same paper, the following theorem is proved, roughly through an equivalence with the min-uncut problem in 4-regular graphs, leading to "good solutions" for the binary paint shop problem. Theorem 4. [START_REF] Meunier | Paint shop, odd cycles and splitting necklace[END_REF] Let t = |Σ| be the size of the alphabet. A binary paint shop problem has a solution with at most 1/4p + 3/4t color changes, where p is a lower bound of the optimal solution, and both p and the solution can be computed in polynomial time.

It improves the easy bound γ ≤ t which can be obtained with a simple greedy algorithm (it is also a consequence of Theorem 1 for q = 2).

These "good solutions" are the best known today. Whether there is a constant factor approximation algorithm for the binary paint shop problem (asked implicitly in [START_REF] Epping | Complexity results on a paint shop problem[END_REF] and explicitely in [START_REF] Bonsma | Complexity results on restricted instances of a paint shop problem for words[END_REF]) is an open question.

Open question. Is there a constant factor polynomial approximation algorithm for the binary paint shop problem ? 1.2.2. Greedy approaches. The greedy algorithm can be quite efficient in some cases, as the following theorems proved in [START_REF] Amini | Greedy colouring of the binary paintshop problem[END_REF] show. The greedy algorithm for an instance of the binary paint shop problem consists in the coloring of the letters in the given order so as to change the current color only at the second occurrences of letters, and only if necessary. A word w is a subword of a word w = (u 1 , . . . , u n ) if w is a subsequence of w (two consecutive occurrences of a letter in w are not necessarily consecutive in w). Theorem 5. [START_REF] Amini | Greedy colouring of the binary paintshop problem[END_REF] The instances of the binary paint shop problem having neither a subword of the form xyxzzy nor a subword of the form xyyzxz are solved optimally by the greedy algorithm.

Note that the two excluded subwords are the same up to a mirror symmetry. Theorem 6. [START_REF] Amini | Greedy colouring of the binary paintshop problem[END_REF] Let Σ be a finite alphabet of size t. When the instances of the binary paint shop problem are chosen uniformly at random among all instances of fixed size 2t with alphabet Σ, then

E(g) ≤ 2 3 t,
where g is the number of color changes when one applies the greedy algorithm.

Actually, in [START_REF] Andres | Some heuristics for the binary paintshop problem and their expected number of colour changes[END_REF], it is proved that actually we have (conjectured in [START_REF] Amini | Greedy colouring of the binary paintshop problem[END_REF])

Theorem 7.
Let Σ be a finite alphabet and let t be its size. When the instances of the binary paint shop problem are chosen uniformly at random among all instances of fixed size 2t with alphabet Σ, then lim

t→+∞ 1 t E(g) = 1 2
where g is the number of color changes when one applies the greedy algorithm.

In the same paper, another greedy algorithm, the "recursive greedy algorithm", is presented and it is proved that Theorem 8. Let Σ be a finite alphabet and let t be its size. When the instances of the binary paint shop problem are chosen uniformly at random among all instances of fixed size 2t with alphabet Σ, then

2 5 t + 8 15 ≤ E(rg) ≤ 2 5 t + 7 10
where rg is the number of color changes when one applies the recursive greedy algorithm.

1.2.3.

Lower bounds and quality of the optimal solution. In [START_REF] Bonsma | Complexity results on restricted instances of a paint shop problem for words[END_REF], a lower bound -computable in polynomial time through dynamic programming -has been proposed for this problem. The same bound has been used in [START_REF] Amini | Greedy colouring of the binary paintshop problem[END_REF] to prove Theorem 5. This bound is given in Proposition 2. We give a new result, which is a necessary and sufficient condition for this bound to be optimal, and also a new one about instances for which all feasible requirement r have solutions with less than t colors changes. We start also a discussion about the expected value of the optimal value of the binary paint shop problem.

Define for each input w = (u 1 , . . . , u 2t ) of the binary paint shop problem an hypergraph on the set {1, . . . , 2t -1} defined as

I(w) := {{i, i + 1, . . . , j -1} : 1 ≤ i < j ≤ 2t, u i = u j }.
The hyperedges are intervals. In terms of the paintshop problem one can think of the elements of {1, . . . , 2t -1} as possible moments for color change: if moment i (i = 1, . . . , 2t -1) is chosen, that means changing the color right after the occurrence of u i (before the occurrence of u i+1 ). The binary paint shop problem consists in designing a minimum number of color changes so that each hyperedge -each interval -of I(w) contains an odd number of them. Less formally, suppose given a finite set of intervals on the real line, the binary paint shop problem aims to find the minimum number of points such that each interval contains an odd number of them. Any finite set of intervals is not a I(w). Easily, Claim 1. All intervals in I(w) have distinct right endpoints. The same holds for left endpoints.

Let C be a set of subsets of a finite set V . Two subsets A, B ∈ C are said to be crossing if A B and B A and A ∩ B = ∅.

If there are no crossing subsets in C, then C is said to be laminar. The notion of laminar set is a very classical one in combinatorial optimization. In the case of binary paintshop problem, one will need a more specific notion. A set C is evenly laminar if

• it is laminar, and • for all A ∈ C, there is an even number of subsets of C contained in A and distinct from A: the set {B ∈ C : B A} has an even cardinality. The following proposition is proved in [START_REF] Bonsma | Complexity results on restricted instances of a paint shop problem for words[END_REF]. Proposition 2. [START_REF] Bonsma | Complexity results on restricted instances of a paint shop problem for words[END_REF] Let w be an input of the binary paint shop problem and let B ⊆ I(w). If B is evenly laminar, then one has γ(w) ≥ |B|. In other words, the cardinality of any evenly laminar subset of I(w) is a lower bound for the binary paint shop problem.

As already noted, the greedy algorithm allows us to find a solution of the binary paint shop problem with at most t changes. In general, the optimum γ(w) is smaller than t, but Proposition 2 shows that if the input w is such that I(w) is evenly laminar, then we cannot do better than t. In fact, the evenly laminar inputs are precisely the inputs for which we cannot do better than t. Proposition 3. Let w be an input of the binary paint shop problem and let t = |Σ| be the size of the alphabet. Then γ(w) = t if and only if I(w) is evenly laminar.

In terms of the necklace splitting problem, this proposition characterizes completely the case when we cannot do better than the number of cuts given by the necklace splitting theorem (Theorem 1) for two thieves and for a u = 1 for all u ∈ Σ. For more than two thieves or for different values of the a u , such a characterization is not known.

The evenly laminar instances have another interesting property.

Proposition 4. Let w be an input of the binary paint shop problem and let t = |Σ| be the size of the alphabet. For each letter, fix the repartition of the colors you want among the two occurences (r(u, c) = 0, 1 or 2). If I(w) is evenly laminar, then it is always possible to get this repartition with at most t colors changes. t color changes are necessary only when r(u, c) = 1 for each color c and for each letter u ∈ Σ.

This proposition is a consequence of Proposition 3 above and Corollary 3 of the paper "Necklace bisection with one cut less than needed" by Simonyi [START_REF] Simonyi | Necklace bisection with one cut less than needed[END_REF]. This latter states

If we can use at most t -1 cuts and fair splitting is not possible then the thieves still have the following option. Whatever way they specify two disjoint sets D 1 , D 2 of the types of beads with D 1 ∪ D 2 = ∅, it will always be possible to cut the necklace (with t -1 cuts) so that the first thief gets more of those types of beads that are in D 1 and the second gets more of those in D 2 , while the rest is divided equally. It can also be proved directly, as we do it below. The proof shows even that the greedy algorithm finds a solution. Note also that conversely Proposition 3 and Proposition 4 together prove the result by Simonyi for the case when a u = 1 for all u ∈ Σ.

To prove Proposition 3, we will need the following lemma.

Lemma 1. Let w be an input of the binary paint shop problem such that I(w) is evenly laminar. Let T ⊆ {1, . . . , 2t -1} be such that for each I ∈ I(w), the cardinality of T ∩ I is odd. Then for each I ∈ I(w) there is x I ∈ I ∩ T in T such that x I / ∈ K whenever K ∈ I(w) and K I.

Proof. By induction, on the cardinality of I(w). Delete an interval J of I(w) that is maximal for inclusion. Apply induction. We get an x I for each interval I = J such that x I ∈ I ∩ T but x I / ∈ K whenever K ∈ I(w) \ {J} and K I. It is easy to see that, since I(w) is evenly laminar and since |T ∩ I| is odd for all I ∈ I(w) such that I ⊆ J, there is an element of T which is contained in J but in no other interval of I(w).

Proof of Proposition 3. Assume first that I(w) is evenly laminar. A solution with at most |I(w)| changes can be found through the greedy algorithm. Proposition 2 allows us to conclude that it is optimal.

For the other direction, assume now that γ(w) = |I(w)|. We will prove by induction on t, which is |I(w)|, that in this case I(w) is evenly laminar. For t = 1, it is obvious.

Assume t ≥ 2.

Let T be a subset of {1, . . . , 2t -1} such that each interval of I(w) contains an odd number of elements of T and suppose that T is minimum. In other words, T is an optimal solution.

Denote by J the interval that has 2t -1 as right endpoint. Denote by k the new highest right endpoint of an interval in I(w) \ {J} (note that k = 2t -2 or k = 2t -3). By induction, I(w) \ {J} is evenly laminar otherwise the greedy algorithm would extend an optimal solution on I(w) \ {J} to an optimal solution for I(w) that is smaller than T .

Suppose now for a contradiction that there exists an interval I in I(w) such that I and J are crossing . Take T an optimal solution for I(w) \ {J}. According to Lemma 1, there is an x ∈ T such that x is in I but in no other interval K ⊆ I. Deleting x from T and replacing it by one of the endpoints of I (depending on whether x ∈ J or not), we get a solution for I(w) with only |T | < |T | color changes. Contradiction.

Hence, I(w) is laminar, and necessarily every laminar otherwise any solution for I(w) \ {J} would be a solution for I(w).

Proof of Proposition 4. We prove the proposition by induction on the number of letters. It is trivially true if t = 1.

Assume that t > 1. Since I(w) is evenly laminar, there is somewhere in w a sequence of consecutive terms of the form XY Y ZZT , letters X and T being possibly the same, but not necessarily. Let w be the word obtained by deleting Y Y ZZ from w. By induction, we can get any repartition in at most t -2 color changes. Extend greedily the coloring on Y Y ZZ starting from X. We get at most 3 color changes on XY Y ZZT : at most one for the Y 's, at most one for the Z's and at most one for T . If we get 3 color changes, the color of X and the color of T are distinct, which means that we already have one color change between X and T at that place in w . In any case, the increase of color changes is at most 2.

The same inductive scheme allows to prove the statement about the instances for which t color changes are necessary.

In [START_REF] Andres | Some heuristics for the binary paintshop problem and their expected number of colour changes[END_REF], it is asked whether it is possible to find the expected value of the optimal value when the instances are drawn uniformly at random. According to Theorem 8, we have E(γ) ≤ 2 5 t + 7 10 . We were not able to propose an interesting lower bound on E(γ), but we conjecture that E(γ) = o(t). Anyway, with the help of the formulation of Subsection 2.1 and with the help of CPLEX (see Section 5 for more details) we have computed the average value γ of γ for various values of |Σ|. Each value γ in the following array results from the computation of the optimal solution of 10 instances of the binary paint shop problem uniformly taken at random among instances for fixed |Σ|. It might help one of our readers to formulate a conjecture.

Remark. When looking at the lower bound provided by Proposition 2, it is tempting to use it in a branch-and-bound scheme. Partial solutions are given naturally in this context by subsets S ⊆ {1, . . . , 2t -1} and by fixing an element in {0, 1} S : if i ∈ S is fixed to 1, it means that i must be a color change (the color of u i and u i+1 must be different), and if i is fixed to 0, then u i and u i+1 must have the same color. We see that, to get lower bounds for partial solutions, we shall generalize the notion of evenly laminar set. Indeed, when a partial solution is already fixed, the binary paint shop problem becomes: let I be a set of intervals of {1, . . . , 2t -1}; let α : I → {0, 1}; design a minimum number of color changes so that each interval I of I contains a number = α(I) mod 2 of them. We could call this problem the generalized binary paint shop problem.

So, the suitable generalization of evenly laminar is the α-laminar set.

A set C is α-laminar, with α : C → {0, 1}, if
• it is laminar, and

• for all A ∈ C, the set {B ∈ C : B A} has a cardinality = α(I) + 1 mod 2.
It is not too difficult to prove that the cardinality of α-laminar subsets of an input of a generalized binary paint shop problem is a lower bound for this latter problem. To compute the largest α-laminar subset, the dynamic programming approach described in [START_REF] Bonsma | Complexity results on restricted instances of a paint shop problem for words[END_REF] can be straightforwardly adapted. Having a way to encode partial solutions and to compute lower bounds can lead to a branch-and-bound scheme. We have implemented it but it is not at all competitive in comparison with the linear programming approach of the previous section. Nevertheless, this can be used to derive valid inequalities for programs (1) or (2) specialized for the binary paintshop of the type

i∈ J y i ≥ |J |
for some α-laminar subsets J . Violated inequalities of this type can be computed through a similar dynamic programming approach, but we have not tested this possibility of improvement.

1.3. The necklace splitting problem. From a complexity point of view, the question of finding the number of cuts stated in Theorem 1 is an intriguing open question. Problems of similar nature are BROUWER, BORSUK-ULAM, SECOND HAMILTONIAN CIRCUIT, NASH, etc. (see [START_REF] Papadimitriou | On the complexity of the parity argument and other inefficient proofs of existence[END_REF] for their definitions). They are problems for which there is no chance to prove their NP-hardness, unless NP=co-NP [START_REF] Meggido | A note on total functions, existence theorems, and computational complexity[END_REF], since the objects that have to be found always exist. Motivated by the question of computing a Nash equilibrium, Megiddo and Papadimitriou [START_REF] Meggido | A note on total functions, existence theorems, and computational complexity[END_REF] defined the complexity class TFNP, consisting exactly of all search problems in NP for which every instance is guaranteed to have a solution.

A subclass of the TFNP class is the PPAD class for which the existence is proved through the following argument :

In any directed graph with one unbalanced node (node with outdegree different from its indegree), there must be another unbalanced node. This class was defined by Papadimitriou in 1994 [START_REF] Papadimitriou | On the complexity of the parity argument and other inefficient proofs of existence[END_REF] in a paper in which he also shows that there exists PPAD-complete problem, that is a problem in PPAD for which the existence of a polynomial algorithm would imply the existence of a polynomial algorithm for any problem in PPAD. The necklace splitting problem for q = 2 belongs to the class PPAD, since it is a consequence of the Borsuk-Ulam theorem that belongs to PPAD1 . Nevertheless, even if the search problem associated to the Borsuk-Ulam theorem is PPAD-complete, it is not known whether the necklace splitting problem for q = 2 is PPAD-complete. This leads to the following question.

Open question. Is the necklace splitting problem for q = 2 PPAD-complete ? Or, a counterpart (asked for instance in [START_REF]Non-constructive proofs in combinatorics[END_REF]) Open question. Is the necklace splitting problem polynomial ? Even in the case with two thieves (q = 2), and even after some effort, one cannot guarantee a better running time than O(n t-2 ) for t ≥ 3, and O(n) for t = 2 [START_REF] Goldberg | Bisection of circle colorings[END_REF]. Actually, when checking the details of the algorithm, the running time in this paper is Θ(n t-2 ). It means that there is constant α such that the algorithm requires at least αn t-2 evaluations of splittings: roughly speaking, the algorithm computes the value of a function on more or less all discrete points -each of them corresponding to a splitting -of a piecewise linear manifold of dimension t -2 in order to decide the relative position of this manifold (the "winding number" in the terminology of this paper) with respect to a special point (ā still with the notations of the paper); it does it for many manifolds in order to find by a binary search the one containing the special point. This has seemed to be sufficienty prohibitive, in addition with other implementation difficulties (each point on which the function is evaluated requires a Gaussian elimination in O(t 3 ), the algorithm requires degeneracy checkings, ...) and we did not try to implement this method.

The GRAPH ISOMORPHISM problem is an NP problem which is not known to belong to either the P class or the NP-complete class, and for which all attempts to settle its complexity have failed. It is usually suspected to lie somewhere between the P class or the NP-complete class.

We cannot resist to make the supposition that we have with the NECKLACE SPLITTING problem a counterpart in the PPAD context. The NECKLACE SPLITTING problem (even for q = 2) is maybe somewhere between the P class and the PPAD-complete class.

An algorithmic proof of the case with two thieves exists [START_REF] Meunier | Discrete splittings of the necklace[END_REF]. It is path-following method similar to the one used by Scarf [START_REF] Scarf | The approximation of fixed points of a continuous mapping[END_REF] to prove Sperner's lemma. But, contrary to this latter proof, the path travels in a cubical complex, instead of a simplicial complex, and the labels are vertices of a cube, instead of being integers (see Section 3). Whether there is similar proof for more than two thieves remains open. This question is probably difficult since, although there are several proofs of this kind for the Borsuk-Ulam theorem, which hides behind the necklace splitting theorem for two thieves, there is no proof at all of this kind for the more general Dold theorem (see for instance the work by de Longueville and Zivaljevic [START_REF] De Longueville | The Borsuk-Ulam-property, Tucker-property and constructive proofs in combinatorics[END_REF]), which hides behind the necklace splitting theorem for an arbitrary number of thieves.

Open question. Is there a path-following proof of the necklace splitting theorem for an arbitrary number of thieves ? 2. Linear programming 2.1. A first formulation. Consider an instance (w, r) of the paint shop problem with alphabet Σ and color set C. Assume w = (u 1 , . . . , u n ) to be of length n. To ease the discussion, we introduce the notation P (u) which indicates for u ∈ Σ the positions of the letter u in w.

Any solution c = (c 1 , . . . , c n ) can be encoded through variables x i,c for all i ∈ {1, . . . , n} and c ∈ C where

x i,c = 1 if c i = c 0 if not. These variables must satisfy i∈P (u)
x i,c = r(u, c) for all c ∈ C and u ∈ Σ (the requirement is satisfied) and c∈C x i,c = 1 for all i ∈ {1, . . . , n} (each occurrence of a letter receives exactly one color).

Adding a variable y i encoding whether there is color change between u i and u i+1 , we can formulate the binary paint shop problem as an integer linear program. Define for all i ∈ {1, . . . , n -1}

y i = 1 if x i,c = x i+1,c for some c ∈ C 0 if not.
The formulation is then

(1) min n-1 i=1 y i s.t. i∈P (u) x i,c = r(u, c) for all c ∈ C and u ∈ Σ (i) c∈C x i,c = 1 for all i ∈ {1, . . . , n} (ii)
y i ≥ x i,c -x i+1,c
for all c ∈ C and i ∈ {1, . . . , n -1} (iii)

y i ≥ x i+1,c -x i,c
for all c ∈ C and i ∈ {1, . . . , n -1} (iv)

x i,c ∈ {0, 1} for all c ∈ C and i ∈ {1, . . . , n} (v)
y i ∈ {0, 1} for all i ∈ {1, . . . , n -1}. (vi)
To solve the necklace splitting problem, we can use this formulation in a branch-and-bound and stop as soon as a solution with at most (q -1)t color changes is found (as always in this paper q = |C| and t = |Σ|). Moreover, we can use (q -1)t + 1 as an upper bound in order to cut a subtree in the branch-and-bound tree even before having found a feasible solution (consequence of Theorem 1).

In the special case of the necklace splitting problem, we face a problem with high symmetries, similar of the ones of the coloring of graphs or for the bin-packing problem. The following solution is classical in such a situation. These variables must satisfy i∈P (u) and i≥j z j,i = a u z j,j for all u ∈ Σ and all j ∈ {1, . . . , n} (the requirement is satisfied) and j≤i z j,i = 1 for all i ∈ {1, . . . , n}

(each occurrence of a letter receives exactly one color).

An alternative formulation to (1) by an integer linear program for the necklace splitting problem is the following one.

(2)

min n-1 i=1 y i s.t.
i∈P (u) and i≥j z j,i = a u z j,j for all u ∈ Σ and all j ∈ {1, . . . , n} j≤i z j,i = 1 for all i ∈ {1, . . . , n}

y i ≥ z j,i+1 -z j,i for all 1 ≤ j ≤ i + 1 ≤ n y i ≥ z j,i -z j,i+1 for all 1 ≤ j ≤ i + 1 ≤ n z j,i ∈ {0, 1} for 1 ≤ j ≤ i ≤ n y i ∈ {0, 1} for all i ∈ {1, . . . , n -1}.
z j,i is equal to 1 if u i gets the same color as u j and if u j is the first occurrence of a letter getting this color. It is clear that any solution of the necklace splitting problem can be encoded in such a way. More interesting, this formulation has not the drawback of the formulation (1): two solutions identical up to a permutation of C lead to the same solution of (2).

2.3.

Another formulation when there are only two colors. If there are only two colors, another formulation is possible, namely the following one, which uses less variables than the preceding ones.

Fix one of the color c ∈ C. The interpretation of the variables is now straightforward.

(

) min n-1 i=1 y i s.t. i∈P 3
x i = r(u, c) for all u ∈ Σ (i)

y i ≥ x i -x i+1
for all i ∈ {1, . . . , n -1} (ii)

y i ≥ x i+1 -x i for all i ∈ {1, . . . , n -1} (iii) x i ∈ {0, 1} for all i ∈ {1, . . . , n} (iv)
y i ∈ {0, 1} for all i ∈ {1, . . . , n -1}. (v)
2.4. Lagrangian relaxation. The first formulation (1) suits Lagrangian relaxation. We haven't implemented it. If we relax constraints (iii) and (iv), we get the following Lagrangian subproblem

u∈Σ l u (µ, µ ) + min y∈{0,1} n n-1 i=1 1 + c∈C µ i,c + µ i,c y i ,
where y = (y 1 , . . . , y n ), µ = ((µ i,c )) i∈{1,...,n},c∈C and µ = ((µ i,c )) i∈{1,...,n},c∈C and l u (µ, µ ) is the value of min i∈P (u),c∈C

(µ c,i-1 + µ c,i-1 -µ c,i -µ c,i )x c,i s.t. i∈P (u)
x i,c = r(u, c) for all c ∈ C and u ∈ Σ c∈C x i,c = 1 for all i ∈ P (u)

x i,c ∈ {0, 1} for all c ∈ C and i ∈ P (u)
, which is the value of an optimal b-matching in a bipartite graph, computable in strongly polynomial time.

Since for any values of µ and µ , the Lagrangian subproblem has integer solutions, it has the so-called integer property, and the Lagrangian relaxation does not provide a better bound than the linear relaxation. Anyway, such a relaxation is interesting here since solving the Lagrangian multiplier problem is probably more efficient than solving the linear programming relaxation directly.

Necklace splitting through cubical complexes

We come now back to the necklace splitting problem. The problem is the following.

Necklace splitting problem for two thieves

INPUT: A finite alphabet Σ of size t whose elements are called letters, a word w = (u 1 , . . . , u n ) ∈ Σ * in which each letter u is present an even number of times.

TASK: Find a coloring c = (c 1 , . . . , c n ) ∈ {1, 2} n such that for each u ∈ Σ, we have |{i ∈ {1, . . . , n} : u i = u and c i = 1}| = |{i ∈ {1, . . . , n} : u i = u and c i = 2}|, and such that the number of color changes is less than or equal to t.

Recall that more poetically the letters are the types of beads, the word w is the sequence of beads on the chain, and that the two colors correspond to the two thieves: for instance, c i = 1 indicates that the ith bead goes to the thief number 1.

The only known algorithmic proof deals with the case with q = 2 (two thieves) and is given in [START_REF] Meunier | Discrete splittings of the necklace[END_REF]. We describe in the sequel the algorithm but give first a short overview. The existence of a fair splitting is a consequence of a theorem by Ky Fan, which asserts the existence of a cube with certain labels (a "full" t-cube) in a cubical complex whose vertices get labels satisfying particular conditions (somewhat in the spirit of Sperner's lemma). We first explain this theorem (Subsection 3.1). Then we describe the algorithm finding the full t-cube whose existence is asserted by Ky Fan's theorem (Subsection 3.2). The correctness of the algorithm proves actually Ky Fan's theorem. Then, we explain how to encode the necklace splitting problem in the framework of cubical complexes, labels and Ky Fan's theorem (Subsection 3.3), in order to get an algorithm finding a fair splitting, which appears to be in this context a full t-cube. Finally, we give some details on how to exploit the particular features of the necklace to make quickly the checkings and computations required by the algorithm (Subsection 3.4). A cubical complex is a collection K of cubes embedded in an Euclidean space such that • if τ ∈ K and if σ is a face of τ then σ ∈ K and • if σ and σ are in K, then σ ∩ σ is a face of both σ and σ . V (K) is the set of vertices of the cubical complex K. A cubical complex is said to be pure if all maximal cubes with respect to inclusion have same dimension.

A m-dimensional cubical pseudo-manifold K is a pure m-dimensional cubical complex in which each (d-1)-dimensional cube is contained in at most two m-dimensional cubes. The boundary of K, denoted by ∂K, is the set of all (m -1)-cubes σ such that σ belongs to exactly one m-dimensional cube of K.

Denote by C m the cubical complex which is the union of the cube m := [-1, 1] m and all its faces. ∂C m , its boundary, is a (m -1)-dimensional cubical pseudo-manifold without boundary.

Let k ≥ 0 be an integer. Given k distinct integers i 1 , i 2 , . . . , i k , each of them in {1, 2, . . . , m}, and k numbers 1 , 2 , . . . , k , each of them belonging to {-1, +1}, we denote

F i 1 i 2 . . . i k 1 2 . . . k := {(x 1 , x 2 , . . . , x m ) ∈ {-1, +1, } m : x i j = j for j = 1, 2, . . . , k},
which is the vertices of an (mk)-face of m . For k = 0, we get all vertices of m . Let M be the cubical pseudo-manifold without boundary obtained by subdividing ∂C t+1 by means of the hyperplanes x i = j n where i ∈ {1, 2, . . . , t + 1} and j ∈ {-n + 1, -n + 2, . . . , -1, 0, 1, . . . , n -

º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º ººººººººººººººººººººººººººººººººººººººººº º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º ººººººººººººººººººººººººººººººººººººººººººººººº º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º ººººººººººººººººººººººººººººººººººººººººººººº º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º ººººººººººººººººººººººººººººººººººººººººººº º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º ººººººººººººººººººººººººººººººººººººººººº º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º º s s © c u +H 0 -H 0 +H 1 -H 1 +H 2 -H 2 E T © x 1 x 2 x 3 Figure 1. An illustration of M for n = 2 t = 2. 2, n -1}. Let λ : V (M) → V (C m )
be a labelling of its vertices with vertices of C m such that the labels of two adjacent vertices are either identical or neighbors on the 1-skeleton of C m . A d-cube of K (with 0 ≤ d ≤ m) is said to be full if the image of its vertices under λ is of the form

F d + 1 d + 2 . . . m 1 2
. . . m-d .

We have then the following theorem by Ky Fan (in a specialized version of Theorem 5 in [START_REF] Fan | Combinatorial properties of certain simplicial and cubical vertex maps[END_REF]).

Theorem 9. If λ is antipodal (i.e. such that λ(-v) = -λ(v) for all vertices v ∈ M), there exits always at least on full t-cube.

We explain in Subsection 3.3 how the necklace splitting problem can be embedded in this framework. The vertices of M will encode the different splittings. The labelling λ of a vertex will indicate the thief advantaged for each type of bead, for the splitting encoded by the vertex. The existence of a full t-cube will imply the existence of a fair splitting.

3.2.

An algorithm finding a full t-cube. We endow M with hemispheres. These hemispheres are denoted +H 0 , -H 0 , +H 1 , -H 1 , . . ., +H t , -H t . +H i (resp. -H i ) is the set of points (x 1 , x 2 , . . . , x t+1 ) of ∂ t+1 such that x i+1 ≥ 0 (resp. x i+1 ≤ 0), and such that, if i ≤ t -1, then x j = 0 for j > i + 1. The sign of the hemisphere +H i (resp. -H i ) is +1 (resp. -1) and we denote it by sign(+H i ) = +1 and sign(-H i ) = -1.

On Figure 1, the hemispheres of M obtained by subdividing ∂C 3 for n = 2 are highlighted. The carrier hemisphere CarrHem(σ) of a cube σ is the hemisphere of smallest possible dimension containing σ. Now, assume that we have a labelling λ of for some m ≥ t and assume moreover that λ is antipodal, that is that -λ(v) = λ(-v) for any vertex v ∈ V (M). We define the notion of sign for a full d-cube σ with d < m: let

F d + 1 d + 2 . . . m 1 2 . . . m-d
be the image of its vertices. 1 is then its sign, denoted by sign(σ).

In [START_REF] Meunier | Discrete splittings of the necklace[END_REF], the following method for finding a full t-cube is described. Consider the following graph G = (N, E). The nodes of G are the cubes τ in one of these three situations. It can be checked that all nodes have degree 1, 2 or 4. A cube has degree 1 only if its dimension is 0 (it is either the 0-cube (1, 0, . . . , 0) or (-1, 0, . . . , 0), no other 0-cube being contained in +H 0 or -H 0 ) or if it is a full t-cube. It can also be proved that in a connected component of G, there is at most one 0-cube node. If a cube τ is of degree 4, it can be proved that we are in Situation [START_REF]Non-constructive proofs in combinatorics[END_REF] and that it has exactly 4 full facets, two pairs of opposite facets. We make then two copies of τ , each of them linked to one of these pairs. G becomes a collection of cycles and paths. Following the path starting at (1, 0, . . . , 0), we eventually arrive at a full t-cube.

We get Algorithm 1. It is a path-following algorithm, similar to Scarf's algorithm computing fixed point for continuous mapping [START_REF] Scarf | The approximation of fixed points of a continuous mapping[END_REF]. In the pseudocode below, τ is the current cube and σ the current cube of the previous iteration. Note that σ and τ are such that one is always the facet of the other and that the maximal one has always the dimension of its carrier hemisphere.

Since it is very far from the exhaustive enumeration of the t-cubes of M, we may hope that a similar phenomenon that for Scarf's algorithm happens, that is that it provides a fast algorithm to find full t-cubes. The experimentation is made in Section 5.

3.3.

Application to the necklace. The necklace is identified with the interval ]0, n[⊂ R. The beads are numbered with the integers 1, 2, . . . , n, from left to right. The kth bead occupies uniformly the interval ]k -1, k[.

For S ⊆]0, n[, we denote by φ i (S) the quantity of beads of type i in positions included in S. More precisely, we denote by 1 i (u) the mapping which indicates if there is a bead of type i at point u of ]0, n[:

B i (u) =    2 if u
th bead is of type i and if it is the first bead of this type. 1 if the u th bead is of type i and if it is not the first bead of this type. 0 if the u th bead is not of type i.

We have then

φ i (S) := S B i (u)du.
The definition of B i may be surprising since the first bead of each type is counted twice; this is only a trick to avoid tie between the two thieves.

Let x := (x 1 , x 2 , . . . , x t+1 ) be a vertex of M. We order the x i in the increasing order of their absolute value. When |x i | = |x i |, we put x i before x i if i < i . This gives a permutation π such that Algorithm 1 The algorithm finding a full t-cube whose existence is claimed by Ky Fan's theorem.

τ ← (1, 0, . . . , 0) let σ be such that τ is a facet of σ and CarrHem(σ) = sign(τ )H 1 // σ is an edge in ±H 1 while τ is not full or dim τ = t do if τ is full and dim(CarrHem(τ )) = dim τ + 1 then // Situation (1) let σ ∈ CarrHem(τ ) be such that τ is a facet of σ and σ = σ else if σ is full and σ is facet of τ then // Situation (2) let σ be the facet of τ such that σ ∩ σ = ∅ // σ and σ are opposite else if τ is full and dim(CarrHem(τ )) = dim τ then // Situation (3) d ← dim τ if σ is a facet of τ then let σ be such that τ is a facet of σ and CarrHem(σ ) = sign(τ )H d+1 else let σ be such that σ is full, is a facet of τ and sign(σ ) = sign(CarrHem(τ ))

end if end if σ ← τ τ ← σ end while return τ |x π(1) | ≤ |x π(2) | ≤ . . . ≤ |x π(t+1) | = 1.
It encodes a cut as follows: the necklace is cut at points n|x i |. Since among the |x i |, at most t are different from 1 (we are in M, which is embedded in ∂C t+1 ), we get a splitting in at most t cuts, as required. From left to right, we rank the subnecklaces. Given a subnecklace, we look at the smallest k such that n|x k | is greater than or equal to the coordinate of any point of the subnecklace (i.e the first cut at the right of the subnecklace). The sign of x k indicates the thief who gets this subnecklace.

Then, we define λ = (λ 1 , λ 2 , . . . , λ t ) : V (M) → {-1, +1} t = V (C t ) as follows: we cut the necklace at points n|x i |. By convention, x π(0) := 0; we define This formula can be understood as follows: λ i (x) equals +1 (resp. -1) if the first thief gets strictly more (resp. strictly less) beads of type i than the second one, when we cut the necklace at points n|x j |, and assigning the subnecklaces to the thieves according to the rule described in the previous paragraph. Let us give an example. Figure 2 shows a necklace with n = 16, t = 3, and 4 cuts. These 4 cuts are compatible for instance with the vertex (x 1 , x 2 , x 3 , x 4 ) where There are 4 subnecklaces: the first one goes to the thief + since the minimal index k such that 16|x k | is greater than all points of this subnecklace is 1; the second one goes also to +; the third and the fourth ones go to -. The image of this vertex through λ is (+1, -1, -1) where the first component corresponds to the blue beads (color 1), the second one to the red beads (color 2), and the third one to the green beads (color 3).

λ i (x) := +1 if t j=0 sign(x (j) )φ i n|x π(j) |, n|x π(j+1) | > 0 -1 if not, for i = 1, 2, . . . , t,
x 1 = 6 16 , x 2 = - 3 16 , x 3 = -1, x 4 = - 12 16 .
It can be checked that λ maps adjacent vertices to the same vertex or to adjacent vertices, and that it is antipodal. We are thus in the framework of Subsection 3.1. A full d-cube σ is obtained by d cuts sliding on d beads and since it is full, each of these cuts "slides" along distinct beads of distinct types, from type 1 to type d. More precisely, take the splitting encoded by the vertex of σ with the highest (resp. lowest) coordinates : the thief + (resp. -) is advantaged for all the first d types of beads.

A full t-cube having necessarily a vertex encoding a fair splitting (changing the assignment of the type i bead change the thied advantaged for type i), Algorithm 1 provides an algorithm solving the necklace splitting problem. Nevertheless, we have a priori no guarantee on the time needed to solve a real problem. In Section 5, this algorithm is experimented.

3.4. Some details of implementation.

3.4.1.

Cubes. A cube σ of ∂M is encoded through a couple (LowerPoint,UpperPoint) where LowerPoint (resp. UpperPoint) is the coordinate of the vertex having the lowest (resp. highest) values for each coordinate. Note that there are no ambiguity and that the dimension of σ is the number of coordinates that differ between LowerPoint and UpperPoint.

Full cubes.

To check if a d-cube is full, it is enough to check if the first thief is advantaged for each of the first d types by the splitting encoded by UpperPoint and if the second thief is advantaged for each of the first d types by the splitting encoded by LowerPoint.

3.4.3.

Sign. The sign of a d-cube is given by the thief advantaged for type d + 1.

3.4.4. Carrier hemisphere. The carrier hemisphere of a vertex is given by the rank and the sign of its last nonzero coordinate.

Local searches

We have developed two local search models, one for the paintshop problem, and one for the necklace splitting. 4.1. Paintshop moves. For the general paint shop problem, the objective to minimize is the number of color changes. The initial configuration is an admissible coloring (c 1 , . . . , c n ) ∈ C n such that it satisfies the coloring constraints, i.e. |{i ∈ {1, . . . , n} : u i = u and c i = c}| = r(u, c) for all u and c. The local search algorithm performs swap moves in the sequence between two positions i 1 < i 2 such that

• u i 1 = u i 2 and • c i 1 = c i 2 .
In order to intensify the search, i 1 is chosen just before or after a color change. We have used the same moves for the binary paintshop problem. 4.2. Necklace splitting moves. The local search designed for the paint shop version can be applied to the necklace version -the search must be stopped as soon as the number of cuts becomes less than or equal to (q -1)t. It appears that in the special case of the necklace, we can design another local search.

For the necklace splitting problem, the objective is to find a fair division between q thieves, with the number of cuts N = (q -1)t given by the theorem 1. Remark that this number of cuts is not always the minimum.

The model is made of 2 * N variables, i.e for each cut we have 2 variables, the place (in {1, . . . , n}) of the cut and the thief who receives the part just after the cut. For breaking symmetries, we give the first part to the first thief. The initial configuration is made of N random cuts and each part is randomly assigned to a thief. The objective function to minimize is the sum of the deviations for each type and thief couple between the current division and a fair one. The algorithm stops when a fair division is found, or when a timeout is reached.

The local search algorithm performs 2 types of moves :

• Displacement of a cut : a cut is chosen, and is displaced to a new place which is distant of less than D places from the current place. • Change of thief : a part is chosen and given to another thief, distinct from the thieves that own the next left and right parts, in order to keep constant the number of cuts. We wanted to perform small moves, that can be efficiently incrementally evaluated. We limited therefore each cut displacement by a maximum distance of D = 20 places to the left or to the right of the current place. We experimentally fixed the ratio between the 2 types of moves (displacements and changes of thief) to 4, i.e we try with a probability of 0.8 a displacement move and a probability of 0.2 a change of thief.

We have implemented a simplified variant for 2 thieves, where the only variables are the N cuts places and a single type of moves, the cut displacements (also limited with a maximum distance equal to 20). 4.3. Metaheuristic. For both problems, the metaheuristic used for escaping local minima is ID-Walk [START_REF] Neveu | ID-Walk : A Candidate List Strategy with a Simple Diversification Device[END_REF]. It is a very simple metaheuristic, based on the size of the explored neighborhood. Like all local search algorithms, the algorithm changes a current configuration by performing at each step a local transformation, i.e. a local move as described above. At the end of the walk, it returns the best configuration found during the walk.

The pseudo-code described in Figure 2 shows in details the main step of the algorithm : how the neighbor that will become the next current configuration is selected. IDWalkStep randomly performs an incomplete exploration of the neighborhood of the current configuration. It selects the first improving or equal neighbor found if any, and in case all MaxNeighbors visited neighbors degrade the objective function, it selects the less degrading one. The parameter MaxNeighbors of the algorithm is the size of the randomly explored neighborhood. This parameter controls the behavior of the algorithm. If the MaxNeighbors potentially explored neighbors represent an important part of the neighborhood, the algorithm will perform more intensification than if MaxNeighbors is small w.r.t. the size of the neighborhood.

In addition, the diversification performed by the algorithm also mainly depends on this parameter. If Maxneighbors is small, it is not likely to find a configuration better than or equal to the current one among these explored neighbors. The degradation of the objective obtained then by choosing the less degrading explored neighbor will be greater than if a larger number of neighbors would be tested. With a small part of the neighborhood being explored, it is also not likely that the algorithm returns in the following moves to an already visited configuration and the presence of a tabu list device becomes unnecessary.

For each instance to be solved, this MaxNeighbors parameter is automatically tuned. We alternate tuning and running phases. During the tuning phases, the algorithm is run on small walks with different parameter values. The parameter value that yields the best result is selected and used during the next running phase.

Computational results

The algorithms described in the previous sections were implemented in C++. The implementations were tested on a computer with a Intel Core 2 Duo CPU 2.26 GHz processor, with 1.96 GB RAM, using the GNU-C++ compiler (gcc 3.4.5). For the linear programming resolution, we have used CPLEX 12. n the length of the word w, t the cardinality of Σ and q the number of colors All instances were generated at random, since no benchmark is available (as noted in the Introduction, this problem had not been studied from a practical point of view). They can be downloaded from http://cermics.enpc.fr/∼meuniefr/home.html/PaintshopNecklace Instances 5.1. General paint shop problem. The approaches tested for the (general) paint shop problem are linear programming (Subsection 2.1) and the local search (Subsection 4.1). We have generated 15 instances, as follows. The parameters n, q, t are fixed. The ith letter is an element drawn uniformly at random from Σ, independently from the other letters. Each time a letter is drawn, a color is also drawn, therefore at the end we have for each letter a pool of colors to be attributed to its occurrences.

For the local search method, as it is a stochastic incomplete method depending on the initial configuration, we performed 2 sequences of 10 tries per instance, each try being limited to 1 min CPU time for the first sequence, and to 5 min CPU time for the second sequence.

We report the best and the median solutions among these 10 tries.

The linear programming was experimented with a time limit equal to 30 min CPU time.

The results are given in Table 1.

Linear programming is able to solve optimally the general paint shop problem when the number of types and the number of colors are quite small (≤ 5). As soon as these parameters grow, the gap between the upper and lower bounds provided by the linear program becomes large. with the optima. The feasible solutions found by the local search are anyway largely better than the ones obtained by the linear program, and in a laps of time really smaller.

5.2.

Binary paint shop problem. The approaches tested are the three formulations of linear programming, (1), 2) and (3), as well as local search.

We have generated instances, where a sequence of n letters with 2 occurrences of each letter is randomly generated. The objective is to color this sequence with 2 colors, with a minimum of color changes.

The results are given in Table 2. Note that LP (2) behaves very badly -the '-' means that CPLEX terminates because of an 'out of memory' error. The reason is probably that it has too much variables.

The binary paintshop problem also proves the superiority of the local search to find good feasible solutions, and again more quickly than linear programming. We can anyway note that the linear programming approach (LP (1) and ( 3)) is efficient up to n 250 and the instances of this size are solved to optimality in less than 30 minutes. The efficiency of the linear programming approach was already noted in Subsection 1.2, in which it was tested on instances of size n ≤ 240. 5.3. Necklace splitting. When there are strictly more than two thieves, we have tested the two formulations (1) and (3) of the linear programming and the two local search methods LSn and LSp.

(2) was not able to solve any instance, whence we have omitted its results in the table. When there are exactly two thieves, we have added the path-following method of Section 3.

The instances were generated uniformly at random among the instances with the parameters n, q and t fixed, and with the same number of beads of each type. We have generated 15 "small" and 15 "large" instances with q ≥ 3 and also 15 "small" and 25 "large" instances with q = 2.

For the linear programming approaches, we have initialized the branch-and-bound with an upper bound (q -1)t + 0.1 since by the splitting necklace theorem (Theorem 1), we know that there is a solution strictly better than this value, and we stop the branch-and-bound when the first integer solution is found (in CPLEX, there is a so-called "MIP integer solution limit").

For the LSn local search method, as described in previous section, we use a model where the number of cuts is fixed to (q -1)t cuts. This method stops with success when a fair division is found. The LSp local search method works with fair divisions and tries to lower the number of cuts. It stops with success when a solution with (q -1)t or less cuts is found.

The results are given in Tables 3,4, 5 and 6. For the local search methods, we performed 10 tries per instance, each try being limited to 1 min . CPU time. We report for each instance, the number of successes and the average time for a successful try. 3. Results for the necklace splitting problem with q ≥ 3 -small instances.

LSn

Instance n q t Success Time (in s) 34.9 Table 4. Results for the necklace splitting problem with q ≥ 3 -large instances.

When there are 3 or more thieves (see Tables 3 and4) the local search -especially LSn -is efficient, and the linear programming approach hardly finds a solution for relative small instances (n 400). For large instances (Table 4), linear programming and LSp were both unable to solve any of them in the time limits.

We can remark -see Table 6 -that for the problem with 2 thieves and 3 types of beads, the cubical path-following method is more efficient than the local search, in the sense that it is a complete method that always finds a solution in a time comparable with the time of a successful execution of the local search method. This latter method sometimes fails, depending on the initial 5. Results for the necklace splitting problem with q = 2 -small instances. configuration. On the contrary, when the number of types grows, the cubical path-following method becomes less efficient than the local search method.

We can also note -see Table 5 -that the linear programming approach and LSp work better when the number of cuts (q -1)t ensured by the necklace theorem becomes high. This can be explained by the strategy followed by these approaches, which consists in decreasing the number of cuts until reaching the target number.

Conclusion.

The two local searches -when applied to the problems they have been designed for -are really efficient. Exact approaches exist when the size of the word (the total number of beads on the necklace) is small (linear programming) for both the necklace problem and the paintshop problem, and for the necklace problem with two thieves and not too many types, say ≤ 5 (the path-following method). It is worth noting that the path-following method is very efficient for the splitting of the necklace between two thieves, when there are only 3 types of beads, the solution being computed in few seconds even for 90 000 beads.

Some concluding remarks

On the theoretical hand, many questions remain open both for the paintshop and the necklace versions -see Section 1. These questions come within complexity theory, discrete probability, combinatorial optimization and combinatorial topology. So many areas meet rarely in the same problem. On the practical hand, we know how to solve the paintshop-necklace problem for high instances with local searches, and we propose approaches through linear programming and a pathfollowing method. An efficient exact method for the paintshop problem remains to be designed, as well for the necklace problem for three thieves and more.

Finally, let us emphasize that the path following method appears to be quite efficient. Actually, it was designed to solve the problem of finding a full t-cube (see Section 3), which is more general than the splitting of the necklace. The existence of a full t-cube is very close of Tucker's lemma, the combinatorial counterpart of the Borsuk-Ulam theorem. One may ask whether this method would be efficient for the computation of the zeroes of antipodal map f : S d → R d , whose existence Cubical LSn path-following Instance n q t Time (in s) Success Time (in s) N5000 2 3 1 30000 2 3 1.1 7 6.2 N5000 2 3 2 30000 2 3 4.8 7 1.9 N5000 2 3 3 30000 2 3 1.2 9 2.8 N5000 2 3 4 30000 2 3 2.7 7 2.5 N5000 2 3 5 30000 2 3 2. 6. Results for the necklace splitting problem with q = 2 -large instances. is ensured by the Borsuk-Ulam theorem. However, a step is missing, namely the existence of a "cubical approximation theorem" which is a still open question: any continuous mapping can be approximated by a simplicial map; it is not known if a similar statement holds for a cubical map (see for instance Property 6.1 in [START_REF] Babson | A homotopy theory for graphs[END_REF]). Since cubical complexes are often more tractable than simplicial complexes a positive answer to this latter question would provide a promising approach to the computation of zeroes of antipodal maps.

  γ 4.1 7.2 13 23.4 26.1 28.2 31.1 35.4

2. 2 .

 2 Killing symmetries. Let us consider the necklace splitting problem. Any solution can be encoded (up to symmetry) through 1 ≤ j ≤ i ≤ n z j,i = 1 if c j = c i and c k = c j for all k < j 0 if not.

3. 1 .

 1 Cubical complexes and Ky Fan's theorem. Let C be a cube, ∂C the boundary of C, and V (C) the set of vertices of C. Two facets of a m-cube are said to be adjacent if their intersection is a (m -2)-cube. For a given facet σ of C, there is only one non-adjacent facet. Two non-adjacent facets are opposite.

Situation ( 1 )

 1 : τ is full, dim (CarrHem(τ )) = dim τ + 1 and sign(CarrHem(τ )) = sign(τ ) Situation (2): τ has a full facet, dim (CarrHem(τ )) = dim τ and sign(CarrHem(τ )) = sign(τ ) Situation (3): τ is full and dim (CarrHem(τ )) = dim τ Two nodes τ and τ are adjacent in G if all the following hold: (a) τ is a facet of τ , (b) τ is full, (c) dim τ = dim (CarrHem(τ )), and (d) sign (CarrHem(τ )) = sign(τ ).

  where (j) is the smallest integer k such that |x k | ≥ |x π(j+1) |, and with the convention sign(0) := 0.

Figure 2 .

 2 Figure 2. The cuts associated to the vertex x 1 = 6 16 , x 2 = -3 16 , x 3 = -1, x 4 = -12 16 .

LP

  Algorithm 2 ID WalkStep (x : current configuration, best : best configuration, MaxNeighbors: maximum number of neighbors to be visited)

	Candidate ← 1 RejectedCandidates ← ∅ Accepted? ← false while (Candidate ≤ MaxNeighbors) and (not Accepted?) do Select randomly a neighbor x of x
	if cost(x ) ≤ cost(x) then Accepted? ← true else
	RejectedCandidates ← RejectedCandidates ∪ {x } end if
	Candidate ← Candidate +1 end while
	if Accepted? then
	x ← x else
	x ← the configuration in RejectedCandidates with the smallest cost end if
	if cost(x) < cost(best) then
	best ← x end if

Table 1 .

 1 2. The local search uses the version of IDWalk implemented in the INCOP [19] C++ local search library. Results for the general paint shop problem. LSp local search designed for the paintshop version (Subsection 4.1). LSn local search designed for the necklace version (Subsection 4.2).

	The following notations are used.
	LP linear programming.

Table 2 .

 2 The local search behaves well, even if we were not able to give a reasonable lower bound to estimate the gap LP (1) 30 min LP (2) 30 min LP (3) 30 min LSp 60 s Results for the binary paint shop problem.

	LSp 300 s

In[START_REF] Papadimitriou | On the complexity of the parity argument and other inefficient proofs of existence[END_REF], the necklace splitting problem is stated to belong to PPAD for any q but it seems unlikely to be true since in the general case, the necklace splitting theorem is a consequence of the more general Dold theorem, which is in PPA-q.


Alain Le Bot

Statistical Energy Analysis and the second principle of thermodynamics

Statistical Energy Analysis is a statistical method in vibroacoustics entirely based on the application of energy balance that is the first principle of thermodynamics. In this study, the definition of vibrational entropy is introduced for sub-systems containing energy and modes. The rate of entropy production at interfaces between sub-systems is also derived. Finally, in steady-state condition, an entropy equilibrium is reached. The meaning of entropy and some implications of this entropy balance are also discussed.

Introduction

Statistical Energy Analysis [START_REF] Lyon | Theory and Application of Statistical Energy Analysis[END_REF][START_REF] Lyon | Fluctuation theory and (very) early statistical energy analysis[END_REF] is born from the application of statistical physics concepts to vibroacoustical systems. The idea is quite simple. When the number of modes of vibroacoustical systems is so large that the solving of governing equations becomes unpracticable, it is preferable to give up a deterministic description of the system and to adopt statistical methods. This standpoint is reasonable. It has been followed in several other fields in physics, kinetic theory of gases instead of point mechanics, statistical theory of turbulence instead of Navier-Stoke's equation, statistical behaviour of granular material and some others. In all these cases, the number of entities is very large so that a complete description of all of them would lead to a set of equations untractable in practice and whose solution would be very sensitive to errors of modelling. In addition, the amount of produced information would be huge, the major part being useless.

The application of concepts and methods of statistical physics to the audio frequency range instead of thermal vibration raises some difficulties. First of all, the number of entities in vibroacoustics (the modes) is not so large than in thermics Alain Le Bot Laboratoire de tribologie et dynamique des systèmes CNRS, Ecole centrale de Lyon, 36, av. Guy de Collongue 69134 Ecully, FRANCE e-mail: alain.le-bot@ec-lyon.fr 1 (atoms or molecules). Statistical methods applied to poor populations are fragile. This explains why results of SEA are sometimes disappointing. SEA is too oftently used outside its validity domain. Secondly, small populations lead to large fluctuations. While it is almost impossible (or at least very difficult) to observe fluctuations in thermodynamical systems, large fluctuations are common in SEA and it is sometimes necessary to deal with large population of similar systems, the so-called Gibb's ensemble, to increase the quality of SEA results. Finally, the equipartition of energy among modes is sometimes violated. Poor population and low modal overlap are conditions favourable to a deviation from the equilibrium state. This is why it is so urgent to extend SEA to non-equilibrium states [START_REF] Bot | Energy exchange in uncorrelated ray fields of vibroacoustics[END_REF][START_REF] Bot | Derivation of statistical energy analysis from radiative exchanges[END_REF][START_REF] Maxit | Extension of sea model to subsystems with non-uniform modal energy distribution[END_REF] by relaxing the diffuse field assumption following the example of non-equilibrium thermodynamics.

Up to now, SEA is entirely based on the application of energy balance that is the first principle of thermodynamics. But nothing is told on entropy in SEA [START_REF] Carcaterra | An entropy approach to statistical energy analysis[END_REF][START_REF] Carcaterra | An entropy formulation for the analysis of energy flow between mechanical resonators[END_REF]. Conceptually, both quantities energy and entropy are necessary for a complete derivation of statistical physics and therefore SEA. Energy is indeed necessary to describe the state of the system. Entropy is necessary to measure the loss of information induced by the renouncement to a full description of the system. In this regard, different levels of approximations would lead to different values of entropy. In particular, starting from a complete theory (null entropy), a sequence of theories each of them being an approximation of the preceeding one, leads to an increasing sequence of entropy values. In SEA, the level of approximation has been stated, but the entropy has not yet been defined. This is an important shortcoming.

Entropy is also necessary to define the temperature. The classical definition of temperature T with [START_REF] Pauli | Statistical Mechanics[END_REF],

1

T = ∂ S ∂ E ( 1
)
where S is the entropy and E the internal energy, shows that the temperature measures the rate of increasing of entropy (and therefore the loss of information on the system) with energy. A positive temperature means that entropy is a non-decreasing function of internal energy. The loss of information during the approximation process is therefore more important for energetic systems. It is rather common in SEA literature to define the vibrational temperature as being the modal energy. This result is true but a formal proof requires to introduce the entropy [START_REF] Bot | Entropy in Statistical Energy Analysis[END_REF]. This is the purpose of this paper.

First principle of thermodynamics in SEA

SEA is a simple method to assess the vibrational energy of complex systems. SEA is entirely based on some statistical considerations and the application of energy balance (first principle) and, as we shall see, the application of entropy balance (second principle).

In SEA, a complex system is sub-divided into n components called sub-systems. Sub-systems are considered as tanks containing vibroacoustical energy E i with i = 1, . . . n whatever their nature, structural component or acoustical cavity (Fig. 1). Within sub-system i, the vibrational energy E i is repartited among N i modes. Modes are therefore the sites which carry vibrational energy, exactly in the same way that molecules carry kinetic energy in kinetic theory of gases and that atoms carry vibrational energy in solids. In the two latter cases, this energy (kinetic or vibrational) is called heat. In SEA, the equivalent of heat is therefore the vibrational energy itself. The only difference between a true heat and the vibrational heat introduced in SEA is the frequency of the underlying vibration, thermal range for the former and audio frequency range for the latter.

The heat in SEA is thus defined as the vibrational energy E i in broadband. The analysis is confined to a frequency band ∆ ω about the central frequency ω (rad/s). No strict definition is given for the width of the frequency band, but it is commonly admitted that octave bands are well suited.

The first principle of thermodynamics can now be introduced. All sub-systems can receive energy from sources, driving forces in the structural case or noise sources in acoustics. The power being injected into sub-system i is noted P inj i . But they also dissipate vibrational energy by natural mechanisms such as damping of vibration, absorption of sound by walls, attenuation of sound... The power being dissipated is noted P diss i . Finally, the vibrational energy can be exchanged with adjacent sub-systems. The net exchanged power between sub-sytem i and j is noted P i j . In steady-state condition, the energy balance for sub-system i reads,

P diss i + ∑ j =i P i j = P inj i . (2)
The power being injected P inj i is assumed to be known, but the powers being dissipated P diss i and being exchanged P i j must be expressed in terms of vibrational energies (Fig. 2).

The power being dissipated by internal losses is, In all these sub-systems, the vibration field is diffuse i.e. homogeneous and isotropic.

P diss i = ωη i E i , (3)
The SEA approach consists in writing the exchange of energy between these subsystems.

where η i is the damping loss factor usually determined by a direct measurement. The power supplied by the sub-system i to the sub-system j is,

P i→ j = ωη i j E i , (4)
where η i j is the coupling loss factor. The net exchanged power between sub-systems i and j is P i j = P i→ j -P j→i and therefore [START_REF] Lyon | Power flow between linearly coupled oscillators[END_REF],

P i j = ω (η i j E i -η ji E j ) , (5)
Coupling loss factors are phenomenological constants attached to the junction between two sub-systems. Their values must be determined in each case either by a direct measurement or by using some predictive relationships. These theoretical relationships have been derived for a large number of cases, coupling between adjacent plates, acoustical cavities, connection between plate and beam, sound radiation, vibrational response and so on. We do not enter into the discussion of the validity of a particular method to derive such relationships. A large literature is devoted to this problem and many discussions on the efficiency of these relationships can be found. For the purpose of the present discussion, it is enough to admit that for every junctions, two coupling loss factors η i j and η ji exist.

Coupling loss factors verify the reciprocity relationship,

N i η i j = N j η ji . (6)
The reciprocity relationship highlights the importance of the modal energies E i /N i . Substituting Eq. ( 6) into Eq. ( 5) leads to,

P i j = ωη i j N i E i N i - E i N i , (7)
showing that the net exchanged power is proportional to the difference of modal energies. The SEA equation is simply obtained by substituting Eqs. [START_REF] Bot | Energy exchange in uncorrelated ray fields of vibroacoustics[END_REF][START_REF] Maxit | Extension of sea model to subsystems with non-uniform modal energy distribution[END_REF] in Eq. ( 2),

ω    N 1 ∑ j η 1 j -N l η lk . . . -N k η kl N n ∑ j η n j       E 1 /N 1 . . . E n /N n    =    P inj 1 . . . P inj n    (8)
This is a linear system on vibrational temperatures whose matrix is symmetric.

Vibrational entropy, vibrational temperature

In order to rigorously define the entropy of vibrational systems within the context of SEA, it is important to well understand the approximation process applied to equations of motion to derive SEA equations. The equations of motion are the reference theory which gives an access to every physical quantities. There is no loss of information, the entropy is null. SEA is a simplified theory which does not give access to the detail of all physical quantities. There is a loss of information. In SEA, the vibrational energy is repartited among modes and the exact repartition of energy is not known. This exact repartition is refered as microstate of the system. A microstate of the system is a list of modes with a specification of their energy level such as:

Mode 1 Energy e 1 Mode 2 Energy e 2 . . .

Mode N Energy e N

The sum of all modal energies is the energy of the overall system E = ∑ N i=1 e i . Indeed, the solving of the equations of motion provides this list and therefore the knowledge of the microstate. Conversely, one can admit that the knowledge of this list gives of the total information on the system. Actually, a complete description of the state of system in steady condition is given by a list of modal amplitudes (complex-valued numbers) rather than modal energies (real-valued numbers). But in this text, we will not discuss the question of entropy induced by the loss of information when one neglects phase shifts between modal amplitudes.

The problem is therefore to quantify the loss of information between the knowledge of a microstate, that is the repartition e i with i = 1 . . . N and the knowledge of a macrostate, that is the total energy E and the number N of modes. The question is to count the number of microstates that correspond to a given macrostate.

With this idea in mind, a SEA system can be viewed as a set of N linear oscilators whose natural frequencies is an increasing sequence ω 1 , ω 2 . . . ω N (Fig. 3). And the number W of microstates attached to a macrostate E, N is given by the structure function [START_REF] Bot | Entropy in Statistical Energy Analysis[END_REF],

Ω (E) = 2π ω N E N-1 N -1! (9)
and,

W = Ω (E) h N δ E (10)
where δ E is the uncertainty on E and h is a constant introduced during the discretization of phase space into equiprobable cells. The final step is to apply Boltzmann's definition of entropy, S = k logW (11)

with the result,

S(E, N) = kN 1 + log 2π hω E N (12)
This is the microcanonical entropy of a SEA sub-system. Eq.( 12) gives the complete expression of the "vibrational entropy" of any SEA sub-system. The temperature is obtained as for any thermodynamic system with,

1 T = ∂ S ∂ E N ( 13
)
with the result,

T = E kN ( 14
)
As it was expected from Eq. ( 7) giving the power flow between two SEA subsystems, the "vibrational temperature" is well defined by the modal energy. In the literature, this result is generally obtained from an analogy between SEA and thermodynamics. This is now a logical consequence of the expression of the entropy obtained from Boltzmann's definition.

Second principle of thermodynamics in SEA

The second principle of thermodynamics states that entropy of isolated system cannot decrease. This is also true within the context of SEA. The problem that must be considered is the mixing of vibrational energy of two adjacent sub-systems.

Let us consider two sub-systems with energies E 1 , E 2 and mode counts N 1 and N 2 . If these sub-systems are isolated, their entropies are respectively S(E 1 , N 1 ) and S(E 2 , N 2 ) given by Eq. ( 12). Now, if these two sub-systems are connected together, the final state has energy E 1 + E 1 and the total number of modes is N 1 + N 2 . When equilibrium is reached, the final entropy of the overall system is S(E 1 + E 2 , N 1 + N 2 ), once again given by Eq. ( 12).

The difference between the final entropy and the sum of initial entropy is therefore the entropy created during the mixing process.

∆ S = S(E, N) -[S(E 1 , N 1 ) + S(E 2 , N 2 )] (15)
By substituting Eq. ( 12), it yields,

∆ S = k(N 1 + N 2 ) log E 1 + E 2 N 1 + N 2 -kN 1 log E 1 N 2 -kN 2 log E 2 N 2 (16)
This is the entropy created by mixing the energy of the two sub-systems. This entropy production is non-negative ∆ S > 0. This result stems from the convexity of the function f (x, y) = -y log(x/y). The fact that ∆ S is non-negative can be interpreted in terms of loss of information. The loss of information for sub-system i is the log of the number of microstates corresponding to E i , N i . And the loss of information for the overall system is the log of the number of microstates corresponding to

E = E 1 + E 1 , N = N 1 + N 1 .
But there is many more possibilities to share the energy E = E 1 + E 1 over N = N 1 + N 1 modes than the sum of possibilities to share on the one hand, E 1 over N 1 modes and, on the second hand, E 2 over N 2 modes. The difference between the two is exactly the loss of information during the mixing process.

Entropy balance in SEA

Coming back to the initial situation of n sub-systems in interaction, we are now in position to state an entropy balance of the overall system in SEA. Three questions must be examined: sources, dissipation and mixing.

The variation of entropy is driven by the variation of vibrational energy around a vibrational temperature. Since the number of modes N is always fixed, Eq. ( 13) gives the infinitesimal variation of entropy dS for an infinitesimal variation δ E,

dS = δ E T ( 17
)
For sources, the injected power is P inj i . The vibrational energy δ E supplied to the sub-system during time dt is δ E = P inj i dt. It follows that the increase rate of entropy by sources is, dS

inj i dt = P inj i T i = k P inj i N i E i (18)
The last equality stems from Eq. ( 14).

Similarly, dissipation processes of vibration within sub-systems leads to a modification of vibrational level. This energy is dissipated that is transformed into heat (in the sense of thermics). In classical thermodynamics, dissipation processes induce an increase of entropy by creating heat inside the system. But, in SEA, that we have called vibrational heat is the vibrational energy itself. And dissipation leads to a decreasing of vibrational energy. In other words, dissipation tends to cool the system and therefore induces a decreasing of vibrational entropy.

dS diss i dt = - P diss i T i = -kωη i N i (19)
where the last equality is deduced from Eq. ( 3). The mixing of energy at interfaces between sub-systems also induces a variation of entropy. As we have seen in previous section, this variation is always non-negative. Let us develop this point. The power being exchanged between subsystems i and j is P i j . Therefore, the vibrational entropy introduced in or extracted from sub-system i is -P i j /T i . Following the same reasoning, the vibrational entropy introduced in sub-system j is -P ji /T j . Since P i j = -P ji , the net vibrational entropy introduced in the entire system by the mixing process is,

dS i j dt = P i j 1 T j - 1 T i = kω(η i j E i -η ji E j ) N j E j - N i E i (20)
The last equality stems from Eq. ( 5). For the entire system, the vibrational entropy introduced in the system is,

dS dt = n ∑ i=1 dS inj i dt + dS diss i dt + ∑ i> j dS i j dt (21)
It is easy to deduce from Eq. ( 2) that this entropy is null,

dS dt = 0 (22)
It means that there is no production of entropy for the entire SEA system. But there is an exchange of entropy with exterior which exactly balances the production of entropy by mixing processes (Fig. 4).

Conclusion

In this paper, it has been shown that the second principle of thermodynamics can be stated in the context of SEA. Explicit relationships have been derived for the vibrational entropy of sub-systems and the production of entropy at interfaces of sub-systems. SEA is up to now only based on the application of the energy balance. An entropy balance also applies. Entropy is also produced by mixing process at interfaces between adjacent sub-systems. Vibrational entropy S i of sub-systems results from the balance of sources, dissipation and mixing.

energy over modes. But if we want to measure the effect of particular statistical properties such as the boundary conditions are not known, we must modify this entropy expression. And we can even imagine to add all these individual entropies for boundary conditions, size of system, properties of material and so on, to get a more accurate expression of vibrational entropy.

F. Ziegler:

You mentioned that when you define the "vibrational temperature" as modal energy divided by Boltzmann constant and when you calculate the vibrational temperature of a plate for usual acoustical levels, you get very a high temperature about ten power eleven Kelvins! So, what are the physical consequences of this fact? Can we will not use this theory of thermodynamics only because of the improper scale of these numbers?

A. Le Bot: I think that there is absolutely no physical consequences of this fact. In astronomy, for instance, measurements are so accurate and signals so tiny that they must aware of noise level induced by mechanical vibration. They have very large structures which are in thermal equilibrium with surrounding air and therefore, the "vibrational temperature" is equal to the true thermal temperature of hundred Kelvins. But in our case, the sources of vibration have a mechanical origin and therefore we deals with very large vibration, which are not in thermal equilibrium with usual thermal frequencies. This is why we get so high vibrational temperatures. But this very hot vibration is confined into a relatively low and narrow frequency band which is disconnected from thermal frequencies. The value of Boltzmann constant is not well-suited in SEA for usual vibrational systems and therefore, the question which raises is the definition of an appropriate scale for vibrational temperature.

A. Belayev:

Antonio was the first to introduce the vibrational entropy in SEA.

A. Carcaterra:

I just worked on that subject some years ago. And it is a very interesting theoretical point of view. But my concern was that it is not really obvious how we can use this additional concept of vibrational entropy in terms of improving the SEA models. How is it possible to use an entropy balance equation in order to get more information on SEA models or in order to get an advantage in the description of vibroacoustical systems?

A. Le Bot:

This is indeed an important question and may be the only question of interest in fact. Is it useful to use the entropy concept in vibroacoustics? I now work on this problem for a couple of years and I sincerely hope that it is useful! But let me read some lines from Ingo Muller who recently wrote an interesting paper in Entropy journal on historical aspects of thermodynamics: "In the nineteenth century -after the formulation of the seconf law -there was a noisy controversy between energetics, represented by Oswald, and thermodynamics favoured by Boltzmann. Energeticists maintained that the entropy was not needed. There were wrong, but they did have a point, albeit only at small temperatures. Planck was involved -in a minor role -in the discussion as an unaprreciated supporter of Boltzmann's thermodynamic view. It was this controversy which prompted Planck to issue his oft-quoted dictum: The only way to get revolutionary advances in science accepted is to wait for all scientists to die."

Fig. 1

 1 Fig. 1 Decomposition of complex structure in SEA. The vibroacoustical problem is solved by splitting the complex structure into n elements.In all these sub-systems, the vibration field is diffuse i.e. homogeneous and isotropic. The SEA approach consists in writing the exchange of energy between these subsystems.

Fig. 2

 2 Fig.2Energy balance in SEA. Sources supply energy to sub-systems. Part of this energy is dissipated by natural processes. Energy is finally exchanged between adjacent sub-systems. Vibrational energy E i of sub-systems results from the balance of sources, dissipation and exchanges.

Fig.

  Fig.[START_REF] Bot | Energy exchange in uncorrelated ray fields of vibroacoustics[END_REF] Principle of a SEA system. The vibrational energy E is repartited among N linear oscillators whose natural frequencies is an increasing sequence ω 1 , ω 2 . . .ω N . The detailed repartition of the energy e 1 , e 2 . . .e N is a microstate whereas the knowledge of the total energy E and the number N of oscillators is a macrostate.

Fig. 4

 4 Fig.[START_REF] Bot | Derivation of statistical energy analysis from radiative exchanges[END_REF] Entropy balance in SEA. Sources supply entropy to sub-systems. Dissipation processes extract entropy since they are responsible of a cooling of the sub-system. Entropy is also produced by mixing process at interfaces between adjacent sub-systems. Vibrational entropy S i of sub-systems results from the balance of sources, dissipation and mixing.

Acknowledgments

The author wishes to acknowledge the ANR (National Research Agency, France) for its financial support with the project ANR-BLANC DyVIn.

Questions

G. Tanner:

What is the meaning of the number of modes N if one considers the continuum limit which is natural in acoustics?

A. Le Bot:

This problem is also encoutered in classical mechanical statistics. The usual response of physicists is to say that basically nothing is continous, everything is quantum that is discrete. I think that this response is not satisfactory for vibroacoustics. In physical statistics, we start from systems which have a huge but finite number of states and we derive continuum mechanics. But in statistical vibroacoustics we start from a continous equation and our problem is not to know if this equation is an approximation of a more fundamental equation but rather to degrade it with further statistical assumptions. What was discussed in this talk is how to quantify the amount of information that has been lost during this second level statistical process.

Y. Ben-Haim:

Could you extend this formalism to open systems? For instance, when vibroacoustic systems radiate and they have a lost of energy and they also exchange entropy because energy is leaving the system and going into vacuum or air.

A. Le Bot:

I just said that this approach is limited to the case where the surface of constant energy is closed but not that the system itself is closed. I don't know if this a possibility to apply this formalism to open systems, but I feel that this formalism is not simply well-suited for non-finite systems which, by nature, cannot be in thermal equibrium.

P. Shorter:

Let's me make a comment on the number of configurations. It's not only a story of number of modes. If you consider a plate with only two modes but in a very large ensemble of similar plates, they may have varying damping, material properties or boundary conditions. So the variation of entropy is taken over this space of configurations. But, if you look at a single system, a single system has a very smooth response, while it has a huge number of modes. But that doesn't definetely suppose it has only one value, the one given by a SEA model. It's value can be different from the one you've got from an ensemble average.

A. Le Bot:

In the expression of the vibrational entropy I propose to use, it is just included the missing information relative to fact that we don't know the exact repartition of