Gabriel Volte
email: volte@lirmm.fr

Eric Bourreau
email: bourreau@lirmm.fr

Rodolphe Giroudeau
email: giroudeau@lirmm.fr

Olivier Naud
email: olivier.naud@irstea.com

Exact method approaches for the differential harvest problem

Keywords: Column generation, Enumeration technique, Constraints programming, Exact method, Precision agriculture

The trend towards a precise, numerical, and data-intensive agriculture brings forward the need to design and combine optimization techniques to obtain decision support methodologies that are efficient, interactive, robust and adaptable. In this paper, we consider the Differential Harvest Problem (DHP) in precision viticulture. To tackle this problem, we dedicated a specific column generation approach with enumeration techniques and a constraint programming model. Therefore, a set of simulated instances (which differ in field shape, zone shape, and size) was created to perform a parametric study on our different approaches. The specific column generation approach presented in this paper is preliminary work in the development path of more sophisticated resolution methods such as robust optimization and column generation/constraint programming hybridization.

Problem description

The Differential Harvest Problem, introduced by [START_REF] Briot | A constraint-based approach to the differential harvest problem[END_REF], consists of optimizing harvests of different grape qualities in vineyards so that we obtain a certain quantity, denoted by Rmin, of good quality grapes. In the problem, there are only two types of grape quality: A-grapes and B-grapes (let us assume that A-grapes are of better quality than B-grapes).

Thanks to agronomic information obtained a priori, it is possible to map (see Figure 1) a vineyard by distinguishing areas according to the quality of the grapes. Meanwhile, geolocated harvesting machines equipped with two hoppers (harvest tanks with a maximum load of CapaM ax) are able to use such a map. When one of the two hoppers is full, both must be emptied into a bin located at the edge of the plot. These machines have two harvesting modes, that can be changed only when they are emptying the hoppers at the bin, the selective mode, and the non-selective mode. The selective mode corresponds to sorting good grapes quality in one hopper and other grapes in the second hopper. When the Rmin quantity of A-grapes is harvested in the selective mode the machine can change to the non-selective mode where the loading capacity is perfectly handled (cf. Figure 2). There is a technical issue with the harvesting machine which is related to the longitudinal size of its picking head of the harvester. This size is almost the length of wheelbase, approximately 5 meters. This problem occurs during zone changes and more particularly during the change from a zone with B-grapes to a zone with A-grapes, let us note this change BA (AB for the change from zone A to B).

When a BA transition occurs, three cases can be isolated (see Figure 3):

case a), the machine head has just entered zone A. The harvesting hopper (which is hopper B) cannot be changed to hopper A because it is still harvesting B-grapes and therefore hopper A would be corrupted with B-grapes. -In case b), the grape picker is overlapping both zones. The reasoning is the same as in case a) because we are still harvesting B-grapes.

-In case c), the harvester is completely in zone A, we no longer harvest Bgrapes. The harvesting hopper can, therefore, be changed from hopper B to hopper A to harvest the A-grapes in hopper A.

When changing from AB, the harvesting hopper is changed from hopper A to hopper B as soon as the area transition has occurred, avoiding the corruption of A-grapes with B-grapes.

Any row r is composed with a succession of BA and AB transitions, this leads to these four following row representations (consecutive A or B can be merged):

r = (AB) * and its symmetric r = (BA) * . One can observe that in this row composition the difference between the number of BA transition when harvesting in the different directions is exactly one. r = (AB) * A and its symmetric r = (BA) * B. In this configuration, the number of BA-transitions is the same in either direction.

Depending on the row configuration and the row direction the latency causes an asymmetry in the harvested quantities, therefore in the optimization part, we will need to determine the direction of each row to obtain the Rmin quantity.

For the sake of simplicity, the vineyard rows extremities are oriented upper to bottom, the upper extremity can be chosen arbitrarily. The article is organized as follows: the first section 1 gives the context of this work and provides the problem definition. The second section 2 refers to the previous and related works on the problem. In section 3 we introduce a new graph model and decide to provide models for two exact methods; first a column generation approach (see subsection 3.1) then a constraint programming model (see subsection 3.2). In the section 4 we outline the results obtained with our different approaches.

Related Works

Precision agriculture is a principle of agricultural parcel management that aims to optimize yields and investments, by seeking to take better account of the variability of environments. In [START_REF] Robert | Precision agriculture: a challenge for crop nutrition management[END_REF], the authors asserted that precision farming was the future of crop nutrition offering benefits in crop quality, sustainability, food safety, etc. A few years later, [START_REF] Mcbratney | Future directions of precision agriculture[END_REF] reviewed some precision agriculture advances and proposed new directions of research. [START_REF] Reichardt | Adoption and future perspective of precision farming in germany: results of several surveys among different agricultural target groups[END_REF] analyzed the adoption of precision agriculture technologies for several actors in the agricultural industry.

In the last decades, a lot of works was performed in digital and precision agriculture using operation research techniques involved in the resolution of vehicle routing problems, scheduling problems or stochastic problems.

The surveys [START_REF] Bochtis | The vehicle routing problem in field logistics part i[END_REF] and [START_REF] Bochtis | The vehicle routing problem in field logistics: Part ii[END_REF] assert that most of the agricultural applications involve the motion of machines hence they first classify the agricultural field operations which can be modeled as a vehicle routing problem. They present an approach to represent the planning and scheduling of moving machines as a vehicle routing problem with time windows where the machine has to process deterministic, stochastic or dynamic requests.

VRP-specific optimization methods are addressed in [START_REF] Seyyedhasani | Reducing field work time using fleet routing optimization[END_REF] to solve their fleet routing problem, they have reduced the operating time by at most 17.3% using their approach rather than a human-made solution.

One can find some works on-field coverage problem [START_REF] Plessen | Partial field coverage based on two path planning patterns[END_REF][START_REF] Burger | Complete field coverage as a multivehicle routing problem[END_REF], where the goal is to cover a field under technical constraints. The purpose of the work presented in [START_REF] Plessen | Partial field coverage based on two path planning patterns[END_REF] is to reduce the soil compaction. Smaller vehicles are used to cover the fields but those vehicles have smaller storage capacity. Thus the full field coverage in a single run is no longer possible and a path planning strategy is used to partially cover the field under compacted area minimization constraints. In comparison, the article [START_REF] Burger | Complete field coverage as a multivehicle routing problem[END_REF] focuses both on finding minimal operating cost and on balancing the vehicle's workload.

The paper [START_REF] Robert | A stochastic dynamic programming approach to analyze adaptation to climate change-application to groundwater irrigation in india[END_REF] explores the consequence of groundwater resource use under climate change scenarios. The problem is modeled as a dynamic stochastic problem with several temporal decision stages with multiple sources of risk that should impact farmer decisions.

Investment behavior under different policy and price scenarios was studied in [START_REF] Viaggi | An integer programming dynamic farmhousehold model to evaluate the impact of agricultural policy reforms on farm investment behaviour[END_REF]. They employ a dynamic multi-objective farm-household integer programming model on a northern Italy case study application highlighting the potentialities and the limits of the methodology applied.

A column generation approach is used to solve a crop rotation scheduling problem to produce a pre-determined demand for crops while respecting some ecological production constraints, this problem is called the sustainable vegetable crop demand-supply problem [START_REF] Santos | Sustainable vegetable crop supply problem[END_REF].

In few available literature, the DHP has been solved with methods based on Constraint Programming (CP), first a step model was proposed in [START_REF] Briot | Integration of operational constraints to optimize differential harvest in viticulture[END_REF] where they were able to optimally solve a 16 rows instance in 6 days, then a precedence model was introduced [START_REF] Briot | A constraint-based approach to the differential harvest problem[END_REF] which gives better results yet instances with 14 rows reach the 2 hours time limit, and Cost-Optimal Reachability Analysis [START_REF] Saddem Yagoubi | New approach for differential harvest problem: The model checking way[END_REF] (CORA, which is a model-checking techniques branch) finding optimal solution on vineyards with up to 12 rows in few minutes.

Models

We propose a new graph model of the problem that we call the "flatten" representation of the vineyard (extremities are merged to consider only the rows) in opposition with the "physical" representation of the vineyard (rows are split into two extremities) used by [START_REF] Briot | A constraint-based approach to the differential harvest problem[END_REF] and [START_REF] Saddem Yagoubi | New approach for differential harvest problem: The model checking way[END_REF]. Let n be the number of rows, CapaM ax be the hoppers capacity, Rmin the minimum A-grapes quality needed to be harvested, b be the bin/depot, an undirected weighted complete graph G = (V, E) with labeled edges, V = {0, . . . , n} ∪ {b} and E = {(i, j, k)|i, j ∈ V 2 , k ∈ {0, 1}} (k refers to the row harvest direction see Figure 4). Taking the edge (i, j, k) means that the vehicle moves from row i to row j harvesting row i with direction k, if k = 0 the row is harvested from top to bottom, otherwise the row is harvested from bottom to top. Let say D is the weight of G computed from a distance matrix. It must be noted that because the vehicle has an important turning radius, the distance between rows are not exactly euclidean. qA/qB are the two harvesting functions:

(i, k) → N, i ∈ V, k ∈ {0, 1}.
The goal is to find a set of disjoint routes (except for the bin b), respecting the CapaM ax capacity, covering V and minimizing the harvesting time (here the distance) while harvesting at least Rmin quantity of A-grapes.

This problem can be seen as a Heterogeneous Vehicle Routing Problem [START_REF] Toth | The vehicle routing problem[END_REF] with two resource constraints (the grapes quality, A and B) and two vehicle types (one selective and the other non-selective) with different capacities. If the vehicle is selective the harvested grapes are sorted according to their quality, thus the vehicle has two hoppers each with a capacity equal to CapaM ax, otherwise both grapes quality are mixed in both hoppers, therefore, the vehicle hoppers can be merged into only one hopper with a capacity 2 * CapaM ax. Let us consider γ the number of selective vehicles and λ the total number of vehicles. The following bounds are easy to verify:

Rmin CapaM ax ≤ γ ≤ n and Qtot 2 * CapaM ax ≤ λ ≤ n
Qtot refers to the total amount of grapes presents in the vineyard. Previous works on the problem tackled it with constraint programming and model checking. We would like to investigate integer linear programming and more precisely column generation to observe the effectiveness of these techniques on the DHP. As early preliminary work, we tried to solve this problem with integer linear programming models and out-of-the-box solving methods. Because this was unsuccessful, we concluded that column generation techniques should be used here. The following subsection 3.1 explains the use of these techniques on the DHP. We identified that the principal weakness of the constraint programming approach used previously was to introduce a new global constraint that specifically fits the DHP. To avoid this, we decided to focus on designing constraint programming models and decision strategies that suit the most to our problem while using state-of-the-art generic constraints. We dedicate the subsection 3.2 to highlight our constraint programming approaches.

The column generation approach

We use Dantzig-Wolfe decomposition [START_REF] George | Decomposition principle for linear programs[END_REF] on the DHP to obtain a set partitioning master problem with a side constraint which is the Rmin constraint and an elementary shortest path with resource constraints pricing problem.

Let us denote Ω the set of all feasible routes. The master problem selects routes in Ω to obtain at least the Rmin quantity. For the sake of memory usage, only solving the master problem, restricted to a subset R of Ω, is worth considering because the number of routes in Ω grows exponentially with the number of rows. Assume R ⊂ Ω is the set of feasible routes R = (R s ∪ R s ), with R s be the set of non-selective routes and R s be the set of selective routes. Selective routes must be generated independently of the non-selective routes, they use vehicle types with different capacities and resources consumption, therefore two pricing problems will be needed, one to generate selective routes and the other to generate non-selective routes.

Despite the classical branch-and-price scheme to VRP, we decided to opt for an enumeration technique [START_REF] Baldacci | An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts[END_REF]. There are several works on enumeration (see [START_REF] Laurence | Integer and combinatorial optimization[END_REF][START_REF] Poullet | Ground staff shift planning under delay uncertainty at air france[END_REF][START_REF] Baldacci | An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts[END_REF][START_REF] Contardo | A new exact algorithm for the multi-depot vehicle routing problem under capacity and route length constraints[END_REF] for more details). The enumeration technique operates as follows. First, the relaxation of the restricted master problem is solved, like if we were solving the root node with branch-and-price, to obtain the linear relaxation optimal value z * M P . With the last solved master problem special dual costs are obtained, denoted by CR * . Then any integer solution gives an upper bound z IP . These bounds and the dual costs are provided to a specific pricing problem which will generate all columns with a reduced cost of 0 < z IP -z * M P = . If we solve the new restricted master problem, this time without the linear relaxation, the solution obtained is optimal for the restricted master problem and thus for the master problem. The principal drawback of this technique is that too many columns may be generated if the linear relaxation of the restricted master problem is of poor quality, the gap with any integer solution would be too large.

Let us define the restricted master problem decision variables:

∀r ∈ R s , y s r = 1 if non-selective route r is used 0 otherwise ∀r ∈ R s , y s r =
1 if selective route r is used 0 otherwise Note a ir = 1 if row i is harvested in the route r, 0 otherwise. Let q t r be the quantity of t-grapes collected in the route r and c r the cost of the route r (total traveled distance computed from the weight matrix D). The route cost is the total traveled distance on the route. A non-selective route does not harvest A-grapes, all grapes are mixed in B-grapes.

Model M1: Restricted Master Problem Min r∈R (y s r + y s r )c r (1) r∈R (y s r + y s r )a ir = 1 ∀i ∈ V [π i ] ( 2
)
r∈R s q A r y s r ≥ Rmin [θ] (3)
y s r ∈ {0, 1} ∀r ∈ R s (4)
y s r ∈ {0, 1} ∀r ∈ R s (5)
The aim is to minimize the cost of each route (1) while the entire field is harvested [START_REF] Bochtis | The vehicle routing problem in field logistics part i[END_REF]. The constraint (3) verifies that at least the Rmin quantity of good quality grapes is harvested. And finally, the constraints (4) and ( 5) ensure the integrality of the y variables.

Pricing sub-Problem The pricing problem generates improving routes for the master problem based on the value of the constraints in the dual solution of the restricted master problem.

We solve the pricing problem, a shortest path problems with resource constraints, with dynamic programming using a labeling algorithm, introduced first by [START_REF] Irnich | Shortest path problems with resource constraints[END_REF], enhanced by [START_REF] Feillet | An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems[END_REF]. We adjusted this algorithm to our two pricing problems. Because extension and dominance rules are straightforward from the original, we decided not to reintroduce them in this paper. The only originality in our label algorithm is that two labels lists are used. One list, L 0 , for labels with direction 0 and the other, L 1 , for labels with direction 1. Therefore as the direction changes for every row in a route, the label obtained from the extension of the label L 0 in the labels list with direction 0 is added to the labels list with direction 1.

For each constraint (2), we obtain a dual cost π i and each constraint (3) gives the θ dual cost. Using these dual costs we compute a reduced cost ĉr for any route r in the master problem. This reduced cost depends on whether the route is selective, thus let ĉs r = c r -i∈r a ir π i +qA r θ be the reduced cost of the selective route r and ĉr = c r -i∈r a ir π i for the non-selective route. It also important when generating new selective routes to take the θ dual cost into account at each label extension to avoid interesting routes from being dominated:

ĉs r = c r - i∈r a ir π i + qA r θ = c r - i∈r a ir (π i + qA i θ)
In the column generation part, routes with positive reduced cost can be discarded because they cannot belong to any optimal solution. Nevertheless, in the enumeration procedure, a new pricing problem is solved which brings out the routes with a reduced cost strictly less than .

Constraint Programming

We introduce in this section our constraint programming approach (CP). First, we describe a classical precedence model mainly used in VRP (partially used by [START_REF] Briot | A constraint-based approach to the differential harvest problem[END_REF], fully explained in [START_REF] Bourreau | De la Programmation Linéaire à la Programmation Par Contraintes[END_REF]) enhanced by specific bin packing capacity constraints. Finally, a constructive search strategy is detailed. Let V be the set of at most n vehicles(|V | = n). For each vehicle, two dummy depots are created: an initial depot and a final depot. Note V d (resp. V f ) the set of initial (resp. final) depots. The set of nodes N in the graph, such that |N | = n + 2 * |V | (one node per row and two nodes per vehicle), is ordered as follows:

N = { rows 1, . . . , n, V d n + 1, . . . , n + |V |, V f n + |V | + 1, . . . , n + 2 * |V |}
Let us define the decision variables (see Figure 5 and Table 1, the distance matrix are displayed in the Figure 11 and Figure 12):

-∀i ∈ N, successor i ∈ N (resp. predecessor i ∈ N ) variables giving the successor (resp. predecessor) of the row i in the route. -∀i ∈ N, position i ∈ N, variables providing the position of the row i in the route, initial depots are in position 0. -∀i ∈ N, assignment i ∈ V variables indicating the vehicle assignment of the row i. -∀i ∈ N, direction i ∈ {0, 1}, variables showing the direction of row i.

-∀v ∈ V, selective v ∈ {0, 1}, variables indicating whether a vehicle is selective.

-∀i ∈ N ∀u ∈ {A, B}, CapaSumq u i ∈ [0, CapaM ax], variables measuring the cumulative sum of the harvested u-grapes quantity before harvesting row i.

-Obj is the objective variable which computes the total traveled distance. direction 0 1 1 0 1 0 0 1 0 0 0 1 1 1 selective 1 1 1 1 0 0 0 0 1 1 0 1 1 0 CapaSumqA 57 0 0 70 0 150 50 100 0 0 0 120 144 200 CapaSumqB 43 0 0 30 0 150 50 100 0 0 0 80 56 200 Table 1. Variables affectation for an eight rows instance, CapaM ax is set to 200 and Rmin to 174, illustrated in Figure 5. The harvesting quantity qA/qB is displayed for the direction 1, but for the opposite direction, the harvesting quantity is computed by adding 5 (the latency) to qB and to subtract 5 to qA.

Model M2: Constraint Programming

∀f i ∈ V f successor fi = n + i ( 6
)
∀d i ∈ V d assignment di = i (7) ∀f i ∈ V f assignment fi = i (8) ∀i ∈ V d position i = 0 (9) AllDif f erent(successor 1 , . . . , successor |N | ) (10) ∀i ∈ N direction successori = 1 -direction i (11) ∀i ∈ N position successori = 1 + position i (12) ∀i ∈ N assignment successori = assignment i (13) i∈[1,n] (qA i * selective assignmenti ) ≥ Rmin (14) ∀i ∈ N CapaSumqA successori = CapaSumqA i + Q A i (15) ∀i ∈ N CapaSumqB successori = CapaSumqB i + Q B i ( 16
)
∀d i ∈ V d s di < s di+1 (17) ∀i ∈ N predecessor k = i ⇔ successor i = k (18) ∀u ∈ {A, B} dif f N (assignment, CapaSumq u , (1, . . . , 1) T , Q u ) ( 19
)
Obj = i∈N D i,successori,directioni (20)
min Obj

Constraints ( 6), ( 7), ( 8) and ( 9) assign the successor of a final depot to the corresponding initial depot, the same vehicle is affected to initial and final depot and initial depots are in position 0. The AllDif f erent constraint [START_REF] Santos | Sustainable vegetable crop supply problem[END_REF] ensures that routes are disjointed and that they cover all the rows, every successor is distinct implies that a row is taken exactly once (there are n values for n variables). The direction, position and assignment variables are updated depending on their successors [START_REF] Feillet | An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems[END_REF], [START_REF] Irnich | Shortest path problems with resource constraints[END_REF] and [START_REF] Mcbratney | Future directions of precision agriculture[END_REF]. Constraint [START_REF] Plessen | Partial field coverage based on two path planning patterns[END_REF] ensures that the Rmin A-grapes quantity is collected. The cumulative amount of already harvested Agrapes (resp. B-grapes) is computed with (15) (resp. ( 16)), these constraints ensure that no vehicle exceeds its hoppers loading due to the maximum value of the CapaSum domain. The constraints [START_REF] Toth | The vehicle routing problem[END_REF] and ( 21) minimize the total traveled distance.

We added redundant constraints to improve the performance of this model: first, symmetry breaking constraints [START_REF] Robert | A stochastic dynamic programming approach to analyze adaptation to climate change-application to groundwater irrigation in india[END_REF] between vehicles are used then a channeling constraint [START_REF] Robert | Precision agriculture: a challenge for crop nutrition management[END_REF] between successor and predecessor variables. The diffN constraints [START_REF] Seyyedhasani | Reducing field work time using fleet routing optimization[END_REF] are also redundant and handle the vehicle capacity taking account of the vehicle filling and the object positioning in the vehicle, this positioning depends on both the X and Y axis (see Figure 6). We create two objects per row: one indicates the A-grape quantity harvested in the rows and the other indicates the B-grapes quantity harvested. Objects are affected by vehicle assignment (X axis) and ordered depending on their position in the route with the CapaSumq u variables ∀u ∈ {A, B} (Y axis) which link row with its direct successor. The height of a task, Q u i ∀u ∈ {A, B} , depends on the type of the node i ∈ N : q u i,selectivei,directioni for rows, 0 for initial depots and CapaM ax -CapaSum u v f for final depots. The height of the final depots thereby defined is used to make the diffN constraint even more compact, all vehicles will have their maximum capacity reached due to the height of the final depots which fill the remaining space (see Figure 6). The Snake constructive search strategy One of the advantages of constraint programming is the possibility to choose the search strategy in the decision tree. The strategy is based on two axes: variable choice and value choice. The variable choice is a determining factor in a good strategy. Indeed, if the first variables used have a large domain or are weakly constrained then the decision tree is larger. With this in mind, we wanted to create a strategy that mimics a greedy method, which we call: the Snake. The Snake strategy builds a route and then constructs entirely the next one and so on. The purpose is to find a good solution in a few decision nodes. Other strategies (as DomOverWDeg) generally build route fragments, and, at the bottom of the decision tree, try to assemble these fragments to obtain a feasible route. This assembly is very combinatorial due to the many possible arrangements of the fragments, see Figure 7.

The Snake strategy works as follows: the first variable is the first available initial depot. The choice of the new variable is determined by the choice of the value of the previously instantiated variable. The first available value for the variable is selected, the values are increasingly sorted (we want to minimize the total distance). Once a final depot is instantiated, the next variable selected is the next initial depot. The variables that calculate the distance to the successor are used. Besides, these variables are sorted so that optimization begins with selective routes. 7. The Snake strategy vs the DomOverWDeg strategy illustration.

• • • • • • • • • • • • • • • • DomOverWDeg Snake • • • • • • • • ? • • • • . . . • • • • • • Fig.

Experimental results

In this section, we present the experimental results, first, we introduce the data sets used for the experimental study, then we outline the results obtained with our models. For the parametric study, we were focusing on exact methods and thus on finding optimal solutions.

Description of data sets

We have tested our models on different instances, some were artificially generated based on real data observed in a vineyard, at INRA Pech-Rouge (Gruissan), located in the southern France (cf. Figure 1).

As [START_REF] Briot | A constraint-based approach to the differential harvest problem[END_REF][START_REF] Saddem Yagoubi | New approach for differential harvest problem: The model checking way[END_REF] we decompose this instance to create a set of smaller instances, denoted by G-instances. We create instances with 10 consecutive rows and up to 24 rows (the original instances), with a hopper capacity of 900 and 1800 and the Rmin value takes value in {0, 0.25, 0.5, 0.7, 0.9, 1} of the total A-grapes in the vineyard.

Artificial instances were generated based on two vineyard shapes, the square instances (S-instances) and the triangle instances (T -instances) see Figure 10, that seems to be theoretically interesting. We assume that the triangle instances must be the worst-case instances because everything is symmetric. The square instances were determined to see the influence of the increase of the Rmin value on the objective function.

The same construction as the original instance is used to construct artificial instances. The Table 2 summarizes the parameters variation of each instance type.

#rows

CapaM ax Rmin Total G-instances {10, 11, . . . , 24} {900, 1800} {0, 0.25, 0.5, 0.7, 0.9, 1} 1140 T -instances {10, 11, . . . , 24} {100, 200, . . . , 500} {0, 0.25, 0.5, 0.7, 0.9, 1} 540 S-instances {10, 11, . . . , 24} {100, 200, . . . , 500} {0, 0.25, 0.5, 0.7, 0.9, 1} 540 Table 2. Parameters variation for each data set.

Results

In this section, we will detail the results obtained for our approaches. The results were performed on an Optiplex 5055 computer with an AMD RYZEN 7 Pro 1700 (8 cores/4 Mo/16 Threads/3 GHz) processor. For the column generation approach, we use CPLEX 12.8.0.0 and for the constraint programming, we use Choco 4.10.1.

Results for the column generation methods The time limit for all the instance was fixed to 10 minutes, except for the original instance with 24 rows where the time limit was 1 hour, due to the number of instances that has to be solved.

To the best of our knowledge, we are the first who were able to solve the real instance with 24 rows, see Figure 1, in 2210 seconds and almost all the computation time is used to generated routes and to find an integer solution, the enumeration technique took less than a few minutes and generates only 18 columns.

In the Table 5, a comparison is made between the results obtained with the variation of the CapaM ax parameter for the S and T instances and the same results for the G instances are shown in the Table 3. The results displayed are the average computation time and the average integrality gap of the Rmin values for every row's number and CapaM ax value. When the CapaM ax parameter increases there is a huge increase in the computation time since the pricing problem is more difficult to solve (the number of non-dominated routes generated is larger). For the G instances, the gap is really small (less than 0.002 %) however almost all the large instances reach the time limit. 3. Results for the G instances with the variation of the CapaM ax parameter.

The Figure 8 and Figure 9 indicate the results obtained for the G instances according to the Rmin parameter variation and each point represents the average value of the CapaM ax values. One can see that the objective value and the computation time appear not to increase from 0% to 90% Rmin but when demanding to harvest all the A-grapes the objective value grows due to the latency, all the rows have to be harvested in the direction that maximizes the A-grapes harvested, yet the computation time is low even for the biggest instances.

Results for the constraint programming approaches Precedent works using constraint programming to solve the DHP were able to solve optimally a 16 rows instances in 6 days, then optimally solve 10 and 12 rows instances with a 2 hours time limit. We propose to compare our approach to its ability to obtain a good feasible solution in a short time.

With this in mind, we only show the results for a few instances (one with 10 rows, 13 rows, and 16 rows), with a 10 minutes time limit. The results for the constraint programming approach are summarized in the Table 4, we are looking for statistics for the first, the best solution (whether the optimal solution is found according to the column generation solution) and for optimality proof. For the 10 rows instance, with the DomOverWDeg strategy a poor quality first solution has been found. Moreover, the last solution is not improving so much the first solution (4379 to 4358). Meanwhile, the Snake strategy gives a good first solution in a few decision nodes (27 nodes). This solution is improved to optimality in under 2 minutes. The diffN constraint adds some reasoning to the model because the nodes number decreases but the total time to compute an optimal solution is higher.

For the instance with 13 rows, the analysis is even worse for the DomOver-WDeg strategy cannot find any solution within the 10 minutes time limit even with the diffN constraint. Nevertheless with the Snake strategy a solution is found in less than 1 second but at the end of the time limit, no optimal solution has been proved. For the 16 rows instance, the Snake strategy also finds a solution in less than 1 second but is not able to improve it to optimality in less than 10 minutes.

These results are interesting for a hybridization approach because the feasible solution found by the constraint programming in less than a few minutes can be used in the enumeration part for the column generation approach. Table 4. Constraint programming results for the instance with 10, 13 and 16 rows with a 600 seconds time limit.

Conclusion

In this paper, we have proposed both a column generation, with enumeration technique, approach based on a new graph representation of the DHP and a constraint programming model using global constraints. We have performed a parametric study on various instance sets, some based on real data and other purposely generated. The main difficulty is that computing the improving routes in the pricing problem may be awful with the growth of the CapaM ax parameter. The small integrality gap obtained gives us good hope to solve larger instances with a bigger time limit, and validate the efficiency of the column generation approach to tackle the DHP, the real instance with 24 rows was optimally solved. The constraint programming results are promising for a hybridization approach, computing all the -improving routes with the constraint programming integer solution (found in a few minutes) for the enumeration part.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Illustration of the agronomic map with different zones of grapes quality (real data from the Gruissan vineyard).

Fig. 3 .

 3 Fig. 3. Latency illustration.

Fig. 4 .

 4 Fig.[START_REF] Bourreau | De la Programmation Linéaire à la Programmation Par Contraintes[END_REF]. The flatten graph representation of the vineyard, solid edges correspond to direction 0 and dashed edges refer to direction 1, dotted edges are direction free edges.

Fig. 5 .

 5 Fig.5. Illustration of the optimal solution obtained with constraints programming for an instance with 8 rows. Plain arcs (resp. dotted and dashed arcs) representing vehicle one (resp. two and three), for the sake of clarity only the used vehicles are represented.

Fig. 6 .

 6 Fig.6. Representation of the diffN constraint for the A-grapes for the instance shown in the Figure5.

Fig. 9 .Fig. 10 .

 910 Fig. 9. The evolution of the computation time when the Rmin parameters increase for the G instances.

Fig. 11 .Fig. 12 .

 1112 Fig. 11. Distance matrix between rows and the depot with direction 0, for the example instance Figure5.

Table 5 .

 5 Results for T and S instance type with the variation of the CapaM ax parameter.

			T		S				T		S
	#rows CapaM ax CPU(s) gap(%) CPU(s) gap(%) #rows CapaM ax CPU(s) gap(%) CPU(s) gap(%)
		100	0.29	4.25	0.2	3.37		100	0.82	0.13	47.66	3.70
		200	0.49	0.11	0.94	0.41		200	16.52	4.55	216.75 5.25
	10	300	2.36	0.04	2.64	0.64	17	300	529.01 5.12	603.39 5.72
		400	6.52	0.41	9.05	0.87		400	521.21 1.77	525.95 2.48
		500	9.40	1.10	16.40	1.67		500	542.55 1.80	624.74 4.15
		100	1.32	4.95	0.15	2.26		100	0.71	0.99	2.78	3.94
		200	14.96	7.03	0.91	8.16		200	6.55	0.22	7.11	0.54
	11	300	48.99	7.28	79.15	8.45	18	300	441.58 0.52	512.01 1.04
		400	87.25	7.30	52.64	8.24		400	518.07 1.59	549.86 0.27
		500	59.52	7.53	98.07	8.35		500	559.98 2.15	620.04 3.87
		100	0.23	1.22	0.24	2.56		100	0.55	1.67	0.08	0.64
		200	0.90	0.58	0.93	0.50		200	310.40 3.79	311.51 4.63
	12	300	8.96	0.38	10.50	0.27	19	300	521.54 4.20	522.08 4.93
		400	15.42	0.68	20.34	0.58		400	517.21 4.35	626.03 7.15
		500	42.56	0.50	26.88	1.12		500	512.78 2.23	613.55 3.85
		100	1.35	3.46	2.34	3.32		100	0.047	0	106.80 1.91
		200	20.37 6.07	159.77 7.017		200	10.36	0.26	16.08	0.31
	13	300	318.57 5.95	419.87 7.16	20	300	500.71 0.53	513.86 0.73
		400	523.88 6.56	518.98 7.51		400	504.41 0.76	620.26 2.10
		500	455.87 6.83	267.43 7.39		500	512.33 2.53	607.29 3.03
		100	0.52	1.93	0.33	2.73		100	0.14	1.67	0.08	0.53
		200	2.87	0.82	3.09	0.48		200	415.4	3.71	515.31 4.24
	14	300	21.14 1.07	25.82	0.75	21	300	520.53 3.83	623.61 4.34
		400	125.38 0.44	92.45	0.60		400	506.63 3.95	608.38 4.78
		500	249.35 0.65	245.66 0.39		500	519.92 2.30	607.89 3.07
		100	1.97	2.19	0.591 2.04		100	1.08	2.04	0.18	1.09
		200	307.76 4.83 454.34 5.88		200	48.26	0.87	38.33	0.58
	15	300	428.17 5.32	524.62 6.29	22	300	515.78 2.96	522.21 1.34
		400	526.90 5.54	545.35 6.36		400	519.62 0.70	626.18 2.26
		500	515.87 3.29	530.25 6.18		500	549.81 2.48	640.07 2.57
		100	0.36	1.10	0.21	0.36		100	0.22	0.98	0.10	1.34
		200	3.65	1.34	7.00	0.77		200	418.62 3.47	418.97 3.78
	16	300	156.90 0.24	136.39 1.07	23	300	515.7	2.51	542.45 4.02
		400	526.57 0.44	513.76 0.26		400	524.80 2.57	621.25 4.65
		500	517.73 0.99	550.97 2.74		500	521.29 2.32	621.82 2.63

Acknowledgements

This work was supported by the French National Research Agency under the Investments for the Future Program, referred as ANR-16-CONV-0004

Supported by organization French National Research Agency under the Investments for the Future Program, referred as ANR-16-CONV-0004.

Appendix


Perrine André
email: perrine.andre@u-bordeaux.fr

Gordon Proctor

Esther Bénédicte Driollet

Esther Lopez-Garcia

David Gomez-Cabrero

Eric Neyraud

Fernando Rodriguez-Artalejo

Martine Morzel

Catherine Feart

Esther Garcia-Esquinas

Catherine Féart

The role of overweight in the association between the Mediterranean diet and the risk of type 2 diabetes mellitus: a mediation analysis among 21 585 UK biobank participants

Keywords: BMI, Diabetes, mediation analysis, Mediterranean diet, overweight, type 2 diabetes mellitus

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

INTRODUCTION

According to the International Diabetes Federation, about 8.8% of adults have diabetes [START_REF]IDF Diabetes Atlas[END_REF]. Worldwide, the prevalence and incidence of type 2 diabetes mellitus (T2DM) has increased, with a subsequent increase in health complications [START_REF]IDF Diabetes Atlas[END_REF]. In the United Kingdom (UK), prevalence rates raised from 3.2% in 2004 to 5.3% in 2014 [START_REF] Zghebi | Examining trends in type 2 diabetes incidence, prevalence and mortality in the UK between 2004 and 2014[END_REF]. T2DM is a long-term metabolic disorder, mainly characterized by insulin resistance (IR) and pancreatic beta-cell dysfunction [START_REF] Defronzo | From the triumvirate to the ominous octet: a new paradigm for the treatment of type 2 diabetes mellitus[END_REF]. Excessive body weight represents one of the main risk factors of T2DM.

Therefore, concomitantly with the increased prevalence of diabetes over time, the prevalence of excessive weight has substantially increased: worldwide, the proportion of overweight or obese (i.e. body mass index BMI ≥ 25kg/m²) adults increased from 29% to 37% in men, and from 30% to 38% in women, during the period from 1980 to 2013 [START_REF] Ng | Global, regional, and national prevalence of overweight and obesity in children and adults during 1980-2013: a systematic analysis for the Global Burden of Disease Study 2013[END_REF]. In 2015, 58% of women and 68% of men were overweight or obese in the UK [START_REF]Statistics on Obesity, Physical Activity and Diet -England[END_REF]. Gray et al. observed that higher BMI was consistently associated with a higher risk of developing T2DM among older adults, even for participants who were only moderately overweight (25 kg/m² ≤ BMI ≤ 27.49 kg/m²) with a 14% to 31% higher risk of diabetes for men and women respectively [START_REF] Gray | The Relationship between BMI and Onset of Diabetes Mellitus and its Complications[END_REF].

Because of the epidemic of obesity, expected trends regarding the incidence of T2DM are alarming and today most public health strategies to counteract both obesity and diabetes emphasize modifiable risk factors, such as avoiding unhealthy diet, sedentary lifestyle, smoking and excessive alcohol intake. Regarding diet, the plant-based Mediterranean diet (Medi Diet) is widely recognized as a healthy dietary pattern [START_REF] Martinez-Gonzalez | Mediterranean food pattern and the primary prevention of chronic disease: recent developments[END_REF]. Accumulated evidence has supported a beneficial effect of higher adherence to this healthy dietary pattern on the risk of diabetes [START_REF] Khazrai | Effect of diet on type 2 diabetes mellitus: a review[END_REF][START_REF] Jannasch | Dietary Patterns and Type 2 Diabetes: A Systematic Literature Review and Meta-Analysis of Prospective Studies[END_REF][START_REF] Esposito | Mediterranean diet and type 2 diabetes[END_REF][START_REF] Esposito | A journey into a Mediterranean diet and type 2 diabetes: a systematic review with meta-analyses[END_REF][START_REF] Koloverou | The effect of Mediterranean diet on the development of type 2 diabetes mellitus: a meta-analysis of 10 prospective studies and 136,846 participants[END_REF]. Specifically, in a recent review and meta-analysis based on 6 studies (2 out of 6 included non-Mediterranean populations), Jannasch et al. observed a 13% lower risk of T2DM for the upper quantile of Medi Diet [START_REF] Jannasch | Dietary Patterns and Type 2 Diabetes: A Systematic Literature Review and Meta-Analysis of Prospective Studies[END_REF]. Esposito et al. found that 5 out of 8 metaanalyses showed a favorable effect of the Medi Diet compared with other dietary patterns on weight loss. Moreover among 2 meta-analyses selected, up to 23% lower risk of T2DM was observed with greater adherence to a Medi Diet [START_REF] Esposito | A journey into a Mediterranean diet and type 2 diabetes: a systematic review with meta-analyses[END_REF]. Regarding interventional studies, a review and meta-analysis on 16 randomized clinical trials (RCTs) suggested that after 6 months of a dietary intervention, the Medi Diet induced a significant mean weight loss of -1.84 kg, compared with other diets for which weight loss remained non-significant [START_REF] Ajala | Systematic review and meta-analysis of different dietary approaches to the management of type 2 diabetes[END_REF].

Hamman et al. found a 16% lower risk of diabetes for every kilogram of weight loss, suggesting a dose-response effect [START_REF] Hamman | Effect of weight loss with lifestyle intervention on risk of diabetes[END_REF]. In this context, we hypothesized that the contribution of the Medi Diet to the reduced risk of T2DM in previous studies could be explained by (i) a direct effect of Medi Diet on T2DM independent of overweight (whatever the role of diet on overweight), (ii) the above effect jointly with an effect of Medi Diet on T2DM mediated by overweight, (iii) a single effect of Medi Diet on overweight, this latter being then favorable to the glycemic control or insulin resistance, for instance, and therefore for the risk of diabetes.

Elucidating the role of overweight in this association is important because it can help resolve the controversy on whether the Medi Diet can prevent T2DM even among those in which the Medi Diet fails to reduce weight. The aim of the present analysis was to disentangle these relationships among UK adults using a mediation approach with diet as a major determinant of diabetes and changes in overweight as potential mediators in the relation between adherence to a Medi Diet and T2DM.

SUBJECTS AND METHODS

The UK Biobank

The UK Biobank is a prospective cohort initiated in 2007 that included more than 500 000 UK participants recruited between 2007 and 2010, aged 40 to 71 years and who registered for primary health-care provision under the National Health Service (see UK Biobank's online protocol http://www.ukbiobank.ac.uk). The UK Biobank obtained ethical approvals from the North West Multi-Centre Research Ethics Committee, the Community Health Index Advisory Group, the Patient Information Advisory Group, and the National Health Service National Research Ethics Service. All participants gave written informed consent.

At baseline participants provided information on lifestyle, health and socioeconomic factors, and underwent a complete physical examination. Follow-ups were conducted between 2012 and 2013 (F1, approximately 4% of baseline participants were followed-up) and between 2014 and 2017 (F2, approximately 4.7% of baseline participants were followed-up).

Study sample

This research has been conducted using the UK Biobank resource under application number 3028. Analyses were based on a selected sample from the UK Biobank cohort with available dietary data and diabetic status. Figure 1 describes the sample selection for the present analysis. From the initial sample of 502 591 UK Biobank participants, we identified 38 027 participants with at least one follow-up data and without secondary withdrawal of consent. Among these 38 027 participants, we excluded those without data on diabetic status at baseline (n= 62) or at least at one follow-up after baseline (n= 202) or with prevalent diabetes (n= 1 319). Moreover, we excluded women who had gestational diabetes, as well as participants with transient diabetes (i.e. those reporting incident diabetes at F1 but not at F2, n= 17). Then, we excluded participants without nutritional data (n= 13 181) or nutritional data not reflecting the usual diet (usual diet is defined in the Diet section, n= 1 662), leading to a final sample of 21 585 participants.

Assessment of type 2 diabetes

At baseline and each follow-up, participants were invited to answer the following question: "Has a doctor ever told you that you have diabetes?" and women with a positive answer were also asked whether they had been diagnosed with diabetes only during pregnancy. The type of diabetes (type 1 or 2 diabetes) was not available, but, as type 1 diabetes most often appears in children or young adults, we considered that most incident cases in this study were T2DM.

As the self-reported age of T2DM diagnosis included many missing or unlikely data, we determined this as the mean age between the two follow-up intervals for all participants.

Diet

Between baseline and F1, participants were invited to answer up to five dietary surveys at regular intervals over the previous 24h as described previously [START_REF] Bradbury | Dietary assessment in UK Biobank: an evaluation of the performance of the touchscreen dietary questionnaire[END_REF]. Dietary information was collected via the Oxford WebQ, a web based 24h recall developed for use in large population studies [START_REF] Liu | Development and evaluation of the Oxford WebQ, a low-cost, web-based method for assessment of previous 24 h dietary intakes in large-scale prospective studies[END_REF][START_REF] Anderson | Adiposity among 132 479 UK Biobank participants; contribution of sugar intake vs other macronutrients[END_REF]. The following question was added to ensure that responses reflected usual diet: "Would you say that what you ate and drank yesterday was fairly typical for you?". Most (around 82%) of 24h dietary recalls were considered as reflecting typical diet. These latter (i.e, dietary surveys reflecting the usual diet) were used in all the analyses, in order to select participants with stable diet over time. We calculated average food, drink and energy intakes (derived from food composition tables) with an average of 2.2 dietary surveys reflecting the usual diet per participant.

Adherence to the Medi Diet was assessed as described by Sofi et al. [START_REF] Sofi | Mediterranean diet and health status: an updated meta-analysis and a proposal for a literature-based adherence score[END_REF], using literaturebased thresholds of selected food groups and alcohol, in order to avoid sample-dependent data analysis (i.e. food consumption based on median sample [START_REF] Féart | Potential benefits of adherence to the Mediterranean diet on cognitive health[END_REF]). The term "literature-based Medi Diet score" was used in this article to refer to this Medi Diet score [START_REF] Sofi | Mediterranean diet and health status: an updated meta-analysis and a proposal for a literature-based adherence score[END_REF]. We computed this score, which ranged from 0 (poor adherence) to 18 (highest adherence), using the portion size of 8 food groups (i.e. fruits, vegetables, legumes, cereals, fish and olive oil, for which the higher, the better; meat and meat products, and dairy products, for which the lower, the better) and alcohol (a moderate consumption of 1 to 2 units per day was considered as beneficial).

The literature-based Medi score was used as a continuous variable (+1 point) in the present study.

Overweight

Body mass index (BMI) was measured at baseline and at each follow-up, and expressed in kg/m². For the present analyses we only used data on BMI collected after inclusion (at F1 or F2 if missing at F1). This strategy enabled us to account for the temporality of mediation analyses requiring the mediator (i.e. overweight) to be measured after the main exposure (i.e. Medi Diet). Overweight was considered as a BMI ≥ 25 kg/m², those with lower BMI being considered not overweighted.

Covariates

Sociodemographic, lifestyle and health characteristics were collected at baseline, including age, sex, educational level (considered as A-level, college or university versus less or other qualification), tobacco use (non-smoker, ex-smoker or current smoker), physical activity (defined as less than 210 min walking/week or 150 min moderate activity/week or 75 min intense activity/week, based on World Health Organization recommendations for people aged 18 to 64 (20)), number of comorbidities (defined as the number of comorbidities among the following: cancer, heart attack, angina, stroke, hypertension, blood clot, chronic bronchitis, asthma, eczema, allergic rhinitis or hay fever) and number of drugs taken regularly.

Statistical analyses

Quantitative and qualitative variables were expressed as means ± standard deviation (SD) or number (percentages), and were compared using Student's t test or Chi2 test according to T2DM status, respectively. -Total effect, i.e. the whole association between adherence to the Medi Diet and the risk of T2DM, including the one mediated by the odds of overweight; -Direct effect, i.e. the association between adherence to the Medi Diet and the risk of T2DM, adjusted for overweight; -Indirect effect, i.e. the association between adherence to the Medi Diet and the risk of T2DM, mediated by the overweight.

Secondary analyses were carried out for exploratory purposes and performed (i) by removing the alcohol item from the literature-based Medi Diet score, in order to avoid an association between Medi Diet T2DM which could be excessively driven by alcohol intake ( 22), (ii) by excluding non-whole grains from the cereal item, given that whole but not refined grains could protect from diabetes [START_REF] Aune | Whole grain and refined grain consumption and the risk of type 2 diabetes: a systematic review and dose-response meta-analysis of cohort studies[END_REF][START_REF] Pepa | Wholegrain Intake and Risk of Type 2 Diabetes: Evidence from Epidemiological and Intervention Studies[END_REF] (iii) and by using each food group of the literature-based Medi Diet score separately, simultaneously adjusting for other food groups, to evaluate if the association could be driven by a particular food group than another.

In supplementary analyses, we assessed the robustness of our main analysis by implementing an alternative Medi Diet adherence score. We chose to compute a score already proposed by Panagiotakos et al [START_REF] Panagiotakos | Adherence to the Mediterranean food pattern predicts the prevalence of hypertension, hypercholesterolemia, diabetes and obesity, among healthy adults; the accuracy of the MedDietScore[END_REF], which considered the same 9 food groups as the literature-based Medi score, with some modifications (emphasis is done on non-refined cereals and full fat dairy products), but that also considered consumption of potatoes (the higher, the better) and poultry (the lower, the better). This score ranges from 0 (low adherence) to 55 (high adherence) points, each of the 11 food groups being marked from 0 to 5 points depending on the level of consumption. This alternative Medi score was considered as a continuous variable (+5 points) in the present study.

Missing data represented less than 3% of the analytical sample, we thus imputed missing values using the reference category for qualitative variables or the median value for quantitative variables. Statistical analyses were performed using SAS software version 9.4 (SAS Institute Inc., Cary, 134 NC, USA) and R software version 3.3.2 (R Foundation for Statistical Computing, Vienna, Austria).

RESULTS

Overall, the participants included in our study sample (n= 21 585) exhibited similar characteristics than those non-included (n= 481 006) regarding age at baseline (56.5y for included participants versus 57.1y for non-included participants), BMI at baseline (26.5 kg/m² for included participants versus 27.5 kg/m² for non-included participants), sex (proportion of women 52% in the present studied sample versus 54% for non-included participants) and the average number of drug consumed at baseline, as proxy of comorbidities (2.0 for included participants versus 2.5 for non-included participants).

Characteristics of the included participants

The studied sample consisted of 21 585 participants. Mean age at baseline was 56.5 years (range: 40.2 -71.0), and there was a slightly lower proportion of men (48%) than women.

During a mean follow-up time of 6.1 years (range: 1.3 -10.9), 473 participants developed incident diabetes.

The average BMI (SD) was 30.7 (5.5) kg/m² for incident cases of T2DM and 26.4 (4.3) kg/m² for participants without T2DM, representing 85.6% and 57.0% of overweight, respectively.

Overall, T2DM incident cases were older, more often men, and were more likely to present a more inactive lifestyle, a higher prevalence of drugs consumption, and a higher prevalence of comorbidities than their counterparts (Table 1). However, there was no difference on average energy intake between groups.

[Table 1 here] The literature-based Medi Diet score was normally distributed with 8.8 out of 18 points on average among the 21 585 participants. Incident T2DM cases had a lower score than those who did not develop diabetes (-0.7 point on average).

Regarding the consumption of each food included in the Medi Diet, participants who remained free from T2DM over time consumed more fruits, more vegetables and olive oil, and less meat and meat products than participants who developed T2DM (Table S1).

Regression-based mediation analysis between the literature-based Medi score, overweight and risk of T2DM.

In multivariate analyses, each 1-point increase of adherence to the Medi Diet was associated with a 8% lower odds of overweight (Path α, odds ratio OR: 0.92, 95% CI: 0.91-0.93) (Table 2). Moreover, being overweight was associated with a higher risk of T2DM (Path β, hazard ratio HR: 3.89, 95% CI: 3.00 -5.04).

Regarding the whole association between Medi Diet adherence and risk for T2DM, we observed that each additional point of the Medi Diet score was associated with a 14% decreased risk of T2DM (HR: 0.86, 95%CI: 0.82 -0.90); 10% of this association (HR: 0.90, 95% CI: 0.87 -0.92) was mediated by the reduced overweight associated with each additional point of the Medi Diet score, and 4% (HR: 0.96, 95% CI: 0.93 -0.99) was due to the Direct effect of the Medi Diet on the risk of T2DM. After additional adjustment for comorbidities and number of drugs consumed, these results were virtually unchanged.

[Table 2 here]

Secondary analyses

When (i) alcohol item was removed from the literature-based Medi Diet score or when (ii) considering only whole cereals, results were unchanged. None of the food groups were directly associated with the risk of T2DM (i.e. Direct effect). However, higher intake of fruits, vegetables and olive oil, and lower intake of meat and dairy products were indirectly associated with a lower risk of T2DM by a lower odds of overweight (i.e. Indirect effect mediated by BMI) (data not shown).

Supplementary analyses

Using the alternative Medi Diet adherence score proposed by Panagiotakos et al., we observed similar findings which reinforced the robustness of the results. Each 5-additional point of the alternative Medi Diet was associated with a 28% decreased risk of T2DM (HR: 0.72, 95% CI: 0.67 -0.79) as a whole; a 18% (HR: 0.82, 95% CI: 0.77 -0.85) decreased risk of T2DM explained by an indirect association mediated by overweight, and a 10% (HR: 0.90, 95%CI: 0.84 -0.96) decreased risk of T2DM only explained by a higher adherence to this dietary pattern (Table S2).

DISCUSSION

In the present study with participants from the UK Biobank prospective cohort, a higher adherence to a Medi Diet was associated with a lower risk of T2DM over time. This association was mostly mediated by the lower odds of being overweight or obese among the highest Medi Diet adherents, although direct effect of Medi diet on the risk of T2DM, independent of overweight, was also observed.

This overall result appears consistent with existing literature, agreeing with a beneficial role of the Medi Diet in the prevention of T2DM. Specifically, in a meta-analysis based on 122 810 subjects, Schwingshackl et al. found a pooled risk ratio of 0.81 for T2DM comparing individuals in the highest vs. lowest adherence of Medi Diet [START_REF] Schwingshackl | Adherence to a Mediterranean diet and risk of diabetes: a systematic review and meta-analysis[END_REF]. In 2014, based on 22 relevant studies including RCTs, meta-analyses and systematic reviews, Khemayanto et al.

concluded that the combination and interaction of Medi Diet food groups was essential for the prevention and management of T2DM [START_REF] Khemayanto | Role of Mediterranean diet in prevention and management of type 2 diabetes[END_REF]. Specifically, these food groups (i.e. such as fruits, vegetables, legumes, olive oil or fish) provided health promoting properties such as lower body weight, hemoglobin A1C, density lipoprotein (LDL) and oxidative stress, and improved HDL, these latter being beneficial for the improvement of the prevention and prognosis of T2DM [START_REF] Khemayanto | Role of Mediterranean diet in prevention and management of type 2 diabetes[END_REF]. According to our exploratory results, when each food group part of the Medi Diet was considered separately in mediation models none was directly associated with T2DM (i.e. Direct effect, not mediated by the odds of developing overweight), suggesting that the synergistic effect that occurs in a Medi Diet might brings superior benefits compared to each isolated nutrient [START_REF] Martínez-González | Mediterranean diet: the whole is more than the sum of its parts[END_REF].

The vast majority of previous studies only adjusted for BMI or the waist circumference (i.e. Direct effect), while our innovative approach took into account both the direct and the indirect effect of the Medi Diet on the risk of T2DM mediated by overweight. Our mediation analysis indicated that the association between Medi Diet adherence and risk of T2DM was mostly mediated through overweight (≈ 10% out of 14%). Specifically, a higher adherence to the literature-based Medi Diet was inversely associated with a lower odds of developing overweight, this latter being positively associated with a higher risk of T2DM. Interestingly, using an alternative Medi Diet definition, based on 11 food groups and different cut-off points, the present results were confirmed which reinforced the robustness of our findings.

The biological plausibility of our results is strong. Hamman et al. found a 16% lower risk of diabetes for every kg of weight loss, suggesting a dose-response effect [START_REF] Hamman | Effect of weight loss with lifestyle intervention on risk of diabetes[END_REF]. Also, a previous study observed that weight loss among overweight or obese patients with T2DM was consistently associated with a reduction of hemoglobin A1C, in a dose-dependent manner [START_REF] Gummesson | Effect of weight reduction on glycated haemoglobin in weight loss trials in patients with type 2 diabetes[END_REF]. A reduction of an average 16.7% in the homeostasis model assessment of IR (HOMA-IR) and 23.3% in leptin, both involved in the pathogenesis of T2DM, was also observed following a mean weight loss of 5.6 kg among 35 overweight or obese subjects [START_REF] Wang | Relationships between changes in leptin and insulin resistance levels in obese individuals following weight loss[END_REF].

Moreover, evidence has accumulated suggesting that greater adherence to a Medi Diet results in significant weight loss. In a RCT over 12 months, Medi Diet led to a similar weight loss than the American Diabetes Association diet (whose its composition in fiber is lower than the Medi Diet), but with a greater weight loss compared to a low-fat diet (ranging from -4.1 to -10.1 kg across studies for the Medi Diet) [START_REF] Mancini | Systematic Review of the Mediterranean Diet for Long-Term Weight Loss[END_REF].

Therefore, the inverse association between higher adherence to a Medi Diet and lower risk of T2DM observed in the literature may be, at least in part, explained by the preventive role of the Medi Diet on the odds of developing overweight or obesity.

In our study, the whole effect of the Medi Diet (i.e. Direct & Indirect effects) on the risk of T2DM resulted in a higher impact than each effect alone (i.e. Direct or Indirect effect only), suggesting that better adherence to a Medi Diet would have a synergistic impact on both the lower odds of overweight and the reduced risk for developing T2DM. This latter result suggests a beneficial effect of the Medi Diet preventing T2DM even among those who do not reduce their weight. These results can be attributed to a higher intakes of nutrients and food groups associated with anti-inflammatory properties, polyphenols, vitamins, minerals as well as other antioxidants, which are found in typical Medi Diet food groups such as fruits, vegetables, fish, olive oil, legumes, red wine and nuts [START_REF] Pérez-Jiménez | Identification of the 100 richest dietary sources of polyphenols: an application of the Phenol-Explorer database[END_REF][START_REF] Martínez-González | Benefits of the Mediterranean Diet: Insights From the PREDIMED Study[END_REF][START_REF] Schwingshackl | Mediterranean dietary pattern, inflammation and endothelial function: a systematic review and meta-analysis of intervention trials[END_REF]. Other potential beneficial effects of a Medi Diet on glucose metabolism and insulin sensitivity include in contrast lower intake of pro-inflammatory nutrients such as saturated fatty acids, refined sugars and a low-to moderate consumption of alcohol [START_REF] Risérus | Dietary fats and prevention of type 2 diabetes[END_REF][START_REF] Chandalia | Beneficial effects of high dietary fiber intake in patients with type 2 diabetes mellitus[END_REF][START_REF] Bonnet | Moderate alcohol consumption is associated with improved insulin sensitivity, reduced basal insulin secretion rate and lower fasting glucagon concentration in healthy women[END_REF]. Some limitations of the present work should be emphasized. First, the rate of participant loss to follow-up was high, which could lead to a selection bias, although minimized as observed in the present study. Therefore, the obtained results may not be generalizable to the whole UK biobank cohort, and further investigations, in other population-based cohorts, are needed to confirm such results. Second, longer follow-up time would allow increasing the duration between nutritional assessment (Medi Diet) and assessment of the mediator (BMI). However, to limit inverse causation due to dietary changes over time that would occur at the time of the diagnosis of T2DM, and to have the most accurate and representative assessment of usual diet, analyses were focused only on participants who reported a typical diet in nutritional questionnaires. Third, the diagnosis of diabetes was self-declared and we have considered that all incident cases of diabetes, except for gestational diabetes, were T2DM, which increased the risk of exposure misclassification.

Our study also has important strengths including its large sample size, its sampling among a population-based cohort and the use of a literature-based non-sample-dependent Medi Diet score which will allow comparison across further studies. Moreover, only dietary questionnaires reflecting the usual diet were used to determine usual food consumption. The robustness of our results were tested and confirmed with another different Medi Diet score, highlighting that these results are robust even with the use of another definition of the Medi Diet. Finally, we take into account a large range of sociodemographic, lifestyle and clinical factors to minimize the possibility of potential confounding.

Conclusion

In this study, we found that overweight may have a crucial mediated-effect in the relationship between higher adherence to a Medi Diet score and lower risk of T2DM. Interestingly, we also found a direct effect of the Medi Diet, regardless of the overweight, suggesting that this dietary pattern can prevent T2DM even if it does not lead to lower weight. These results seem to be clinically relevant for public health, in particular for encouraging a Mediterranean-like dietary pattern adoption for primary prevention of T2DM and overweight/obesity.

  Logistic regressions were performed to evaluate the association between adherence to a Medi Diet and the odds of overweight (Path α, Figure 2). Cox proportional hazards models, with age considered as the time scale, were used to analyze the association between overweight and risk of T2DM (Path β, Figure 2). The hypotheses of log-linearity and proportionality of risks were tested. Based on the non-significant interaction between Medi Diet and overweight (ρ-value 0.61) and between Medi Diet and sex (ρ-value 0.46), we decided not to stratify the analyses. The covariates considered as confounding factors, seclected according to the DAG (Directed Acyclic Graph) process and using data from the literature, included sex, educational level, energy intake, inactive lifestyle, tobacco use and overweight. Additional adjustment for age at baseline in the logistic regression model (Path α), or literature-based diet adherence score in the Cox proportional hazards model (Path β) were performed. Regression-based mediation analyses (21) were fitted to distinguish the Direct effect of adherence to a Medi Diet on risk of T2DM, and the Indirect effect mediated by overweight. It results in three estimates (Figure 2):

Figure 1 .Figure 2 .

 12 FIGURES

  effect (Medi Diet  T2DM mediated by overweight) 0.90 [0.87 -0.92] <0.0001 Total effect (Medi Diet  Overweight  T2DM) 0.86 [0.82 -0.90] <0.0001 440 Path α represents the regression coefficient (*Odds Ratio) for the association between 441 adherence to a Medi-diet and overweight. Path β represents the regression coefficient for the 442 association between overweight and the risk of T2DM (supplementary adjustment for Medi 443 diet). Abbreviations: Medi Mediterranean; T2DM Type 2 Diabetes Mellitus. Models were 444 adjusted for sex, educational level, average intake of calorie, sedentary lifestyle, tobacco use 445 (supplementary adjustment for age at baseline for the path α model, and adherence to the 446 Medi-diet for path β).

Table 1 .

 1 Baseline characteristics of the participants according to the T2DM, study sample from the UK Biobank (n= 21 585).Values are mean ± standard deviation or number (%). Abbreviations: T2DM Type 2 Diabetes Mellitus; BMI Body Mass Index, overweight being defined as BMI >25 kg/m².

	Potential cofounders

Table 2 .

 2 Mediation analysis of the association between adherence to a literature-based 436 Mediterranean diet (+ 1 point, /18 points) and the risk of T2DM mediated by overweight, 437 study sample from the UK Biobank (n= 21 585).

Acknowledgments and fundings: This work was supported by the Joint Programming

Initiative (JPI) Healthy diet for healthy life (HDHL). The SALAMANDER project is funded by the French National Research Agency (ANR, France), the Research Council for Biotechnology and Biological Sciences (BBSRC, UK) and the Ministry of Economy and Competitiveness (MINECO, Spain). This specific analysis was agreed by the UK Biobank Steering Committee (application #3028).

Declaration of interest:

The authors declare that they have no conflicts of interests.

Authors' contribution:

All authors contributed to study concept and design. PA and BD performed statistical analysis and interpretation of data. PA prepared the manuscript. All authors critically reviewed the manuscript for important intellectual content. All authors read and approved the final manuscript.

Guarantors: MM, CF, FRA and GP.