Emilie Joannopoulos
email: emilie.joannopoulos@usherbrooke.ca

Franc ¸ois Dubeau

Jean-Pierre Dussault

Mounir Haddou

Candido Pomar

J.-P Dussault

A simple pooling model with application in the feed industry and its global solution analysis

We present a specific pooling model which, while simple, still uses bi-linear objective and constraints. An absolute lower bound is available for this model. We conjecture that any local solution is a global minimizer for this simple instance. We will motivate its usage within a feed industry application. We will then present several experiments to support our conjecture. Since the dimension is in the hundreds, no global solver is able to solve it. Among arguments to support our conjecture is the fact that for smaller instances solvable by global solvers, the solutions computed by local solvers are indeed global.

Introduction

Finding the global solution to nonlinear nonconvex problems has been an active research interest for several years. Few global solvers exist, as BARON [START_REF] Tawarmalani | A polyhedral branch-and-cut approach to global optimization[END_REF][START_REF] Sahinidis | BARON 14.3.1: Global Optimization of Mixed-Integer Nonlinear Programs[END_REF] or Couenne [START_REF] Belotti | Couenne: a user's manual[END_REF] and they use a branch-and-bound algorithm. The branch-and-bound methods consists in finding lower and upper bounds of the nonconvex problem and refining them successively. Such algorithms are useful and efficient for small problems that may have dozens of constraints but if the problem is too large it cannot be solved using branch-and-bound algorithm. Thus, some other methods have to be found for large problems. This is our case when we consider the diet problem, especially in the pig industry. The problem that we study has 254 variables and 2700 constraints and we would like to determine its global solution. Indeed, this study has first and foremost a practical aim. The goal is to set up a new least cost feeding system in farms in order to decrease the feed cost that represents more than 70% of the production cost. Using nonlinear solver, we are able to compute local solutions to our problem. We conjecture that the local solution obtained is indeed a global optimum. In this paper, after stating the problem that we are interested in, the diet problem, we will describe some useful methods to determine upper and lower bounds to a nonlinear nonconvex problem. First of all, we will present two different ways to formulate our problem. The pooling problems are commonly used in petroleum industry but can be easily adapted for the agrifood industry. These formulations make it possible to obtain an upper bound of the global optimum of the diet problem since we are looking for a minimum. By discretizing one variables that appears in the bilinear terms, the problem can be transformed into a mixed integer linear problem. This method could give a good approximation of the optimal solution. Then we will describe three relaxation methods. The best known is probably the linear relaxation introduced by McCormick in 1976 [START_REF] Mccormick | Computability of global solutions to factorable nonconvex programs: Part I -Convex underestimating problems[END_REF]. It relaxes a nonlinear nonconvex problem into a linear convex problem. This method leads to a lower bound as well as the one introduced by Tawarmalani et al. in 2010 [START_REF] Tawarmalani | Strong valid inequalities for orthogonal disjunctions and bilinear covering sets[END_REF] which gives the convex hull of sets like B = {(x, y) ∈ R n + | ∑ n i=1 ax i y i + b i x i + c i y i r} and the semidefinite programming relaxation. We will try to reduce the gap between the lower and upper bounds at most thanks to all these approaches and we will see that some methods seems to be theoretically efficient but could not be in the specific case of the diet in the pig industry.

2 Pooling formulation of a diet problem

Diet problem history

The diet problem was introduced first by Stigler, an American economist, in 1945 [START_REF] Stigler | The cost of subsistence[END_REF]. Initially, it was the following linear problem

   min x c t x, s.t. Ax b, x 0. (P L )
This problem was first solved by using heuristics. Then, in 1947, Dantzig developed the simplex algorithm [START_REF] Dantzig | Linear Programming and Extensions[END_REF][START_REF] Dantzig | The diet problem[END_REF] and undertook to test his algorithm on the Stigler's diet problem and finally made it possible to solve this problem without using heuristics.

Until today, many studies have been performed on the diet problem in general ( [START_REF] Lancaster | The evolution of the diet model in managing food systems[END_REF][START_REF] Lancaster | The history of the application of mathematical programming to menu planning[END_REF][START_REF] Garille | Stigler's diet problem revisited[END_REF] for example), but the linear problem is the most common model used. Moreover, a significant progress has been made in the diet modelling with the add of upper bounds on variables and constraints.

The diet problem interested a lot, especially the pig industry in which feed represents 70 % of the production cost and in an economic context of international competition, it is important to reduce it. Thus, a few studies [START_REF] Benchakroun | Revision of the traditionnal diet formulation model[END_REF][START_REF] Dit Bailleul | Modélisation et optimisation du revenu net de l'engraissement[END_REF][START_REF] Beaudoin | Méthodes d'optimisation du revenu net de l'engraissement porcin[END_REF] have been made in order to reduce feed cost. Those methods are currently used in the industry and use linear programming. More recently, Joannopoulos et al. [START_REF] Joannopoulos | Diet problems[END_REF] presented a new way of modelling the feeding system. This method is based on two feeds which are blended in different proportions each day. The model representing this feeding system is bilinear. More precisely, it has a bilinear objective function, and bilinear and linear constraints. It can be resume by the following model :

                   min x,y ∑ i∈I ∑ j∈J Q 0 i j x i y j + a 0 i x i + c 0 j y j , s.t. ∑ i∈I ∑ j∈J Q p i j x i y j + a p i x i + c p j y j d p ∀p ∈ 1, n , A x y b, 0 x y
x M y M .

(P BL )

The pig's diet model

The model corresponding to the pig's diet problem is slightly different than the general one. Indeed, by referring to the (P BL ), no linear terms appears when there are the bi-linear ones and the model is written as follow :

                                   min x 1 ,x 2 ,y 1 ,y 2 ∑ i∈I ∑ j∈J q 0 i (x 1i y 1 j + x 2i y 2 j ) , s.t. d p j ∑ i∈I q p i (x 1i y 1 j + x 2i y 2 j ) d p j ∀p ∈ P, ∀ j ∈ J, b A     x 1 x 2 y 1 y 2     b, 0     x 1 x 2 y 1 y 2         m x 1 m x 2 m y 1 m y 2     . (P Pig )
In this model, each constraint is lower and upper bounded and is at least non-negative. Upper and lower bounds are equal in case of an equality constraint. Variables x 1 and x 2 are of size 16 and represent the feeds while y 1 and y 2 are of size 111 and represent the quantity of each feeds given at each day. It has a total of 2700 constraints, including 115 equality constraints and 2515 inequality constraints.

A particularity of the problem is that we already know a lower bound of the optimal value which is given by an ideal model.

The ideal model

The ideal problem consists in using the optimal cost feed at each day. This model is a relaxation of the problem (P Pig ) and can be modeled as a linear one as follow :

       min x ∑ i∈I ∑ j∈J q 0 i x i j s.t. d p j ∑ i∈I q p i x i j d p j ∀p ∈ P, ∀ j ∈ J, b Ax • j b, ∀ j ∈ J, (P PigId )
Moreover, it is separable and we can write it as a small linear problem for each day. In that model the vector x • j represents the diet given to the pigs at day j. The global solution to this problem can be obtain easily by a linear solver and its optimal value is 94.8423. Nevertheless, the associated feeding system is impracticable for growers due to the high number of feed to store (1 per day), but the solution will be kept in mind as a lower bound of the problem (P Pig ).

Performance of global solvers

In order to solve the bilinear problem (P Pig ), the modelling were done using AMPL [START_REF] Fourer | AMPL: A Modeling Language for Mathematical Programming[END_REF]. The global solution of the problem could be obtained by using global solvers like Couenne [START_REF] Belotti | Couenne: a user's manual[END_REF] or BARON [START_REF] Tawarmalani | A polyhedral branch-and-cut approach to global optimization[END_REF][START_REF] Sahinidis | BARON 14.3.1: Global Optimization of Mixed-Integer Nonlinear Programs[END_REF], while Ipopt [START_REF] Wachter | On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming[END_REF] guarantee a local optimum only. As we can see in table 1, neither Couenne nor BARON can return optimal solution of the whole (P Pig ) problem, i.e. when |J| = 111, and reached the time limit set to 8 hours. Considering a smaller problem (|J| = 2 to 4), Couenne is not able to return the global solution and also reached the time limit, while BARON, for its part, return the global solution for |J| = 2 and |J| = 3 but is not able to obtain the solution for an higher value of |J|.

On the contrary, Ipopt returns a solution for each instance, but it guarantees only local optimum. However, we can notice that the optimal point obtained for |J| ∈ {2, 3} is in reality a global optimal solution. Hence, we conjecture that the solution returned by Ipopt is a global optimal solution.

Pooling problem

The diet problem as we described it above can be associated to a particular pooling problem. Here, we will describe two way to model a pooling problem, the p-formulation and the qformulation.

The standard pooling problem was introduced by Haverly [START_REF] Haverly | Studies of the behavior of recursion for the pooling problem[END_REF] in 1978. The concept of the pooling problem is the following : inputs are send into pool tanks to be blended together. Then mixtures from the pools are sent to outputs to get the final products. Moreover, inputs can be directly added to the final products. The pooling problem may be illustrated by a graph (Figure 1).

In the p-formulation of a pooling problem, the variables, associated to the flow, are modeled in quantity flowing on each edge. The particularity of this formulation is that we have to add a flow conservation constraint in addition of all the specification requirements. This constraint can be formulated

∑ i∈I w i,p = ∑ j∈O y p, j ∀p ∈ P. INPUTS POOL OUTPUTS i 1 i 2 i 3 i 4 p 1 p 2 j 1 j 2 j 3 j 4 w i 1 p 1 w i 1 p 2 w i 3 p 1 w i 3 p 2 w i 4 p 2 y p 1 j 1 y p 1 j 2 y p 2 j 2 y p 2 j 3 y p 2 j 4 z i 2 j 4
Fig. 1 Illustration of the pooling problem This is how Haverly introduced the pooling problem. Then, Ben-Tal et al. [START_REF] Ben-Tal | Global minimization by reducing the duality gap[END_REF] propose to model the flow between inputs and pools in proportions. This is the q-formulation. In this formulation we also have to add a constraint defining the proportion entering in tanks

∑ i∈I w ip = 1 ∀p ∈ P.
Both formulation are equivalent but the way to model the problem is different. We can wonder if the non-linear algorithms handle both model in the same way.

In the case of the pig's diet problem, inputs cannot be directly added to outputs. For example edge z i 4 j 4 form i 4 to j 4 on figure 1 will not be allowed. From now on, we will not consider these edges.

These two formulations of the pooling problem were implemented in AMPL. Both pformulation and q-formulation return exactly the same solution when they are solved by the non linear solver Ipopt, which is the same as the one given in table 1.

This result supports the conjecture we claimed that it is a global solution of the pig's diet problem. In order to verify the conjecture, we will present several approaches. All of them are either approximation or convex relaxation.

3 Relaxations of bi-linear terms

Approximation of the global optimal solution using variables discretization

The initial bilinear problem is designed in continuous variables. We will see that discretizing one of the variables involved in the bilinear terms give at the end a mixed integer linear problem. This section is inspired from [START_REF] Rodriguez | A comparative assessment of linearization methods for bilinear models[END_REF]. Let 0 x i x M i and 0 y j y M j be the variables and consider one bilinear term x i y j . One variable is discretized in base 2, for example y, as follows

|J|

y j = y M j K ∑ k=0 2 -k α jk
where α jk ∈ {0, 1} is a binary variable and K is the precision of the discretization. Now, the bilinear term is given by

x i y j = x i y M j K ∑ k=0 2 -k α jk = y M j K ∑ k=0 2 -k α jk x i .
We can see here that even by discretizing one variable the term is still bilinear. However, this could be modified by introducing a new variable. Let x i jk be this one, such that

x i jk = 0 if α jk = 0 x i if α jk = 1.
This variable is set thanks to the four following inequality

       x i jk 0, x i jk -x i 0, -x i jk + x i -x M i (1 -α jk ) 0, x i jk -x M i α jk 0. (1)
Thus, we get

x i y j = y M j K ∑ k=0 2 -k x i jk
which is a linear term in x i jk . Therefore, by replacing each bilinear terms by a variable like x i jk and adding the four equations (1) as constraints for each one, the problem become linear.

First we decided to discretize y 1 and y 2 . Applying it on P BL , we obtain the following linear model :

                                                                                     min x 1 ,x 2 ,y 1 ,y 2 ,x 1 ,x 2 ,α,β ∑ i∈I ∑ j∈J ∑ k∈K q 0 i 2 -k m y 1 x 1 i jk + m y 2 x 2 i jk , s.t. d p j ∑ i∈I ∑ k∈K 2 -k q p i m y 1 x 1 i jk + m y 2 x 2 i jk d p j , ∀p ∈ P, ∀ j ∈ J, b A     x 1 x 2 y 1 y 2     b, 0     x 1 x 2 y 1 y 2         m x 1 m x 2 m y 1 m y 2     , x 1 i jk 0, ∀i ∈ I, ∀ j ∈ J, ∀k ∈ K, x 1 i jk -x 1i 0, ∀i ∈ I, ∀ j ∈ J, ∀k ∈ K, -x 1 i jk + x 1i -m x 1 (1 -α jk ) 0, ∀i ∈ I, ∀ j ∈ J, ∀k ∈ K, x 1 i jk -m x 1 α jk 0, ∀i ∈ I, ∀ j ∈ J, ∀k ∈ K, x 2 i jk 0, ∀i ∈ I, ∀ j ∈ J, ∀k ∈ K, x 2 i jk -x 2i 0, ∀i ∈ I, ∀ j ∈ J, ∀k ∈ K, -x 2 i jk + x 2i -m x 2 (1 -β jk) 0, ∀i ∈ I, ∀ j ∈ J, ∀k ∈ K, x 2 i jk -m x 2 α jk 0, ∀i ∈ I, ∀ j ∈ J, ∀k ∈ K, α jk , β jk ∈ {0, 1}, ∀ j ∈ J, ∀k ∈ K.
(P pigDisc ) This problem could be solved by mixed integer linear solvers and return an approximation of the solution of the initial problem (P Pig ) written in continuous variables. The implementation was done in AMPL and we solved it using CPLEX 12.6 as a mixed integer linear solver.

In order to test this methods, we started with a small problem, namely |I| = 16, |J| = 2 and |K| = 4 and then |J| has been increased. Table 2 shows the results for |J| = 2 to |J| = 7. We can notice that the gap between both models is really small. It means that this approximation of the solution is a good one. However, if we look at the CPU time taken by CPLEX to solve (P pigDisc ) problems, we notice that it grows exponentially. It is tenfold for each time that |J| is incremented by one. In the initial problem, |J| = 111. Thus, the needed time to solve the general discretized problem could be 10 100 years.

Use (P pigDisc ) instead of (P Pig ) is a good idea to get an approximation of the global solution but is not appropriate to our problem due to its size and we don't go further in the idea. Moreover the same result appears when the variables x 1 and x 2 are discretized instead.

Convex relaxations

This section will be devoted to the presentation of three convex relaxations. These methods will give lower bounds of the initial (P Pig ).

McCormick relaxation

The first relaxation that we will present is the best known. McCormick [START_REF] Mccormick | Computability of global solutions to factorable nonconvex programs: Part I -Convex underestimating problems[END_REF] introduced it in 1976. It provides a linear relaxation of the initial problem by using only the bounds variables. The concept is the following. Suppose that we have two variables x i and y j that appear in a bilinear term and such that l x i x i u x i , l y j y j u y j .

From these equations, we get

       (x i -l x i )(y j -l y j ) 0, (x i -l x i )(u y j -y j ) 0, (u x i -x i )(y j -l y j ) 0, (u x i -x i )(u y j -y j ) 0, ⇐⇒       
x i y jx i l y jy j l x i + l x i l y j 0, x i u y jx i y jl x i u y j + y j l x i 0, y j u x iu x i l y jx i y j + x i l y j 0, u x i u y jy j u x ix i u y j + x i y j 0.

Let z i j = x i y j then we get the system        z i jx i l y jy j l x i + l x i l y j 0, x i u y jz i jl x i u y j + y j l x i 0, y j u x iu x i l y jz i j + x i l y j 0, u x i u y jy j u x ix i u y j + z i j 0. This system is linear in z i j , x i and y j .

A linear relaxation of the bilinear initial problem is given by replacing all the bilinear terms x i y j by z i j and adding in the model the system described above. This relaxation is called the McCormick relaxation and is very commonly used.

In the case of the diet problem in pig industry, the bilinear terms looks like x ti y t j for i ∈ I, j ∈ J and t ∈ {1, 2}. x 1 and x 2 never appears in the same bilinear term, as well as y 1 and y 2 , x 1 and y 2 or x 2 and y 1 .

Let x 1i j = x 1i y j and x 2i j = x 2i y j . If we applied the McCormick relaxation to (P Pig ), we obtain the following problem :

                                                                             min x,y ∑ i∈I ∑ j∈J q 0 i (x 1i j + x 2i j ) , s.t. d p j ∑ i∈I q p i (x 1i j + x 2i j ) d p j , ∀p ∈ P, ∀ j ∈ J b A     x 1 x 2 y 1 y 2     b, 0     x 1 x 2 y 1 y 2     m. x 1i j 0 ∀i ∈ I, ∀ j ∈ J m y 1 j x 1i -x 1i j 0 ∀i ∈ I, ∀ j ∈ J m x 1i y 1 j -x 1i j 0 ∀i ∈ I, ∀ j ∈ J m x 1i m y 1 j -m x 1i y 1 j -m y 1 j x 1i + x 1i j 0 ∀i ∈ I, ∀ j ∈ J x 2i j 0 ∀i ∈ I, ∀ j ∈ J m y 2 j x 2i -x 2i j 0 ∀i ∈ I, ∀ j ∈ J m x 2i y 2 j -x 2i j 0 ∀i ∈ I, ∀ j ∈ J m x 2i m y 2 j -m x 2i y 2 j -m y 2 j x 2i + x 2i j 0 ∀i ∈ I, ∀ j ∈ J (P PigMC )
This problem is linear and can be solved using CPLEX. The optimal cost is then 94.1812 which is less than the lower bound known. However the model can be improved. Indeed, in (P Pig ) appears the constraints

y 1 j + y 2 j w j (2)
∑ i∈I x 1i = 1 (3) ∑ i∈I x 2i = 1 (4)
By multiplying (3) by y 1 j , as well as y 2 j by (4), we get that

y 1 j = ∑ i∈I x 1i y 1 j y 2 j = ∑ i∈I x 2i y 2 j
which leads to the modification of the constraint (2) by

y 1 j + y 2 j = ∑ i∈I x 1i y 1 j + x 2i y 2 j w j ⇐⇒ ∑ i∈I x 1i j + x 2i j w j .
Identically, the constraints (3) and ( 4) can be modify in the two following

y 1 j = ∑ i∈I x 1i j y 2 j = ∑ i∈I x 2i j
Doing these modifications we just add some valid cutting plans which we hope improve the relaxation.

And hopefully, solving this problem leads to a slight improvement. The optimal cost returned by solvers is 94.8423, which is exactly the lower bound already known give by solving (P PigId ).

After some studies of this model, we can notice that the McCormick relaxation including cutting planes is, in fact, exactly the same linear problem that model the diet using the optimal cost feed at each day, namely (P PigId ) the model giving the lower bound. Indeed, let x i j = x 1i j + x 2i j which correspond to the quantity of ingredient i for the diet of day j. Then when it is replaced in the model (P PigMC ) and we can see that it corresponds exactly to (P PigId ) problem.

Tawarmalani et al. convex hull

More recently, Tawarmalani et al. [START_REF] Tawarmalani | Strong valid inequalities for orthogonal disjunctions and bilinear covering sets[END_REF] stated a new result about the convex hull of a bi-linear set.

Proposition 1 Consider B = (x, y) ∈ R n + × R n + | ∑ n i=1 (a i x i y i + b i x i + c i y i ) r ,
where, for each i ∈ {1, ..., n}, a i , b i and c i are non-negative and r is strictly positive.

Let η i (x i , y i ) = 1 2 b i x i + c i y i + (b i x i + c i y i ) 2 + 4a i rx i y i . Then, conv(B) = (x, y) ∈ R n + × R n + | n ∑ i=1 η i (x i , y i ) r
is the convex hull of B.

Unlike the McCormick relaxation, this one is a non-linear convex relaxation. It represents the convex hull of the bilinear set B.

We will now apply this approach to the pig's diet problem. Because all coefficients in the objective function and constraints are positive, the relaxation can be applied only on the "greater or equal" constraints. The relaxation obtained is not convex due to the bi-linear constraint of type "less or equal", but it can give an idea on the fact that we will be able to improve the lower bound.

Solving this problem using Ipopt, the optimal cost returned is 89.54 which is far from the lower bound. This relaxation is supposed to be the convex hull of the set while McCormick is only a linear relaxation. The fact that the optimal solution of the Tawarmalani et al. relaxation is smaller than the one of McCormick relaxation is due to the bounds on variables.

The next section is devoted to show how bounds on variables act on these two relaxations.

Illustration of McCormick and Tawarmalani relaxations

As an illustration of these two relaxations, consider the set

B = (x, y, z) ∈ [1, 5] 3 |xy + z 4 .
This set is represented by all the point belonging to [START_REF] Dit Bailleul | Modélisation et optimisation du revenu net de l'engraissement[END_REF][START_REF] Ben-Tal | Global minimization by reducing the duality gap[END_REF] 3 and above the surface on figure 2. If we apply the proposition 1 to the set B, we get the following set

B T = (x, y, z) ∈ R 3 + | 2 √ xy + z 4
which is represented in figure 4 by all the point above the black surface.

Finally, figure 5 includes both relaxations in addition the initial bi-linear surface.

We can see that both relaxations intersect each other. Thus it may happen that the Mc-Cormick relaxation is better than Tawarmalani's et al. Even more interesting, if conditions are right, the McCormick relaxation can be strictly included in the convex hull describe by Tawarmalani et al.

For example, if we consider the bi-linear set

B = (x, y, z) ∈ [0,t x ] × [0,t y ] × [0,t z ] | xy + bz r
then the convex hull is given by

B = (x, y, z) ∈ [0,t x ] × [0,t y ] × [0,t z ] | √ rxy + bz r .
The convex relaxation for this set is given by the four following equations xy 0 (5)

x(t yx) 0 (6) (t xx)y 0 (7) (t xx)(t yy) 0 ( 8) By ( 6) and ( 7) we can deduce that rbz t y x,

rbz t x y.

SDP relaxation

Another way to get a lower bound of a bi-linear problem is to use the semidefinite programming relaxation.

The idea to use it comes from the paper [START_REF] Bao | Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons[END_REF]. Every bi-linear problem can be written as a quadratic program. Indeed, (P BL ) can be rewritten min

x,y a 0 x + x t Q 0 y + c 0 y, s.t. a p x + x t Q p y + c p y d p ∀p ∈ 1, n , A x y b, 0 x y m,
The aim of the SDP relaxation is to write the problem as min

x,y,Z f (x, y, Z),

s.t. b g(x, y, Z) B, Z 0,
where f and g are linear functions. First, let the inner product of two matrices A and B be defined as

A • B = tr(AB).
A quadratic term w t Qw can then be written using the inner product of two matrices. Let W = ww t . Thus

w t Qw = Q •W.

By a changing of variable z =

x y and adjusting the data matrices, we are able to state the bi-linear problem as follows :

min z,Z Q 0 • Z + c 0 z, s.t. Q p • Z + c p z d p ∀p ∈ 1, n , Az b, 0 z m, Z = zz t .
It is then relaxed by replacing Z = zz t by

Z zz t ⇐⇒ Z -zz t 0 ⇐⇒ Z z z t 1 0
Thus the SDP relaxation of a bi-linear problem can be written as

                 min z,Z Q 0 • Z + c 0 z, s.t. Q p • Z + c p z d p ∀p ∈ 1, n , Az b, 0 z m, Z z z t 1 0 (P SDP )
In order to accelerate computation of the solution of the SDP problem, we separate it by blocks. So, here, we will consider

z 1 = x 1 y 1 and z 2 = x 2 y 2 .
Then the problem looks like

                                 min z,Z Q 0 • Z 1 + Q 0 • Z 2 s.t. Q p • Z 1 + Q p • Z 2 d p ∀p ∈ P A z 1 z 2 b 0 z 1 z 2 m 1 m 2 Z 1 z 1 z t 1 1 0 Z 2 z 2 z t 2 1 0 (P PigSDP )
To this problem we can add several valid cutting planes. For example, the new variable Z 1 and Z 2 represent the quadratic term and then can be lower bounded by 0 and upper bounded by m i m t i .

The modelling was done in Matlab R2015b. Solving this problem using CVX [START_REF] Grant | CVX: Matlab software for disciplined convex programming[END_REF][START_REF] Grant | Graph implementations for nonsmooth convex programs[END_REF] and in particular the solver SDPT3 leads to an optimal cost of 94.8423, namely exactly the lower bound already known.

After studying this model, we noticed that the SDP relaxation is the same problem that give the lower bound, namely the ideal problem (P PigId ). For the same reasons that we claimed in 3.2.1, it is easy to see that by replacing Z 1 + Z 2 by a new term in (P PigSDP ) leads to solve a problem that determine the optimal cost diet at each day. Moreover, no additional valid cutting planes can be added in order to improve it.

Conclusion

Section 2.5 includes two different way to formulate the diet problem that we are interested in. These two formulations provide solutions of the problem. These solutions are guaranteed to be a local minimum only but we conjecture that they are global minimum. However they provide upper bounds of the global solution.

The others methods presented in this paper are relaxation or approximations. We are able to get a mixed integer linear problem by discretizing some variable involved in bilinear terms. This method can lead to to a solution close the global minimum of the bi-linear problem. However, it is too slow to solve the entire problem due to the branch and bound algorithm used. As an example, solve the problem with 32 continuous variables and 14 integer variables (instead of 222) took around 4 × 10 6 seconds. It is a good method but not appropriate in our case since the problem is too large.

We also presented three relaxations. These approaches provide lower bounds of the bilinear problem but does not improve the one already known. However, some of them provide the same lower bound and the gap between lower and upper bound is only 2%. They are good bounds but each method that we try could not improve it due to peculiar shape of our diet problem. In the general case, these methods can produce a good lower bound.

Fig. 2 Fig. 4 Fig. 5

 245 Fig. 2 Representation of the bi-linear set B = (x, y, z) ∈ [0, 5] 3 |xy + z 4 . Fig. 3 Representation of the bi-linear set B and the McCormick relaxation set B M .

Fig. 6

 6 Fig. 6 Illustration when conditions are met so that McCormick relaxation strictly included in the convex hull describe by Tawarmalani et al.

Table 1

 1 Comparison of non-linear solvers (Couenne, BARON and Ipopt) solution and CPU time.

	|J|	Couenne obj. value CPU time	BARON obj. value CPU time	Ipopt obj. value CPU time
	2	N/A	TL	1.01754	0.144977	1.01754	0.162931
	3	N/A	TL	1.53933	0.132979	1.53933	0.122153
	4	N/A	TL	N/A	TL	2.06981	0.437493
	111	N/A	TL	N/A	TL	96.2316	8.29799
	N/A : not available, TL : time limit reached (28,800 s)

Table 2

 2 Optimal cost of the discretized (CPLEX solver) and bilinear (Ipopt solver) model and CPU time.

		Solution value	CPU time (in s)
		(P Pig )	(P pigDisc )	(P Pig )	(P pigDisc )
	2	1.01754	1.01754	0.162931	5.63164
	3	1.53933	1.53933	0.122153	79.3265
	4	2.06981	2.06986	0.437493	714.843
	5	2.60897	2.60911	0.180731	3 832.76
	6	3.15681	3.15717	0.339369	30 988.7
	7	3.71333	3.71396	0.478266	433 168

  Thus if r t x t y then McCormick relaxation is always better than then convex hull of Tawarmalani et al. Figure 6 illustrates this case for the numerical example. Considering theses results, Tawarmalani et al. relaxation does not help to determine if the local solution is in reality a global minimum.

	Moreover we get by definition of B that
	r -bz	√ rxy.
	Then McCormick relaxation is strictly included in B if and only if
		t y x t x y	√ rxy √ rxy
	⇐⇒	t y x t x t y xy rxy √ rxy
	⇐⇒	t y x t x t y r √ rxy


Laure Sarda

Shirley Carter-Thomas

Benjamin Fagard

Michel Charolles

Laure Adverbials

; Sarda

Carter-Thomas Shirley

Adverbials : from predicative to discourse functions

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

VERSION AUTEURS

Introduction Adverbials: from predicative to discourse functions

Laure Sarda 1 , Shirley Carter-Thomas 1,2 , Benjamin Fagard 1 , Michel Charolles 1,3 1 LATTICE, UMR 8094 CNRS & ENS, Paris, France 2 Institut Télecom, Télecom et Management SudParis (TMSP), France 3 Université Sorbonne Nouvelle, Paris, France

This book deals with adverbials and their relationships to discourse structure. In this volume, the term adverbial refers to an extremely heterogeneous category which does not coincide with the word class of adverbs. Adverbials are generally defined in the literature through their syntactic function. Formally, the notion of adverbials encompasses different grammatical categories: prepositional phrases (PPs), noun phrases (NPs), adverbs, and clauses. Functionally, these categories can appear at different levels of the sentence (either the intraclausal level or extra-clausal level). They are commonly distributed into three main types: adjuncts, disjuncts and conjuncts [START_REF] Quirk | A Comprehensive Grammar of the English Language[END_REF], also termed circumstance, stance and linking adverbials in [START_REF] Biber | Longman Grammar of Spoken and Written English[END_REF] or circumstantial, modal and conjunctive adjuncts in [START_REF] Halliday | An Introduction to Functional Grammar[END_REF]. As Downing & Locke (1992: 58) note: they "are optional elements which can be added or omitted without producing an ungrammatical clause". Referential meaning is basically the main property of adjuncts. Disjuncts have an evaluative function: they add a comment by the speaker/writer on the content of the clause as a whole; whereas the main property of conjuncts is connective: they express how the speaker/writer establishes the semantic connection between two utterances (cf. Downing & Locke 1992: 62-63;Hasselgård 2010: 19 ff.).

One of the main issues is to address the relationship between functions and positions of adverbials. As the above definitions clearly suggest, there is no straightforward correspondence between the two. For instance, initial position can host different types of adverbials, either adjuncts, disjuncts or conjuncts. It is therefore important to clarify how these different terms interrelate at the syntactic and functional level. It is also important to clarify to what extent these categories have also somewhat confusingly been encompassed under the umbrella term of Discourse Markers (DM). We propose to address the issue of the function/position correspondence from a syntactic point of view. We shall try to characterize these functions on a scale of integratedness: the more an adverbial is integrated to the predicate (intra-clausal status), the more it tends to function locally (in this case the boundary between argument and adjunct can be problematic), and conversely, the less it is integrated to the predicate (extra-clausal status), the more it tends to function globally, to acquire discourse-related functions, to have a wide scope, and to set up links with the foregoing and/or the subsequent text.

In the following, we propose an overview of discourse-structuring devices: besides classical cohesion devices such as anaphora and connectives (or conjuncts), the role of various adjuncts in initial position is crucial in organizing text in blocks of information. This will be developed in section 1. In section 2, we report on definitions of Discourse Markers trying to establish correspondences with the various categories of adverbials previously ascribed. We suggest making a distinction between Discourse Structure Markers (DSMs) and Intersubjective Discourse Markers (IDMs). DSMs establish links either backward (conjunct) or forward (adjunct). They set up connections with the preceding text or indexation on the subsequent text. IDMs, in contrast, do not link with linguistic elements before or after their host sentence. They help in conversation management or stance expression. They mainly include disjuncts and various particles, small words or interjections which do not straightforwardly participate in discourse structuring. After these theoretical adjustments, we will present the different chapters organized according to the degree of integratedness of the adverbials under study.

Discourse structuring devices: connection and indexation

Amongst the well-known cohesion tools which help turn a series of sentences into a text or a discourse, two main types of links (besides lexical cohesion) are usually taken into account: connectives and anaphora. They both encode interpretative instructions indicating the links to be established between their host sentence and the preceding text. Understandably, therefore, their use has been the main focus of research in the literature. They are indeed sometimes considered as the only two possible types of cohesive link, as in Reinhart (1980: 168):

The various devices for linking adjacent sentences in a discourse can be reduced to two types of links: the one is referential links (…). The other type of cohesive link is a semantic link between the propositions expressed by the two sentences (…). Any of these two types of link is sufficient to produce a cohesive discourse, and it is necessary that at least one of them will hold.

This line of argument is also followed by Sanders & Spooren (2001: 7):

Generally speaking, there are two respects in which texts can cohere: 1) Referential coherence: units are connected by repeated reference to the same object; 2) Relational coherence: text segments are connected by establishing coherence relations like CAUSE-CONSEQUENCE between them.

Connectives and anaphora complement each other in building a coherent representation of what is said. The example below illustrates how connectives (in bold case) and anaphora (in italics) work together. Both reinforce the cohesion of the excerpt:

(1) An ex-con sets out to avenge his brother's death (…). During his campaign, however, he's tracked by a veteran cop and an egocentric hit man.

(http://www.imdb.com/genre/action).

Despite this complementary quality, there are some fundamental differences between these two types of cohesion markers. Anaphoric expressions contribute to the propositional content of the statements in which they occur and are syntactically integrated. Connectives, on the other hand, signal links between the propositional content and/or illocutionary value of successive statements. They are not syntactically integrated into their host sentence and do not contribute to the truth-conditional interpretation of its propositional contents.

However, anaphora and connectives both establish relationships with the foregoing text. To this extent, they are considered here to belong to the same family of tools, in that they are both able to set up connection links. Another less well-known family of tools which provide a structure for the incoming text are indexation links [START_REF] Charolles | L'encadrement du discours: Univers, champs, domaines et espaces[END_REF][START_REF] Charolles | Framing adverbials and their role in discourse cohesion: From connection to forward labelling[END_REF]. As illustrated in the second section of the book (see in particular the chapters by Bestgen & Piérard and Virtanen), indexation links are typically expressed by adverbials found at the beginning of sentences. Amongst these, we frequently find prepositional phrases, especially temporal and spatial adverbials such as by the second half of the fourteenth century, in England and in France, as in the following example:

( The prepositional phrases (PP), in bold in this excerpt, refer to a specific place or time period within which the different situations reported take place. By the second half of the fourteenth century thus indexes all the situations taking place within the time range denoted by the PP. It opens a temporal frame (TF 1 ) whose scope extends beyond the host sentence to the whole paragraph. In the same way, In England opens a first spatial frame (SF 1 ) which is closed by the advent of the second spatial frame (SF 2 ), In France, which in turn indexes the remainder of the excerpt. This emerging structure can be schematized as follows: dimension and then a spatial one, to organize what he is going to say. This way of organizing textual content is hierarchical and restrictive to the extent that once a dimension of a situation has been introduced by an adverbial, it tends to remain in place. For instance, any new statement occurring at the end of the extract will be understood as occurring under the scope of SF 2 (In France) and thus of TF 1 (By the second half of the 14th century). Linking it to SF 1 (In England) under TF 1 would be impossible, unless In England is reintroduced, either in sentence-initial position which would then lead to the closing of SF 2 (In France) and the opening of new frame SF3 referring to the same place as SF 1 (In England), or in another position, in which case its contents would be simply indexed by the temporal frame TF 1.

This forward-oriented structuring device, which is frequent mostly in planned written texts, was first described by [START_REF] Thompson | Grammar and written discourse: Initial vs. final purpose clauses in English[END_REF] and more systematically detailed in [START_REF] Charolles | L'encadrement du discours: Univers, champs, domaines et espaces[END_REF][START_REF] Charolles | Framing adverbials and their role in discourse cohesion: From connection to forward labelling[END_REF] as Discourse Frames. This notion of frame is based on the hypothesis that only initially occurring adverbials have this 'framing' capacity. They are termed framing adverbials when they play this forward structuring role, extending their scope over several sentences following their host-sentence. Although perhaps debatable on some accounts (cf. Crompton 2006 and this volume), this hypothesis is supported by a series of corpus-based studies1 showing that prepositional adverbials are often used strategically on account of their framing potential [START_REF] Enkvist | A Parametric View of Word Order[END_REF]Virtanen 1992aVirtanen , 1992b, this volume), this volume). This is particularly true when they occur at the beginning of a paragraph, when they are used as a series and when they are announced by a trigger sentence. Chapter 6, by Bestgen & Piérard (this volume) provides additional experimental evidence showing that spatial prepositional phrases are not processed the same way in sentence-initial as in sentence-final position.

To sum up, we draw a major distinction between cohesion markers which a) establish connection links with the foregoing context (connectives and anaphora), and markers which b) establish indexation links with the ongoing text (framing adverbials) 2 . All these devices operate in a concerted way, facilitating access to a coherent interpretation of the discourse, as hearers/readers progressively become aware of it. Given the importance of piloting the processing of incoming utterances, the beginning of the sentence is clearly a strategic location to indicate in advance how the situations and the participants in these situations are connected with those previously mentioned, and what connects them with the incoming information.

In terms of integratedness, if we focus on this initial position, it appears that within this outlying zone there is also a continuum, to the extent that not all constituents are equally integrated, even though all are extra-clausal adverbials. On the very left of the continuum, there are full connectives (conjuncts), such as (for French) mais ('but'), car (causative 'since'), and on the very right (less detached than connectives because they carry ideational content) we find spatial and temporal framing adverbials (adjuncts). Between these two extremes, there are different types of framing adverbials, ranging from the more concrete and ideational to the more abstract and textual. Lamiroy & Charolles (forthcoming) have suggested the following classification: The main common property of these markers is that their indexing function is strictly dependent on their initial positioning. If they are placed at the end of the sentence, they have a local scope which does not exceed the host clause. For instance, if we reformulate excerpt (2), placing the three underlined prepositional phrases in sentence-final position, instead of their original initial position, the reader's processing of the sentence will be affected.

( grammaticalized, they are less bound to the initial position of the sentence. From a diachronic perspective, one interpretation could be that once the discourse function has become strongly associated with the use of an adverbial in initial position (i.e. once the adverbial has been grammaticalized with this function), it can be used as such in other positions, keeping its newly acquired discourse function. This is illustrated in the third section of this book, with chapters 8 (Fagard & Sarda) and 9 (Lewis): both present diachronic studies addressing different cases of shift from ideational to textual or interpersonal uses.

Discourse Markers revisited in the light of discourse structuring functions

We have tried to show that languages provide speakers with a vast array of tools that can be used to build up text or discourse cohesion, including anaphora, connectives and framing adverbials. To clarify the functions of adverbials, it is important not to bundle together those which serve to structure text (either conjunct or framing adverbials) and those which only express speaker attitude or modality. Speakers also have at their disposal various other kinds of expressions, which contribute to discourse meaning without being specifically dedicated to the setting up of links between successive utterances. Such expressions, which can be grammaticalized to various degrees, abound in discourse, both written and spoken4 , and are often referred to as discourse markers. This is [START_REF] Lakoff | Questionable answers and answerable questions[END_REF] term [START_REF] Müller | Discourse Markers in Native and Non-native English Discourse[END_REF]: 2-3), and also arguably the most popular term -along with e.g. discourse particles [START_REF] Schourup | Common Discourse Particles in English Conversation[END_REF][START_REF] Hansen | The Function of Discourse Particles[END_REF][START_REF] Aijmer | English Discourse Particles. Evidence from a Corpus (Topics in English Linguistics)[END_REF][START_REF] Fischer | Towards an understanding of the spectrum of approaches to discourse particles[END_REF]) and pragmatic markers [START_REF] Fraser | Pragmatic markers[END_REF]. 5 The existence of various competing denominations for these elements, which has been reported already on various occasions [START_REF] Schourup | Discourse markers[END_REF][START_REF] Müller | Discourse Markers in Native and Non-native English Discourse[END_REF]Fritz 2009: 3, etc.), is in fact indicative of different views on what a DM is and does.6 Indeed, DMs (or discourse particles, etc.) are not only given different names: they also receive various definitions -among (many) others, see Schiffrin (1987: 31, 323, 328), [START_REF] Hansen | The Function of Discourse Particles[END_REF], Fischer (2006a), Traugott (2007: 144), Waltereit & Detges (2007: 63), [START_REF] Fagard | Imperatives as discourse markers and grammaticalization paths in Romance: A diachronic corpus study[END_REF]; actually, defining DMs proves so complex that Jucker & Ziv (1998) see it as a prototypical category. As pointed out by Lewis (2011: 419-420):

There is little consensus on whether [Discourse Markers] are a syntactic or a pragmatic category, on which types of expressions the category includes, on the relationship of discourse markers to other posited categories such as connectives, interjections, modal particles, speaker-oriented sentence adverbials, and on the term 'discourse marker' as opposed to alternatives such as 'discourse connective' or 'pragmatic marker' or 'pragmatic particle'.

We propose below a working definition of DMs. The question of which elements should be included in the 'category' of DMs is essential, and depends of course on the definition given to this category (one can also wonder whether DMs pertain to a single class, cf. Schiffrin 1994: 40; Müller 2005: 3-4). We suggest including in the DM category only those elements that contribute to discourse management in some way, or elements which express the attitude of the speaker. Both have to do with the interpersonal sphere (cf. [START_REF] Halliday | An Introduction to Functional Grammar[END_REF]) and, though they do not have exactly the same function, share a number of distributional features, such as the capacity to be inserted in any position. Both are also likely to be intersubjective. On the other hand, elements which contribute to discourse structure by linking discourse segments should be termed differently because their main function is to connect propositional contents and structure text in blocks of information. They are less linked to the interpersonal/intersubjective sphere and more to the ideational and textual spheres. Even though many expressions are polyfunctional, most of them specialize in either discourse management and expressing stance, or in linking different textual segments logically or semantically.

Definitions of DMs usually amalgamate both linking and interaction functions. They mention the following features: (a) Syntactically, (i) they are extra-sentential and, as a result, (ii) they have a relatively free distribution (i.e. syntactic position; Schiffrin 1987: 31 ff.) although common clause-initially (Schiffrin 1987: 328;Aijmer 2002: 29), with specific prosodic contours, (iii) they have variable scope and/or attachment points. (b) Distributionally, they tend to cluster with other DMs or marks of subjectivity. (c) Semantically, they have a non-propositional meaning (Lenk 1997: 4): they do not contribute directly to the meaning and structuring of text and discourse, or not to the same degree as connectives.7 (d) Pragmatically, DMs operate at the discourse level: (i) they are used for discourse signaling and negotiation of ongoing discourse-related interaction such as stance expression and conversational management. DMs initiate discourse, mark a boundary (topic shift), are used as fillers, floor-holding devices, to mark fore-or backgrounded information… (see Müller 2005: 9 for a more exhaustive list). (ii) They also have text / discourse-structuring functions (e.g. linking functions, cf.

Fraser 1996): "Discourse marking refers to the explicit expression of the coherence relations (sometimes called discourse relations or rhetorical relations) that can hold between two ideas or groups of ideas" (Lewis 2011: 420); they indicate "the structural organization of the discourse" (Fritz 2009: 4), acting either on a local level, between adjacent utterances, or on a global level, between discourse segments further apart (Lenk 1997: 7).

The question is whether interactive uses (d/i) and linking uses (d/ii) point to different categories of markers, some specialized in spoken discourse and interaction (oh, well, I mean, y'know, etc.) and others in (spoken or written) discourse structure (but, and, or, so, because…), or simply to two different functions (see Schiffrin 1994: 31, who counts all these elements as DMs). This distinction has been seen as representing two ends of a continuum. According to Lenk, a global DM:

refers back to discourse that has occurred somewhat earlier, not immediately adjacent. Future research should investigate how far the scope of discourse markers that mark local coherence relations can reach, and whether discourse markers that are functional on a clearly local level of discourse and those that are functional on a clearly global level of discourse must be considered the extreme ends on a continuous scale of discourse structure markers. If this should be the case, local discourse markers probably represent one end of the continuum where utterance relations are marked, whereas global discourse markers represent the other end of the continuum where topic relations are marked. (Lenk 1998: 211;author's emphasis) This distinction partly overlaps with another distinction between turn-taking and textual functions, to which Fritz (2009: 10) adds a modal component: a) textual function: "topic-and content-related issues such as changing or introducing topics, introducing direct speech, etc."; b) turn-taking function: "concerned with the sequence of turns", including floorholding; c) modal component: "whenever attitudes and evaluations, or modifications of the illocutionary force of an utterance are concerned"; "for English, it is debatable whether it applies to discourse markers, depending on how they are defined".

It is in fact hard to distinguish clearly between these functions in single occurrences of DMs: the question, then, becomes "which of the functions is more dominant"? (Fritz 2009: 11; see also Aijmer 2002: 39). In our view, each candidate form specializes in one function or the other, and the markers with modal and conversation managing functions are clearly less oriented towards text or discourse cohesion.

Therefore, we suggest maintaining a clear functional distinction between markers which contribute to discourse structure by linking different segments, and markers that do not specialize in this structuring function but rather contribute to conversation management or provide information about speaker attitude. In Figure 3 below, we illustrate this distinction, placing horizontally, along the initial zone, the discourse structuring markers (DSMs) dedicated to signaling discourse links with the foregoing and the ongoing text; and orthogonally all other (Inter)subjective discourse markers (DMs), which do not directly contribute to this linking function. These distinctions partly map onto the classical classification of adverbials as conjuncts (connective DSMs), adjuncts (framing adverbials, DSMs) and disjuncts (IDMs). Discourse Structuring Markers thus range from connectives to framing adverbials. They contribute to discourse structure by organizing text segments and connecting/indexing them, and are therefore extremely sensitive to positioning: they must be in initial position in order to fulfill these connecting or indexing functions. This is especially true for the two ends of the continuum, namely for full connectives on the one hand, and for temporal and spatial framing adverbials on the other. By contrast, markers involved in conversation management, and more generally adverbials expressing stance, usually have a local scope and can be inserted in almost any position in the sentence, even though they are frequently found in a clause-initial position. This is the reason why we suggest calling them (Inter)subjective Discourse Markers, and conceptually represent them on an orthogonal axis.

The advantage of distinguishing between these two axes is that it facilitates the conceptualization of a polyfunctional occurrence as a vector in a three dimensional space. For instance, the expression au fond (literally 'at the bottom'; close to 'basically', 'ultimately' or 'in fact'), studied by Fagard & Sarda in this volume could be placed close to the function of stance but it also expresses to a certain extent a connection with the foregoing text or context, especially when it contrasts with a previous occurrence of markers such as apparemment ('apparently'), or à première vue ('at first sight'). It is thus oriented towards the function of connection. This vector is represented in Figure 4 This representation also shows that any (I)DM (more or less on the vertical axis) which can impact to a certain extent on the discourse structure (horizontal axis), generally tends to be oriented either towards the connection pole or towards the indexation pole.

An adverbial in initial position, if it has to do with discourse structuring, will probably specialize in one of the linking functions (connection vs. indexation) depending on its syntactic and semantic properties (cf. chapters 8 and 9). It will either look backwards or forwards, but it rarely does both at the same time.

The chapters in this volume mainly focus on Discourse Structuring Markers rather than on (Inter)subjective Discourse Markers. They offer an overview of how adverbials originate in the predicate zone and can acquire new discourse functions when used clause-initially.

The volume is organized according to the functions played by the adverbials: from the more integrated to the less integrated. We have seen that when their syntactic integration in the sentence is loose, these adverbials are more likely to appear in the periphery and consequently to fulfill discourse functions. There are basically two attractor zones for adverbials, the verb on the one hand and initial position on the other.

Presentation of chapters and degrees of integration of adverbials

This volume is divided into four sections. The ordering of these sections reflects the general movement we have described from more integrated to more detached adverbials. The chapters use different theoretical frameworks: experimental and formal approaches such as Segmented Discourse Representation Theory (SDRT), and cognitive-functional approaches including diachronic perspectives, Grammaticalization, Constructional Grammar and Cognitive Grammar. The first section deals with adverbials in the predicate zone and focuses on lexicalization or subjectification. It begins with a chapter by Catherine Fuchs, "A paradoxical case of locative inversion in French", in which the author investigates a specific type of sentence-initial adverbial in Modern French -a case of locative inversion with unexpected typographical markings. In these structures, the VS word order is preceded by a comma, whereas canonical locative inversions exclude the use of a comma. The author's hypothesis is that the presence of a comma indicates a specific type of text structuring phenomenon. In order to test this hypothesis, she analyzes in detail attested examples of locative inversions and points out the specificities of paradoxical locative inversions. She shows, for instance, that different kinds of restrictions have a bearing on the initial adverbial, the verb and the subject. Paradoxical locative inversion obeys a distinct text-structuring strategy, which the author terms "text priming" and which consists in the progressive constitution of a scene from a subjective point of view. The observed increase in the use of this strategy seems to reveal a phenomenon of subjectification in contemporary French writing.

This phenomenon of subjectification of initial spatial adverbials may not be restricted to French, since Tuomas Huumo, in his chapter entitled "Path Settings: How dynamic conceptualization permits the use of path expressions as setting adverbials" describes a similar tendency in Finnish. In a Cognitive Grammar framework, he investigates setting adverbials, focusing on path expressions. He first explains why path expressions, despite their dynamicity, can be used as setting adverbials in initial position. He then goes on to show that there are different types of path expressions; from the point of view of path construal, he explains why expressions of fictive motion are more subjective and have a greater autonomy with respect to the clause nucleus than canonical path expressions. He discusses three factors bearing on the conceptualization of the path as a setting and the autonomy of the path expression: the nature of the trajectory, the nature of the verb and the nature of the path expression itself.

The second section, "Initial positioning and text organization: A focus on indexing strategies", presents different viewpoints and different methodologies for evaluating the role of adverbial initial positioning in text structuring. It discusses whether the long distance scope of adverbials hinges on their initial positioning. An important issue is whether the initial position encodes in itself some instructions to process the subsequent information (and/or to connect them to what has been previously mentioned), and also whether it can be claimed that any adverbial occurring in this initial slot is specifically used to guide the reader/hearer.

Chapter 4, by Tuija Virtanen, is entitled "Sentence-initial adverbials in written texts: On discourse functions and cognitive motivations". The author investigates the text-structuring functions of sentence-initial adverbials in written English and French. In contradistinction to Peter Crompton in the following chapter, the author believes the initial slot has in itself cognitive potential for discourse organization, but stresses the fact that there is a complex interplay between this potential and various other motivations. Virtanen first studies the textstructuring functions of sentence-initial adverbials and their textual scope. She then investigates specifically the textual potential of the initial slot itself and shows (this time agreeing with Crompton's findings) that discourse boundaries have an impact on this textual potential, along with other signals of closure. Finally, she focuses on the interaction between the position of adverbials and text/discourse type or genre. She shows that these do indeed have an impact on adverbial position, and identifies potential genre markers among sentenceinitial adverbials.

Chapter 5, by Peter Crompton, is entitled "The positioning of adverbials: Discourse function reconsidered". The author investigates the role of sentence-initial position for adverbials in English, challenging the widely accepted view that initial position confers extended discourse scope. This study builds on earlier work [START_REF] Crompton | The effect of position on the discourse scope of adverbials[END_REF] where the author argued that there was no necessary relation between initial position and discourse scope, or final position and local scope. In his chapter, Crompton describes a new corpus-based study from the BNC (British National Corpus), investigating more closely two variables: the relation of adverbial position in the clause to paragraph-internal positioning and textual reference. The study shows that the most important factor for the extension of an adverbial's scope is not clause-initial but paragraph-initial position. Besides, the link to prior discourse seems to be only one of the motivations for initial positioning: the author shows that adverbial clauses can have backward scope irrespective of their position. The author concludes that positioning options of adverbials do not obey a single discourse motivation and suggests that discourse motivations compete with other discourse-independent factors.

Chapter 6, by Yves Bestgen & Sophie Piérard, is entitled "Sentence-initial adverbials and text comprehension". The authors investigate the impact of the position of adverbials on text comprehension with various experiments. They explain that, while linguists have long believed that the position of adverbials has an important role in text structuring, psycholinguists have until now mostly focused on mental representations of texts. They choose to combine these two lines of research, with a series of experiments designed to verify the existence of a link between the sentence position of temporal or spatial adverbials and text comprehension. In the first series of four experiments, the authors manipulate the position of an adverbial and the presence or absence of situational breaks in a narrative. The results confirm the predictions made by the authors: the reading time is longer for a new discourse unit, but the presence of a sentence-initial adverbial can cancel this effect. In a second series of experiments, the authors confirm that the sentence-initial position is indeed responsible for the segmenting function of adverbials, and also provide experimental evidence of their framing function.

The third section "From adverbials to discourse (structure) markers: which grammaticalization path?" presents case studies of various expressions at different stages of grammaticalization. Chapter 7 provides a synchronic study of a recent marker, highlighting two different uses that may represent the first step of a grammaticalization path. The following two chapters (8 and 9) are diachronic studies fully illustrating a grammaticalization path into (inter)subjective discourse markers or discourse structuring markers. They all address issues related to the polysemy and polyfunctionality of the studied expressions.

This section begins with a chapter by Myriam Bras & Catherine Schnedecker, entitled "The French adverbial dans un premier temps and Discourse Relations: From Elaboration to Contrast". Among ordinal adverbials such as premièrement ('firstly'), en premier lieu ('in the first place') and dans un premier temps ('in a first time') -which are usually described as markers that can order textual matter and that can be used to mark up texts -the authors investigate the use of the adverbial dans un premier temps. Drawing on a synchronic corpus study, they distinguish several uses of the adverbial on the basis of formal and semantic criteria. They show that this adverbial is an anaphoric expression that keeps its compositional semantics, ordering events rather than textual matter. They show that dans un premier temps is both retroactive and prospective, establishing backward links (based on a part-of relation between events) and forward links in discourse (based on a simple temporal succession or on an additional contrastive value). These links are analyzed within the SDRT framework, which reveals two major discourse configurations: either a purely temporal interpretation where the Elaboration of an explicit topic plays a central role; or an argumentative interpretation where a Contrast relation between the coordinated elaborating elements is associated with the relation of temporal succession present in the first configuration.

Chapter 8, by Benjamin Fagard and Laure Sarda, is entitled "From locative adverbial to discourse marker: Three case studies in the diachrony of French". The authors investigate the evolution of three adverbials into discourse markers: parallèlement ('parallel to'), au fond ('at the bottom') and d'un côté ('to one side'). These adverbials, which initially had locative uses, have evolved into discourse markers, with frequent sentence-initial use. The authors analyze their evolution within the framework of grammaticalization theory. The main theoretical question at stake in this chapter is whether the grammaticalization of discourse markers is driven by semantics or syntax. In order to answer this question, the authors present a corpus study of these markers. They show that the dichotomy between framing adverbials and discourse markers is partly linked to the referential properties of their components.

Chapter 9, by Diana Lewis, is entitled "Word order and the development of connective markers in English". The author investigates the formation of two discourse connectives, at least and instead, which both, like many other discourse connectives, originated as prepositional phrases. She describes the changes undergone from the original constructions to the modern discourse connectives, within a grammaticalization framework including Construction Grammar analyses. The aim of the study is to analyze in detail these changes, and evaluate the claim that they present a gradual evolution involving scope increase. On the basis of a corpus study on both historical and present-day English corpora, the author argues that both claims are valid, and goes on to show that Construction Grammar can be useful for describing the semantic changes involved. The author concludes that constructional meaning as well as information structure design have to be considered in order to account for word order change and scope change.

The fourth section, "Translation perspectives on adverbial clause positioning", brings an interesting and complementary insight to the debate on the function/position correlations. The two chapters in this last section contribute arguments that tend to relativize the claim that the initial position is cognitively set aside for fulfilling particular discourse functions. It is shown through aligned and parallel corpus studies that syntax and information structure interact and impact on the word order choice that can vary from one language to another. Competing motivations have to be taken into account in order to explain word order discrepancies across languages.

Chapter 10, by Bergljot Behrens & Kåre Solfjeld, is entitled "Discourse role guiding clause type and relative position in translation". The authors investigate the interplay between syntax and discourse structure, and in particular the weighting of the different information units. They compare English, German and Norwegian, languages which are rather alike in structure, but nevertheless display discrepancies in the way the hierarchical structure at the intrasentential level interacts with text-structuring discourse relations. Focusing on Background, a discourse relation in SDRT, the authors discuss the equivalence between alternative intrasentential combinations. In order to do so, they distinguish between the semantic contribution and discourse function of different clause types, and go on to discuss the discourse-functional contribution of intrasentential clause combinations. With the help of a parallel corpus study, they analyze a series of constraints on discourse relations and show that these can be overruled by syntactic downgrading and information structural principles.

Chapter 11, by Wiebke Ramm, is entitled "Discourse-coordinating or discoursesubordinating? The discourse function of clause-related relative clauses in a translation perspective". The author investigates the role of clause-related relative clauses in German. These hybrid structures, such as those introduced by the clause-initial relative adverb wobei, partake of subordinate and main clauses. They have specific propositional status and information structure, and their discourse properties are traditionally described as being 'continuative'. The author shows, on the basis of a corpus study, that the relation established by wobei clauses can actually be described, in SDRT, as an Elaboration relation. The corpus is a sentence-aligned collection of fictional and non-fictional German original texts and their Norwegian translations. This study leads the author to distinguish between different types of wobei-clauses, which depend on the temporal properties of the predicates, correlate to some degree with text type and are also influenced by the context, in particular the sentence following the relative clause.

The different chapters presented above provide a broad overview of the question of adverbials at the syntax/discourse interface, covering a variety of different languages: French, English, German, Norwegian and Finnish and using different frameworks such as Cognitive Grammar, Constructional Grammar, Grammaticalization Theory, experimental approaches and the more formal approach developed in Segmented Discourse Representation Theory (SDRT). They offer a rich insight into the functions linked to adverbial positioning. On the basis of these studies, we would like to defend the working hypothesis that the initial position itself plays a specific role in discourse cohesion, regardless of the components instantiated in that slot. Because of its particular cognitive status, the initial position codes instructions which (are there to) guide the interpretation of the reader. This could be described in terms of grammaticalization of the position, and may explain why the initial position tends to be a privileged locus for categorical changes and for the emergence of both (Inter)subjective Discourse Markers and Discourse Structuring Markers (connectives and framing adverbials).

We hope that the distinctions we have made will help better understand the complex interplay of competing motivations bearing on adverbial use in discourse.

Figure 1 .

 1 Figure 1. Emerging discourse structure with temporal and spatial frames

Figure 2 :

 2 Figure 2: Classification of Framing Adverbials on a scale of integratedness (from Lamiroy & Charolles (Forthcoming)).

Figure 3 :

 3 Figure 3: Distinguishing Discourse Structuring Markers (DSMs) from (Inter)subjective Discourse Markers ((I)DMs)

  Figure 4: Three-dimensional conceptualization of a polyfunctional expression

2) By the second half of the fourteenth century, few

	in France could claim not to be
	involved in it in one way or another. The effects on domestic politics were
	considerably and predictably different. In England, the needs of war (in terms of
	money and provisions) provoked a considerable crisis in the years 1338-41.
	Thereafter Edward III, having learned some valuable political lessons, was able to
	develop a far greater degree of co-operation with his people, in particular with the
	fighting nobility, a spirit fostered by the two outstanding victories won at Crécy
	and Poitiers. In France, by contrast, in spite of what seemed like early successes,
	the personal fortunes of both Philip VI and John II sank very low. Both met defeat
	and one suffered capture, thus becoming, in a very real sense, a national liability.
	The lack of strong leadership served to exacerbate these disasters, and the nobility
	of France was obliged to endure strong criticism for its failure to protect the
	kingdom and its people in their hour of need. (British National Corpus (BNC), The
	Hundred Years War. Allmand, 1991)

For English, see[START_REF] Quirk | A Comprehensive Grammar of the English Language[END_REF][START_REF] Lowe | Sentence initial elements in English and their discourse function[END_REF][START_REF] Downing | An alternative approach to theme: A systemic functional perspective[END_REF][START_REF] Prideaux | Markedness as a discourse management device: The role of alternative adverbial clause orders[END_REF]; for French, see Le Draoulec & Péry-Woodley

2001, 2003; Charolles & Prévost 2003; Vigier 2004; Vigier & Terran 2005; Charolles 2005; Charolles & Péry-Woodley 2005; Sarda 2005; Schrepfer-André 2006; Ho-Dac 2007; Ho-Dac & Péry-Woodley 2009; Sarda & Charolles 2009, and in a contrastive perspective, see Sarda & Carter-Thomas 2009.2 This opposition suggests a theoretical framework to point to different functions: linking backwards or linking forwards. The linking backwards function is mostly realized by markers establishing logical relations with the preceding text (conjuncts) whereas linking forwards functions are realized by markers establishing semantic relations (adjuncts). It is nevertheless important to keep in mind that many markers undergo changes in a grammaticalization process and can behave in between these two extremes. It is also important to consider that forwards linking markers can semantically set up an anaphoric link as for instance the expression dans un premier temps studied in chapter 7 by Bras & Schnedecker.

It is hard to say whether they are more frequent in spoken or written language, although it is usually considered that they are especially common in spoken language (see for exampleLenk 1998: 3).

This is confirmed not only bySchourup (1999: 224), but also by Google's spin-off Culturomics, as the reader can verify on the website <http://www.culturnomics.org/> with a search on all the denominations listed in the following footnote.

Other common terms include discourse organizers[START_REF] Pons Bordería | Los apelativos oye y mira o los límites de la conexión[END_REF], discourse particles[START_REF] Schourup | Common Discourse Particles in English Conversation[END_REF][START_REF] Fischer | Towards an understanding of the spectrum of approaches to discourse particles[END_REF]), discourse signals[START_REF] Lamiroy | Imperatives as discourse signals[END_REF], discourse connectives[START_REF] Erman | Pragmaticalization: The case of ba' and you know[END_REF], and pragmatic markers[START_REF] Fraser | Pragmatic markers[END_REF].

See Schiffrin (1994: 9): "Cohesive devices do not themselves create meaning; they are clues used by speakers and hearers to find the meanings which underlie surface utterances".


domain: math info

text:
Miguel Couceiro
email: miguel.couceiro@uni.lu

Didier Dubois
email: dubois@irit.fr

Henri Prade
email: prade@irit.fr

Agnès Rico
email: agnes.rico@univ-lyon1.fr

Tamás Waldhauser

General interpolation by polynomial functions of distributive lattices

For a distributive lattice L, we consider the problem of interpolating functions f : D → L defined on a finite set D ⊆ L n , by means of lattice polynomial functions of L. Two instances of this problem have already been solved. In the case when L is a distributive lattice with least and greatest elements 0 and 1, Goodstein proved that a function f : {0, 1} n → L can be interpolated by a lattice polynomial function p : L n → L if and only if f is monotone; in this case, the interpolating polynomial p was shown to be unique. The interpolation problem was also considered in the more general setting where L is a distributive lattice, not necessarily bounded, and where D ⊆ L n is allowed to range over cuboids D = {a1, b1} × • • • × {an, bn} with ai, bi ∈ L and ai < bi. In this case, the class of such partial functions that can be interpolated by lattice polynomial functions was completely described. In this paper, we extend these results by completely characterizing the class of lattice functions that can be interpolated by polynomial functions on arbitrary finite subsets D ⊆ L n . As in the latter setting, interpolating polynomials are not necessarily unique. We provide explicit descriptions of all possible lattice polynomial functions that interpolate these lattice functions, when such an interpolation is available.

Introduction and Motivation

The importance of aggregation functions is made apparent by their wide use, not only in pure mathematics (e.g., in the theory of functional equations, measure and integration theory), but also in several applied fields such as operations research, computer and information sciences, economics and social sciences, as well as in other experimental areas of physics and natural sciences. In particular, the use of aggregation functions has attracted much attention in decision theory for it provides an elegant and powerful formalism to model preference [START_REF]Decision-Making Process -Concepts and Methods[END_REF][START_REF] Grabisch | The application of fuzzy integrals in multicriteria decision making[END_REF] (for general background on aggregation functions, see [START_REF] Grabisch | Aggregation Functions. Encyclopedia of Mathematics and its Applications[END_REF]).

In the qualitative approach to decision making, Sugeno integral [START_REF] Sugeno | Theory of Fuzzy Integrals and its Applications[END_REF][START_REF] Sugeno | Fuzzy measures and fuzzy integrals -a survey[END_REF] remains one of the most noteworthy aggregation functions, and this is partially due to the fact that it provides a meaningful way to fuse or merge criteria within universes where essentially no structure, other than order, is assumed (unlike other classical aggregation functions, such as weighted arithmetic means, which require a rich arithmetical structure).

Even though primarily defined over real intervals, Sugeno integrals can be extended to wider domains (not only to arbitrary linearly ordered sets or chains, but also to bounded distributive lattices with bottom and top elements 0 and 1, respectively) via the notion of lattice polynomial function. Essentially, a lattice polynomial function is a combination of variables and constants using the lattice operations ∧ and ∨. As it turned out (see e.g. [START_REF] Couceiro | Characterizations of discrete Sugeno integrals as polynomial functions over distributive lattices[END_REF][START_REF] Marichal | Weighted lattice polynomials[END_REF]), Sugeno integrals coincide exactly with those lattice polynomial functions that are idempotent (that is, which preserve constant tuples); in fact, it can be shown that the preservation of 0 and 1 suffices.

Apart from their theoretical interest, the consideration of Sugeno integrals on distributive lattices (rather than simply on scales or linearly ordered sets) or on finite Boolean algebras [START_REF] Rico | Sugeno integral in a finite Boolean algebra[END_REF] is both useful and natural since scores for different criteria may be incomparable (for instance, when "ignorance" and "indifference" are possible scores). Now in many real-life situations, we are faced with the problem of finding an aggregation operation based on scarce data that are not sufficient to determine a unique function. This fact gives rise to an interesting problem that appears in complete analogy with the classical theory of real polynomial functions, namely, that of interpolation. In this paper we are interested on aggregation functions defined over lattices and thus we consider the problem of interpolating lattice functions f : L n → L on finite sets D ⊆ L n by means of Sugeno integrals or, more generally, by lattice polynomial functions.

The interpolation problem also has a learning flavor. The problem of covering a set of data by a set of Sugeno integrals, has been considered in the linearly ordered case [START_REF] Rico | Preference modeling on totally ordered sets by the Sugeno integral[END_REF][START_REF] Prade | Eliciting Sugeno integrals: Methodology and a case study[END_REF]. More precisely, the condition of existence of a Sugeno integral interpolating a set of data has been laid bare, and the set of solutions (when non-empty) has been characterized as being upper and lower bounded by particular Sugeno integrals (easy to build from data). This process has been shown to be closely related to the version space approach in learning [START_REF] Prade | Elicitation of Sugeno Integrals: A version space learning perspective[END_REF]. The theorems presented in this paper generalize these results to the more general case of partially ordered scales, and also open the possibility of the elicitation of families of generalized Sugeno integrals from, e.g., pieces of data where local and global evaluations may be imprecisely known.

The paper is organized as follows. In Section 2 we recall basic notions and terminology, provide the preliminary results needed throughout the paper, and address the interpolation problem we shall be dealing with. As it will become clear, a solution to this problem (when it exists) is not necessarily unique. Thus we present in Section 3 necessary and sufficient conditions for the existence of such a solution and, as a by-product, describe all possible solutions. Moreover, by confining ourselves to linearly ordered sets, we derive previous results obtained in this restricted setting. In Section 4 we address problems left open, and in Section 5 we discuss possible applications of our results.

Preliminaries

Throughout this paper let L be a distributive lattice. Recall that a polynomial function over L is a mapping p : L n → L that can be expressed as a combination of the lattice operations ∧ and ∨, projections and constants.

In the case when L is bounded, i.e., with a least and a greatest element (which we denote by 0 and 1, respectively), Goodstein [START_REF] Goodstein | The Solution of Equations in a Lattice[END_REF] showed that polynomial functions p : L n → L coincide exactly with those lattice functions that can be represented in disjunctive normal form (DNF for short) by

p (x) = I⊆[n] c I ∧ i∈I x i , where x = (x 1 , . . . , x n ) ∈ L n . 5 (1)
Furthermore, by taking c * I := J⊆I c J , we also have

p (x) = I⊆[n] c * I ∧ i∈I x i ,
and thus we can assume that the coefficients c I are monotone in the sense that c I ≤ c J whenever I ⊆ J. Under this monotonicity assumption we can recover the coefficients of the DNF from certain values of the polynomial function p. To this extent, for each

I ⊆ [n], let 1 I be the tuple in L n whose i-th component is 1 if i ∈ I and 0 if i / ∈ I.
In this way, p (1 I ) = c I . These facts are reassembled in the following theorem, which asserts in particular that polynomial functions are uniquely determined by their restrictions to the hypercube {0, 1} n .

Theorem 1 (Goodstein [5]

). Let L be a bounded distributive lattice, and let f be a function f : {0, 1} n → L. There exists a polynomial function p over L such that p| {0,1} n = f if and only if f is monotone. In this case p is uniquely determined, and can be represented by the DNF

p (x) = I⊆[n] f (1 I ) ∧ i∈I x i .
Goodstein's theorem can be seen as a solution to an instance of the Interpolation Problem (see below), namely, interpolation on the hypercube D = {0, 1} n : a function f : {0, 1}

n → L can be interpolated by a polynomial function p : L n → L if and only if f is monotone, and in this case p is unique.

This result was generalized in [START_REF] Couceiro | A generalization of Goodstein's theorem: interpolation by polynomial functions of distributive lattices[END_REF] by allowing L to be an arbitrary (possibly unbounded) distributive lattice and by considering functions f : D → L, where

D = {a 1 , b 1 } × • • • × {a n , b n } with a i , b i ∈ L and a i < b i , for each i ∈ [n]
. Let e I be the "characteristic vector" of I ⊆ [n] (i.e., the tuple e I ∈ L n whose i-th

component is b i if i ∈ I and a i if i / ∈ I).
The task of finding a polynomial function (or rather all polynomial functions) that takes prescribed values on the tuples e I can be regarded as yet another instance of the Interpolation Problem. In [START_REF] Couceiro | A generalization of Goodstein's theorem: interpolation by polynomial functions of distributive lattices[END_REF], necessary and sufficient conditions were established for the existence of an interpolating polynomial function. Moreover, it was shown that in this more general setting, uniqueness is not guaranteed, and all possible interpolating polynomial functions were provided, thus settling the Restricted Interpolation Problem.

Restricted Interpolation Problem

In this paper we extend these results by solving the following general interpolation problem.

Interpolation Problem Let L be a distributive lattice. Given an arbitrary finite set D ⊆ L n and f : D → L, find all polynomial functions p :

L n → L such that p| D = f .

Main results

Let D ⊆ L n be a finite set, and consider a partial function f : D → L. In this section we provide necessary and sufficient conditions that guarantee the existence of a polynomial function p : L n → L that interpolates f , that is, p| D = f . As a by-product, we will determine all possible interpolating polynomial functions over a natural extension of the distributive lattice L which we now describe.

By the Birkhoff-Priestley representation theorem, we can embed L into a Boolean algebra B; see, e.g., [START_REF] Davey | Introduction to Lattices and Order[END_REF]. For the sake of canonicity, we assume that L generates B; under this assumption B is uniquely determined up to isomorphism. The boundary elements of B will be denoted by 0 and 1. This notation will not lead to ambiguity since if L has a least (resp. greatest) element, then it must coincide with 0 (resp. 1). The complement of an element a ∈ B is denoted by a : a ∨ a = 1 and a ∧ a = 0.

Given a function f : D → L, we define the following two elements in B for each I ⊆ [n]:

c - I := a∈D f (a) ∧ i / ∈I a i and c + I := a∈D f (a) ∨ i∈I a i .
Observe that I ⊆ J implies c - I ≤ c - J and c + I ≤ c + J . Let p -and p + be the polynomial functions over B given by these two systems of coefficients:

p -(x) := I⊆[n] c - I ∧ i∈I x i and p + (x) := I⊆[n] c + I ∧ i∈I x i .
As it will become clear, p -and p + are the least and greatest polynomial functions over B whose restriction to D coincides with f (whenever such a polynomial function exists). First, we need to establish a few auxiliary results.

Given I ⊆ [n] and a = (a 1 , . . . , a n ), x = (x 1 , . . . , x n ) ∈ B n , let x a I be the n-tuple whose i-th component is a i if i ∈ I, and x i otherwise. If I = {i}, then we write x ai i instead of x a I .

Lemma 1. Let p : B n → B be a polynomial function over B. For I ⊆ [n] and x ∈ B n , the polynomial functions q - I and q + I given by

q - I (a) := p(x a I ) ∧ i∈I a i and q + I (a) := p(x a I ) ∨ i∈I a i , are nonincreasing.
Proof. Since monotonicity is defined componentwise, to show that q - I is nonincreasing it suffices to consider the case when I is a singleton.

So let I = {i} and a ∈ B n . In this case, p(x a I ) can be regarded as a unary polynomial function and thus, by [START_REF]Decision-Making Process -Concepts and Methods[END_REF], it is of the form s ∨ (a i ∧ t), for some s ≤ t. Hence, q - I can be expressed as

q - I (a) = s ∨ (a i ∧ t) ∧ a i .
By distributivity, we get q - I (a) = s ∧ a i , which shows that the first claim holds. The second claim follows dually, and the proof of the lemma is complete.

p(1 I ) ≥ p(b) ∧ i ∈I b i ≥ p(a) ∧ i ∈I a i .
This shows that the second claim holds; the first follows similarly.

⊓ ⊔

Using Corollary 1, we can now provide necessary conditions on the coefficients of interpolating polynomials. To show that this condition is also sufficient, we make use of the following lemma.

Lemma 3. Let f : D → L be a function defined on a finite set D ⊆ L n . Then p -(b) ≥ f (b) ≥ p + (b), for every b ∈ D.
Proof. By definition of p -and using the fact that for each I ⊆ [n],

c - I = a∈D f (a) ∧ i / ∈I a i ≥ f (b) ∧ i ∈I b i , we have p -(b) = I⊆[n] c - I ∧ i∈I b i ≥ I⊆[n] f (b) ∧ i ∈I b i ∧ i∈I b i = f (b) ∧ I⊆[n] i ∈I b i ∧ i∈I b i .
By repeated application of distributivity, it is not difficult to verify that

I⊆[n] i ∈I b i ∧ i∈I b i = 1,
and thus p -(b) ≥ f (b). Dually, we can also verify that f (b) ≥ p + (b), which completes the proof.

⊓ ⊔

We can now characterize the class of functions over a distributive lattice L that can be interpolated on finite domains by polynomial functions over the Boolean algebra generated by L. In fact, the following theorem explicitly determines all possible interpolating polynomial functions, whenever such polynomial functions exist. Theorem 2. Let f : D → L be a function defined on a finite set D ⊆ L n , and let p : B n → B be a polynomial function over B given by [START_REF]Decision-Making Process -Concepts and Methods[END_REF]. Then the following conditions are equivalent:

1. p interpolates f , i.e., p| D = f ; 2. c - I ≤ c I ≤ c + I ; 3. p -≤ p ≤ p + .
Proof. Clearly, (2)⇐⇒ [START_REF] Couceiro | A generalization of Goodstein's theorem: interpolation by polynomial functions of distributive lattices[END_REF]. By Lemma 2, (1) =⇒ [START_REF] Couceiro | Characterizations of discrete Sugeno integrals as polynomial functions over distributive lattices[END_REF]. Moreover, if (3) holds, then using Lemma 3 we conclude that for every b ∈ D,

f (b) ≤ p -(b) ≤ p(b) ≤ p + (b) ≤ f (b). Hence, p| D = f . ⊓ ⊔
From Theorem 2 it follows that a necessary and sufficient condition for the existence of a polynomial function p :

B n → B such that p| D = f is c - I ≤ c + I ,
cl (b 1 ∨ b 2 ) = cl (b 1 ) ∨ cl (b 2 ) and int (b 1 ∧ b 2 ) = int (b 1 ) ∧ int (b 2 ) .
Using this fact, the necessary and sufficient condition given above for the existence of an interpolating polynomial function over L can be translated into the following system of inequalities. In the case when L is a finite chain, a solution to the Interpolation Problem was given in [START_REF] Rico | Preference modeling on totally ordered sets by the Sugeno integral[END_REF] and where, rather than polynomial functions, the interpolating functions were assumed to be Sugeno integrals, i.e., idempotent polynomial functions; see [START_REF] Marichal | On Sugeno integral as an aggregation function[END_REF][START_REF] Marichal | Weighted lattice polynomials[END_REF].

Now if L is a finite chain, then cl(c - I ) = {f (a) : a ∈ D, ∀i / ∈ I, a i < f (a)}, and int(c + I ) = {f (a) : a ∈ D, ∀i ∈ I, a i > f (a)}. Hence, cl(c - I ) ≤ int(c + I ) if and only if for every a, b ∈ D, f (a) > f (b) ⇒ ∃i / ∈ I : a i ≥ f (a) or ∃i ∈ I : b i ≤ f (b) . ( 2
)
It is not difficult to see that condition (2) holds for every I ⊆ [n] if and only if condition (3) (see theorem below) also holds. The following result basically reformulates Theorem 3 of [START_REF] Rico | Preference modeling on totally ordered sets by the Sugeno integral[END_REF] in the language of lattice theory.

Theorem 3 ([11]

). Let L be a finite chain, and let f : D → L be a function defined on a finite subset D ⊆ L n . Then there exists a polynomial function p :

L n → L such that p| D = f if and only if ∀a, b ∈ D : f (a) > f (b) ⇒ ∃i ∈ [n] : b i ≤ f (b) < f (a) ≤ a i . ( 3
)

Further work

When we consider a function f : D → L, a polynomial function can be indentified if and only if for every I ⊆ [n] there exists c I ∈ L such that c - I ≤ c I ≤ c + I . In some practical cases this condition would be not satisfied, i.e., the data would be inconsistent with respect to a polynomial function. In such a case one issue can be to build a family of polynomial functions as it is done in the totally ordered context in [START_REF] Prade | Eliciting Sugeno integrals: Methodology and a case study[END_REF]. More precisely, a partition of the dataset can be built in which each set of the partition is compatible with a family of polynomial functions. In general, many partitions are possible since their definition without other conditions depends on the order in which the data are considered. We can add a condition to choose one partition. For example, we can decide to look for the smallest partition in terms of number of subsets. The complexity to check the conditions c - I ≤ c + I for all I ⊆ [n] is at least 2 n , so these conditions become costly when n increases. In the totally ordered context presented in [START_REF] Rico | Preference modeling on totally ordered sets by the Sugeno integral[END_REF] the complexity can be reduced since the check only needs p 2 comparisons of compatibility where p is the cardinality of D. This raises the question of finding a similar result in our context.

Applications and concluding remarks

To replace missing data is a common problem for the statistical treatment of data. There are many methods to give a value to the missing data. On the other hand, Sugeno integral is classically used in decision theory to represent the behavior of a decision-maker. Since polynomials functions are a generalization of Sugeno integrals, it seems natural to make use of these polynomial functions to replace the missing data.

  Given D := e D I : I ⊆ [n] and a function f : D → L, find all polynomial functions p : L n → L such that p| D = f .

⊓ ⊔ Corollary 1 .

 1 Let p : B n → B be a polynomial function over B. For every I ⊆ [n] and a ∈ B n , p(1 I ) ≤ p(a) ∨ i∈I a i and p(1 I ) ≥ p(a) ∧ i ∈I a i . Proof. Let b = a 0 [n]\I ; clearly, a, 1 I ≥ b. Since p is nondecreasing, we have p(1 I ) ≥ p(b), and since b i = 1 for every i ∈ [n] \ I, it follows from Lemma 1 that

Lemma 2 .

 2 Let f : D → L be a function defined on a finite set D ⊆ L n , and let p : B n → B be a polynomial function over B given by (1). If p| D = f , then c - I ≤ c I ≤ c + I . Proof. Suppose p| D = f . By Corollary 1, for every I ⊆ [n] and a ∈ D, p(a) ∧ i ∈I a i ≤ p(1 I ) ≤ p(a) ∨ i∈I a i . Since p(a) = f (a), for every a ∈ D, it follows that a∈D f (a) ∧ i ∈I a i ≤ p(1 I ) ≤ a∈D f (a) ∨ i∈I a i , and hence c - I ≤ c I ≤ c + I as desired. ⊓ ⊔

  for every I ⊆ [n]. Moreover, if for every I ⊆ [n], there is c I ∈ L such that c - I ≤ c I ≤ c + I , then and only then there is a polynomial function p : L n → L such that p| D = f . The latter condition leads us to considering the case when L is a complete lattice (i.e., for which arbitrary joins and meets exist), and to defining two operators cl and int as follows: For b ∈ B, let cl (b) := x∈Lx≥b x and int (b) := x∈Lx≤b x. It is not difficult to see that for any b 1 , b 2 ∈ B, we have

Corollary 2 .Remark 1 .

 21 If L is complete, then there is a polynomial function p : L n → L such that p| D = f if and only if for every I ⊆ [n] there is c I ∈ L such that c - I ≤ c I ≤ c + I or, equivalently, cl(c - I ) = a∈D cl f (a) ∧ i / ∈I a i ≤ a∈D int f (a) ∨ i∈I a i = int(c + I ), for every I ⊆ [n]. Corollary 2 generalizes Theorem 10 in [3] which established necessary and sufficient conditions for the existence of a solution of the Restricted Interpolation Problem.

As usual, the empty meet has value 1 and, dually, the empty join has value 0.

Acknowledgments. The first named author is supported by the internal research project F1R-MTH-PUL-09MRDO of the University of Luxembourg. The fifth named author acknowledges that the present project is supported by the T ÁMOP-4.2.1/B-09/1/KONV-2010-0005 program of the National Development Agency of Hungary, by the Hungarian National Foundation for Scientific Research under grants no. K77409 and K83219, by the National Research Fund of Luxembourg, and cofunded under the Marie Curie Actions of the European Commission (FP7-COFUND).