# Designing mixed fruit-vegetable cropping systems by integer quadratic programming

Sara Maqrot, Simon de Givry, Gauthier Quesnel, Marc Tchamitchian

► To cite this version:

Sara Maqrot, Simon de Givry, Gauthier Quesnel, Marc Tchamitchian. Designing mixed fruit-vegetable cropping systems by integer quadratic programming. 8th International Congress on Environmental Modelling and Software (iEMSs), Jul 2016, toulouse, France. 8 p. hal-01604512

HAL Id: hal-01604512

https://hal.science/hal-01604512

Submitted on 3 Jun 2020

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à 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.

<figure><img src="image_1.png" /></figure>
Jul 11th, 2:30 PM - 2:50 PM

# Designing mixed fruit-vegetable cropping systems by integer quadratic programming

Sara Maqrot

MIAT, sara.maqrot@toulouse.inra.fr

Simon de Givry

MIAT

Gauthier Quesnel

MIAT

Marc Tchamitchian

Ecodéveloppement, INRA, marc.tchamitchian@avignon.inra.fr

Follow this and additional works at: http://scholarsarchive.byu.edu/iemssconference

<figure><img src="image_2.png" /></figure>

Part of the Civil Engineering Commons, Data Storage Systems Commons, Environmental Engineering Commons, Hydraulic Engineering Commons, and the Other Civil and Environmental Engineering Commons

Sara Maqrot, Simon de Givry, Gauthier Quesnel, and Marc Tchamitchian, "Designing mixed fruit-vegetable cropping systems by integer quadratic programming" (July 11, 2016). *International Congress on Environmental Modelling and Software*. Paper 13. http://scholarsarchive.byu.edu/iemssconference/2016/Stream-B/13

This Event is brought to you for free and open access by the Civil and Environmental Engineering at BYU ScholarsArchive. It has been accepted for inclusion in International Congress on Environmental Modelling and Software by an authorized administrator of BYU ScholarsArchive. For more information, please contact scholarsarchive@byu.edu.
# Designing mixed fruit-vegetable cropping systems by integer quadratic programming

Sara Maqrot, Simon de Givry, Gauthier Quesnel
Marc Tchamitchian

MIAT, UR-875, INRA, F-31320 Castanet Tolosan, France
sara.maqrot@toulouse.inra.fr

Ecodéveloppement, INRA, 84000 Avignon, France
marc.tchamitchian@avignon.inra.fr

**Abstract:** Mixed fruit-vegetable cropping systems (MFVCS) are a promising way of ensuring environmentally sustainable agricultural production systems in response to the challenge of being able to fulfill local market requirements. Indeed, they combine productions and they also make a better use of biodiversity. These agroforestry systems are based on a complex set of interactions modifying the utilization of light, water and nutrients. Thus, designing such a system must optimize the use of these resources, by maximizing positive interactions (facilitation) and minimizing negative ones (competition). To attain these objectives, the system's design has to include the spatial and temporal dimensions of these interactions, taking into account the evolution of above- and belowground interactions over a time horizon. However, a considerable amount of research has been conducted, on the one hand, to prove the interest of agroforestry, and on the other hand to propose models supporting cropping plan and crop rotation decisions, but to our knowledge, no model supports the spatial and temporal allocation of both vegetable crops and trees in agroforestry systems. Therefore, we initially built a first MFVCS prototype using the Weighted Constraint Satisfaction framework but the resolution was limited to small scale systems. In this paper, we explore larger MFVCS models using a solver based on Integer Quadratic Programming. The limits of exact methods in solving the MFVCS problem are presented showing the need for approximation methods able to solve a large scale system with solutions of good quality in reasonable time, which could be used in interactive design with farmers and advisers.

**Keywords:** Agroforestry; agroecology; ecological interactions; spatial and temporal crop allocation problem; exact discrete optimization methods.

## 1 Introduction

Agroforestry systems are one of the sustainable approaches that has received considerable research attention over the past with a view to ensure high productions, ecosystem services and environmental benefits (Jose, Gillespie, and Pallardy 2004). These systems combine two principal land-use sciences: agriculture and forestry. However, to our knowledge, none of the several studies conducted on agroforestry systems has specifically examined the combination of vegetable crops with fruit trees using a modeling approach. Accordingly, the aim of the present study is to design mixed fruit vegetable cropping systems, which represents a spatial-temporal crop allocation problem. Nonetheless, unlike existing studies in which allocation concerns only annual crops (Akplogan et al. 2013), our system allocates both annual and perennial crops on the same land while minimizing negative above- and belowground interactions resulting from this combination (Batish et al. 2007) and maximizing positive ones (see Figure 1). Moreover, the system should also respect crop rotation decisions (Dury et al. 2012) in order to avoid soil depletion and to increase pest and disease natural regulation.
To assess the validity of the methodological
choice to design mixed fruit-vegetable cropping
systems, we built a first prototype using the
Weighted Constraint Satisfaction framework but
the resolution was limited to small-scale systems
(Tchamitchian and Godin 2014). In the present
study, we explore larger models using solvers
based on Binary Quadratic Programming
(Billionnet 2007) and exact methods. The aim of
this preliminary work is to examine the ability of
exact methods in solving the MFVCS problem in
order to support farmers in their crop allocation
strategies.

The paper is divided into three main parts.

Section 2 describes the conceptual and the mathematical model of a mixed fruit vegetable cropping system, Section 3 presents results and discussion and the final section concludes the paper.

<figure><img src="image_3.png" /><figcaption>**Figure 1.** Example of above- and belowground interactions between crops and trees (Kaeser et al. 2010).</figcaption></figure>

**2 Materials and methods**

**2.1 Mixed fruit vegetable cropping system model**

We define the mixed fruit-vegetable cropping system as a spatial-temporal crop allocation problem in which crops are assigned to a piece of land over a time horizon. For a first model, we decided to discretize the land as a square of l×l cells; every cell represents a unit land area allocated to a fruit tree, a vegetable crop or a bare soil. Concerning the fruit tree, we chose to focus on only one type, apple, in order to study the impact of apple tree on vegetable crops during their various stages of growth. For vegetable crops, we chose a selection that would allow for variable planting dates along the year and would need different cropping durations: lettuce, tomato, onion, melon and carrot. We added a green manure as it is a required practice for the restoration of soil fertility. Indeed, to represent these crops as time passes, we consider a time horizon divided into three periods of four seasons according to tree growth stages; period P1 corresponds to young trees (sprouts), P2 to intermediate growing trees not yet producing fruits (saplings) and P3 to mature trees. Each tree growing period represents a one-year rotation, except P1 which is represented by only one season for the fact that there is no vegetable crops at this period, only green manure to fertilize the soil. Therefore, we have nine time intervals, and thus nine grids of n × n cells in the final model.

<figure><img src="image_4.png" /><figcaption>**Figure 2.** Projection of the perennial structure of a simulated 3-dimensional plum root system of 2, 3 and 4-year-old trees with a detailed view of the branched roots (Vercambre et al. 2003).</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>**Figure 3.** Surface view of root extensions. Grey cells host trees, and checked cells host roots in periods P1, P2 and P3.</figcaption></figure>

Furthermore, this spatial and temporal allocation depends on a complex set of above and belowground interactions. To simplify our model, we only consider classical and potential interactions observed generally in agroforestry systems: due to root extension dynamics as belowground interactions and microclimate modifications and crop sensitivity to shade as above interactions. For belowground interactions, modeling the evolution of the tree root system is based on (Vercambre et al. 2003) model, which is a dynamic 3D representation of the root system architecture of plum. To illustrate, Figure 2 shows the evolution of this root system in the second, third and fourth year after planting a plum. By looking at this figure, we observe that the root system colonizes a large volume of soil; it extends to a depth of 1m per year with well-branched laterals estimated, on average, to 1m
extension per year over the first fourth years. This observation leads to the graphical representation showed in Figure 3.

As above interactions, the shade of a tree takes place only in the spring and summer seasons, given that trees lose their leaves in autumn and winter. The level of solar radiation and the perimeter of the impact zone depend on different factors such as the tree morphology (height, weight and density of crown), the tree age and variety, and the season in the year. A simulation<fnref n="1" /> of the solar radiation interception of an apple tree in either spring or summer gives the results presented in Figure 4. Colors represent the solar radiation interception around the tree. A dark color is used for interception greater than 50% where we cannot plant crops, yellow for interception under 20% which has no effect on crops and finally orange color for interception between 20% and 50% which represents the potential shade. By looking at this figure, we can see few differences in solar interception between spring and summer. We model the same interception for both seasons, representing only the potential shade (see Figure 5).

<figure><img src="image_6.png" /><figcaption>**Figure 4.** Solar radiation interception simulation of an apple tree. Different colors represent levels of solar radiation interception around the tree; more the color is dark, more the solar interception is important.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>**Figure 5.**Evolution of potential shade in spring and summer (checked cells) at periods P1, P2 and P3.</figcaption></figure>

To analyze the impact of shade on vegetable crops, we used the local agricultural advisers' knowledge from Avignon area due to lack of quantitative descriptions in many cases. In this sense, Table 1 represents the degree of sensitivity to solar radiation interception and to microclimate conditions (interception of winds, humidity, lower evaporation rates) for the selected crops according to planting dates and cropping durations along the year.

For belowground interactions, **Erreur ! Source du renvoi introuvable.** illustrates different root systems for the chosen crops; onion roots are poorly branched, melon roots extend horizontally with small depth (2 feet), lettuce roots have well-

branched laterals with a deep taproot (4 feet) rather poorly branched, carrot roots extend vertically (5 feet) with short branches, and finally tomato roots fill the soil on all sides of the plant extending downward (4 feet) into new territory. Inevitably, mixing trees with crops of different root systems leads to a competition or sharing for water and nutrients.

To define the level of competition for water between vegetable crop roots and fruit tree roots, we classify root systems of vegetable crops according to the surface occupied in the depth, starting from 2 feet which corresponds to the level from where tree roots start extending in depth with more branches (see **Erreur ! Source du renvoi introuvable**.). The classification order is as follows: (onion = melon) < lettuce < carrot < tomato. Unlike this competition, associating trees with crops promotes a better use of water thanks to tree root systems, which transfer water from deep soil layers to dry soil (Burgess et al. 1998) and, conversely, recover the excess water that might impair vegetable crop

<table><caption>**Table 1.** Available crop planting seasons (small boxes) and durations in number of seasons (box values). Crop sensitivity to shade in spring and summer (checked cells for other seasons): (-), (0) and (+) mean respectively, a negative, a neutral and a positive effect in a shaded zone.</caption><thead><tr><th rowspan="2">Crops</th><th colspan="4">Seasons</th></tr><tr><th>Winter</th><th>Spring</th><th>Summer</th><th>Autumn</th></tr></thead><tbody><tr><td>Lettuce</td><td></td><td>1 (0)</td><td>1 (+ + +)</td><td>1</td></tr><tr><td>Tomato</td><td></td><td>2 (0)</td><td>(++)</td><td></td></tr><tr><td>Onion</td><td></td><td>2 (-)</td><td>(0)</td><td></td></tr><tr><td>Melon</td><td></td><td></td><td>1 (-)</td><td></td></tr><tr><td>Carrot</td><td></td><td></td><td>2 (0)</td><td></td></tr><tr><td>Manure</td><td></td><td></td><td></td><td>2</td></tr></tbody></table>

<footnote n="1">¹ Using simulation tool, developed by PSH - INRA Avignon</footnote>
growth. In our model, the surplus water exists in all seasons except summer. Hence, at these periods, sharing for water occurs by the presence of a given crop. However, if the crop is planted away from the trees, it may be impaired due to excess water.

<figure><img src="image_8.png" /><figcaption>**Figure 6.** Root systems of vegetable crops (Weaver and Bruner 1927). Crops are classified in ascending order, from left to right, according to the surface of root branching occurred in the depth.</figcaption></figure>

In addition to above- and belowground interactions, we define operation rules related to the organization of crops in the field. The first rule is to maintain a minimal space between trees allowing them a non-conflict growth and a better light distribution. We model this minimal space by one land unit area in horizontal and vertical directions around a tree (see Figure 8). The second rule consists in fixing the number of land units to be allocated to each

crop in order to diversify the food at a given season. To meet this challenge, minimum numbers are chosen so that each season ensures a minimum cultural mixing, while leaving enough free land units to position trees. Maximum numbers correspond to the case where all land units are allocated to vegetable crops without any tree (see Figure 7). The last rule is crop rotation (Mohler, Johnson 2009) is a common practice of growing series of different types of crops in the same area, respecting a minimum return time. As a first model, we only consider the minimum return time of crops, leaving the optimization of crop sequences as future work. Another

desired criterion concerns spatial grouping of vegetable crops, which has a positive effect on the working-time required to cultivate these crops. We model it by penalizing the dispersion of crops over the land, evaluated through the comparison of the value of a given land unit with the value of its horizontal or vertical adjacent land unit.

<figure><img src="image_9.png" /><figcaption>**Figure 8.** Minimal space between trees. Grey cell hosts a tree and checked cells represent zones where the allocation of another tree is forbidden.</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>**Figure 7.** Percentage interval of a piece of land allocated to each crop at a given season.</figcaption></figure>

## 2.2 Mathematical model

In order to solve the MFVCS problem, we reformulate our conceptual model, described in the previous section, as a mathematical model using Binary Quadratic Programming (BQP), which is an NP-hard problem (Sahni 1974). The objective of this approach is to find, given a symmetric $n \times n$ matrix Q ($Q[i, j] = Q[j, i]$) and n-dimensional vector c, a solution vector x that maximizes a quadratic objective function (1) subject to linear constraints (2) where A and b are, respectively, constant $m \times n$ matrix and m-vector.

$$ \max_{x \in \{0,1\}^n} \sum_{i,j}^{n \times n} 0.5 Q[i,j]x[i]x[j] + \sum_{i=1}^{n} c[i]x[i] \quad (1) $$

$$ Ax \leq b \quad \text{or} \quad Ax \geq b \quad \text{or} \quad Ax = b \quad (2) $$
Therefore, solving our model based on BQP requires defining variables, objective function, and linear constraints. Accordingly, we consider the following binary variables:

* $crop_{x,y}^{t,c} = 1$ iff land unit of coordinates $x, y$ has crop $c$ at time $t$

* $tree_{x,y} = 1$ iff land unit of coordinates $x, y$ has a tree

* $shade_{x,y} = 1$ iff land unit of coordinates $x, y$ has shade

* $roots_{x,y}^{p} = 1$ iff land unit of coordinates $x, y$ has roots at period $p$

Let $L=\{1,...,l\}$ be a set of horizontal and vertical land unit positions of a square piece of land, $C$ the set of crops $C = \{onion, melon, lettuce, carrot, tomato, green manure, bare soil\}$, $T$ a set of time steps starting in autumn ($T = \{1,...,9\}$) and $P$ a set of periods of tree growth stages ($P = \{1,2,3\}$) with $T^p$ the set of time steps at each period $p$ ($T^1 = \{1\} \sim \{autumn\}$, $T^2 = \{2,3,4,5\}$, $T^3 = \{6,7,8,9\} \sim \{autumn, winter, spring, summer\}$).

Concerning the objective function, we recall that the purpose of our problem is to design a MFVCS while optimizing above and belowground interactions over time and space. Based on the chosen interactions, we distinguish three situations of a given land unit; situation (SR) where shadow and tree roots are present, situation ($\overline{SR}$) where roots are present without shadow and finally situation ($\overline{SR}$) where both shadow and roots are absent. Additionally, we assign an effect value $Effect_i$ to each situation $i$ according to the nature of interactions (positive or negative) to be maximized by the objective function. This results in the following equation:

$$ \begin{array}{l} \forall p \in P, \forall t \in T^p, \forall c \in C, \forall y \in Y, \forall x \in X, \\ \max \sum_{p,t,c,x,y} [Effect_{SR} \times roots_{x,y}^{p} \times shade_{x,y} + Effect_{SR} \times roots_{x,y}^{p} \times (1 - shade_{x,y}) + \\ \qquad Effect_{SR} \times (1 - roots_{x,y}^{p}) \times (1 - shade_{x,y})] \times crop_{x,y} \end{array} \quad (3) $$

Notice that the presence of shadow in a given land unit at periods 2 and 3 entails the presence of roots (see Figure 3 and Figure 5).

$$ shade_{x,y} \Rightarrow roots_{x,y}^{p} \quad (4) $$

Hence, by using equation (4), the objective function (3) can be simplified to:

$$ \max \sum_{p,t,c,x,y} [A \times shade_{x,y} + B \times roots_{x,y}^{p} + C] \times crop_{x,y}^{t,c} \quad (5) $$

With:

**A:** Values related to the degree of crop sensitivity to shade. According to Table 1, we assign the value 10 to a unit positive effect(+), 0 to a neutral effect (0) and -10 to a negative effect (-) in a shaded land unit.

**B:** Values related to interactions generated by root systems of apple trees and vegetable crops (competition or sharing for water). Based on Figure 6, we have already defined the level of competition for water for the chosen crops: (onion = melon) < lettuce < carrot < tomato). Thus depending on this reverse ranking, we attribute, respectively, the following values: 0, -10, -20, and -30. Then we assign positive values to crops sharing water resources with trees in all seasons except in summer (see Table 2.): 10 to vegetable crops and 20 to green manure.

**C:** Values related to the absence of shade and tree roots at a given land unit, equal to the opposite values of water sharing except for bare soil (see Table 2) and the opposite values related to potential shade in summer: -20 to lettuce summer and -10 to tomato (see Table 1).

In order to reduce the number of land units allocated to bare soil, we add respectively to the corresponding values in A, B and C a value equal to $min(A) - 10$, $min(B) - 10$, and $min(C) - 10$. This minimum value concerns all crops other than bare soil in all seasons (see Table 3).

In addition to the main objective consisting in optimizing tree-crop interactions (5), we model the spatial grouping of vegetable crops as a secondary term in the objective with a value $C_{disp}$ lower than the inverse of summing all of effect values A, B and C. In this sense, term (6) penalizes the spatial

<table><caption>**Table 2.** Effect values of belowground interactions (competition and sharing for water).</caption><thead><tr><th></th><th>Competition</th><th>Sharing</th></tr></thead><tbody><tr><td>lettuce Spring</td><td>0</td><td>10</td></tr><tr><td>lettuce Summer</td><td>-10</td><td>0</td></tr><tr><td>lettuce Autumn</td><td>0</td><td>10</td></tr><tr><td>Tomato</td><td>-30</td><td>10</td></tr><tr><td>Melon</td><td>0</td><td>0</td></tr><tr><td>Carrot</td><td>-20</td><td>10</td></tr><tr><td>Onion</td><td>0</td><td>10</td></tr><tr><td>Manure</td><td>0</td><td>20</td></tr><tr><td>Bare soil</td><td>0</td><td>-10</td></tr></tbody></table>
dispersion of crops, evaluated through a comparison of a given crop allocated to a given land unit at a given time, with the crop present in its horizontal or vertical adjacent land unit.

$$C_{disp} \times [\sum_{t,c,x \in L-\{l\}, y} (1 - \text{crop}_{x,y}^{t,c}) \times \text{crop}_{x+1,y}^{t,c} + (1 - \text{crop}_{x+1,y}^{t,c}) \times \text{crop}_{x,y}^{t,c}) + \\ \sum_{t,c,x,y \in L-\{l\}} (1 - \text{crop}_{x,y}^{t,c}) \times \text{crop}_{x,y+1}^{t,c} + (1 - \text{crop}_{x,y+1}^{t,c}) \times \text{crop}_{x,y}^{t,c}] \quad (6)$$

<table><caption>**Table 3.** Values of objective function (A, B and C) according to crop spaces, seasons and cropping durations. Grey cells indicate cropping duration. Checked cells represent seasons with no shade.</caption><thead><tr><th rowspan="3"></th><th colspan="12">Seasons</th></tr><tr><th colspan="3">winter</th><th colspan="3">spring</th><th colspan="3">summer</th><th colspan="3">autumn</th></tr><tr><th>A</th><th>B</th><th>C</th><th>A</th><th>B</th><th>C</th><th>A</th><th>B</th><th>C</th><th>A</th><th>B</th><th>C</th></tr></thead><tbody><tr><td>lettuce Spring</td><td>■</td><td></td><td></td><td>0</td><td>10</td><td>-10</td><td></td><td></td><td></td><td>■</td><td></td><td></td></tr><tr><td>lettuce Summer</td><td>■</td><td></td><td></td><td></td><td></td><td></td><td>30</td><td>-10</td><td>-30</td><td>■</td><td></td><td></td></tr><tr><td>lettuce Autumn</td><td>■</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>■</td><td>10</td><td>-10</td></tr><tr><td>Tomato</td><td>■</td><td></td><td></td><td>0</td><td>-20</td><td>-10</td><td>20</td><td>-30</td><td>-20</td><td>■</td><td></td><td></td></tr><tr><td>Melon</td><td>■</td><td></td><td></td><td></td><td></td><td></td><td>-10</td><td>0</td><td>0</td><td>■</td><td></td><td></td></tr><tr><td>Carrot</td><td>■</td><td></td><td></td><td></td><td></td><td></td><td>0</td><td>-20</td><td>0</td><td>■</td><td></td><td>-10</td></tr><tr><td>Onion</td><td>■</td><td></td><td></td><td>-10</td><td>10</td><td>-10</td><td>0</td><td>0</td><td>0</td><td>■</td><td></td><td></td></tr><tr><td>Manure</td><td>■</td><td>20</td><td>-20</td><td></td><td></td><td></td><td></td><td></td><td></td><td>■</td><td>20</td><td>-20</td></tr><tr><td>Bare soil</td><td></td><td>-40</td><td>-40</td><td>-20</td><td>-40</td><td>-40</td><td>-20</td><td>-40</td><td>-40</td><td>■</td><td>-40</td><td>-40</td></tr></tbody></table>

To complete the mathematical model, we define the following constraints:
A crop or a tree in each land unit

$$\text{tree}_{x,y} + \sum_{c \in C} \text{crop}_{x,y}^{t,c} = 1 \quad \forall t \in T, \forall x, y \in L \quad (7)$$

Minimal space between trees (see Figure 8)

$$\text{tree}_{x,y} + \text{tree}_{x+1,y} \le 1 \quad \forall x \in L - \{l\}, \forall y \in L \quad (8)$$

$$\text{tree}_{x,y} + \text{tree}_{x,y+1} \le 1 \quad \forall x \in L, \forall y \in L - \{l\} \quad (9)$$

Definition of shadow in the north, east and west of a tree (see Figure 5)

$$-5 \times \text{shade}_{x,y} + \sum_{\substack{i=\max(1-x,-1) \cdot \min(l-x,1) \\ j=0 \cdot \min(l-y,1) \\ i=0 \text{ or } j=0}} \text{tree}_{x+i,y+j} \le 0 \quad \forall x, y \in L \quad (10)$$

$$\text{shade}_{x,y} - \sum_{\substack{i=\max(1-x,-1) \cdot \min(l-x,1) \\ j=0 \cdot \min(l-y,1) \\ i=0 \text{ or } j=0}} \text{tree}_{x+i,y+j} \le 0 \quad \forall x, y \in L \quad (11)$$

Evolution of tree roots (see Figure 3)

$$\text{roots}_{x,y}^{1} - \text{tree}_{x,y} = 0 \quad \forall x, y \in L \quad (12)$$

$$-9 \times \text{roots}_{x,y}^{p} + \sum_{\substack{i=\max(1-x,-1) \cdot \min(l-x,1) \\ j=\max(1-y,-1) \cdot \min(l-y,1)}} \text{roots}_{x+i,y+j}^{p-1} \le 0 \quad \forall p \in \{2,3\}, \forall x, y \in L \quad (13)$$

$$\text{roots}_{x,y}^{p} - \sum_{\substack{i=\max(1-x,-1) \cdot \min(l-x,1) \\ j=\max(1-y,-1) \cdot \min(l-y,1)}} \text{roots}_{x+i,y+j}^{p-1} \le 0 \quad \forall p \in \{2,3\}, \forall x, y \in L \quad (14)$$

Balance of crops (see Figure 7)

$$\text{minBalance}(c) \le \sum_{x,y} \text{crop}_{x,y}^{t,c} \le \text{maxlBalance}(c) \quad \forall t \in T, \forall c \in C \quad (15)$$

Consecutive crops (see Table 1)

$$\text{crop}_{x,y}^{t,c} - \text{crop}_{x,y}^{t+1,c} = 0 \quad \forall p \in P, t \in T^p, \forall x, y \in L, \\ \forall c \in \{\text{onion}, \text{tomato}, \text{carrot}, \text{manure}\} \quad (16)$$

Crop rotation

$$\text{crop}_{x,y}^{t_2,c} + \text{crop}_{x,y}^{t_3,c} \le 1 \quad \forall t_2 \in T^2, \forall t_3 \in T^3, \forall x, y \in L, \\ \forall c \in \{\text{onion}, \text{tomato}, \text{carrot}, \text{melon}\} \quad (17)$$

### 3. Results and discussion

We performed experiments on a virtual farm of 10 × 10 land units, each being from 1m² to 4m². These experiments were subject to three scenarios in order to assess the impact of above and belowground interactions in our model. The first scenario is Above, it gives a significant importance to above
interactions by multiplying the effect values related to shade by 10. Scenario 2 is *Below* and similarly it attaches great importance to roots by multiplying their effect values by 10. The last scenario is *Equilibrate*, it ascribes equal importance to the impact of above and belowground interactions using exactly the effect values described in Table 3. Besides, each scenario is studied for three models: *Basic* for a model optimizing only the main objective (tree-crop interactions) without crop rotation constraints, *Rotation* for the basic model with constraints on crop rotation (17), and finally the model *Dispersion* in which we optimize for the main objective (interactions) with the secondary one consisting of dispersion (6).

We solved these models using the Binary quadratic programming solver IBM ILOG cplex V12.6.3² with default options on 32 cores of an AMD OPTERON CPU 6176 at 2,3 GHz with 378GB of RAM, running Linux 2.6.32. However, despite the number of cores used, the resolution was slow. Table 4 indeed illustrates, for each model, the time elapsed by the solver to find an optimal solution and to prove its optimality. According to this table, the scenario *Equilibrate* is slower than scenarios *Above* and *Below*, because it has to balance above interactions with below ones, unlike the two latter scenarios which give importance to only one type of interactions. Concerning the models, we note that adding constraints or objective terms increases the solving time (see Table 4).

<table><caption>**Table 4.** Elapsed (wall clock) time (hh:mm) taken by cplex -using 32 cores- to find optimal solutions</caption><thead><tr><th colspan="3">Equilibrate</th><th colspan="3">Above</th><th colspan="3">Below</th></tr><tr><th>Basic</th><th>Rotation</th><th>Dispersion</th><th>Basic</th><th>Rotation</th><th>Dispersion</th><th>Basic</th><th>Rotation</th><th>Dispersion</th></tr></thead><tbody><tr><td>31:57</td><td>71:40</td><td>238:55³</td><td>00:10</td><td>00:23</td><td>46:03</td><td>00:32</td><td>04:32</td><td>71:40</td></tr></tbody></table>

Figure 9 shows the spatial balance of crops over the first three years for model *Rotation*. Analyzing scenarios *Above* and *Below*, we notice that the obtained solutions consist of few trees (9%). This is explained by the high level of negative tree-crop interactions, which forces the solver to assign less trees in order to reduce negative interactions. All land units related to the latter are allocated solely to vegetable crops benefiting from these interactions. For instance, lettuce summer which prefers shade represents 88% of spatial balance in scenario *Above* compared to only 25% in scenario *Below*, contrary to onion which represents 100% in scenario *Below* as it benefits from tree roots compared to only 50% (minimum allowed) in scenario *Above*.

Concerning scenario *Equilibrate*, which represents a balanced compromise between interactions, the solution found diversifies the production while having more trees; 23% compared to 9% in the other scenarios.

In order to visualize the obtained results, we represent them as a piece of land, which changes its cultivation over time horizon. Figure 10 shows, as example, the solutions obtained for model *Dispersion* of scenarios *Equilibrate* and *Above*. We note that these solutions satisfy the modeled constraints of shade, tree roots, minimal space between trees, crop rotation (melon, carrot, tomato and onion) and consecutive crops (onion, tomato carrot and green manure). The main difference between these scenarios is in the number and position of trees and crops on the modeled piece of land.

<figure><img src="image_11.png" /><figcaption>**Figure 9.** Percentage of production per crop over the first three years for model *Rotation*.</figcaption></figure>

<footnote n="2">² http://www.ibm.com/support/knowledgecenter/SSSA5P_12.6.3/</footnote>

<footnote n="3">³ 3% to optimum solution</footnote>
For scenario *Equilibrate*, we observe high density of trees, caused by the lack of a diagonal minimal space between trees, and the overall negative effect of interactions. Therefore, to reduce these negative effects while ensuring the minimum allowed production of crops, the solver assigns many land units to trees (not evaluated in the objective function) at the expense of vegetable crops (evaluated by positive or negative effects of interactions with trees. Trees are group together as in a forest to have less land units related to interactions and thus minimum production of vegetable crops with negative effects. Consequently, this leads to a clear separation between the vegetable garden and the orchard, with insertion of some vegetable crops between trees. Concerning scenario *Above*, we notice a spaced disposition of apple trees in sparse groves. One reason is to ensure a sufficient number of land units of shade for the benefit of vegetable crops (e.g. lettuce summer is at maximum allowed production).

<figure><img src="image_12.png" /><figcaption>**Figure 10.** Representation of two successive periods of mixed fruit vegetable cropping systems (10x10 land units) for scenarios *Equilibrate* and *Above*. See color legend of Figure 9.</figcaption></figure>

# 4. Conclusions and perspectives

In this paper, we have modeled a first prototype of a mixed fruit vegetable cropping system (MFVCS) using Binary Quadratic Programming. Unlike existing approaches supporting allocation of annual crops in agroforestry systems, our proposition focuses on the spatial and temporal allocation of both seasonal and perennial crops. We explicitly described the conceptual and mathematical models, detailing the optimization of positive and negative effects of above- and belowground interactions generated by the combination of crops, while respecting the annual crop rotation and a diversified crop production. The results obtained by cplex solver showed the limit of exact methods in solving the MFVCS, in terms of problem size (maximum of 10x10 land units) and execution time. To counter this, a generic approximate method based on heuristics and the local search should therefore be developed, in interactive design with farmers and advisers, in order to tackle large-scale (land of 1ha ~100x100 land units) and more realistic systems.

In the future, we will enhance the ecological side of our model by optimizing interactions between crops and insect-pests (Batish et al. 2007) and by modeling the crop sequences (Mohler, Johnson, and Resource 2009). As regards the economical side, further research should incorporate in the system design the allocation of working time on the farm over the year.

Concerning the approximate method, we will focus on Wedelin's algorithm (named 'In-the-middle'), which has been successfully applied in commercial systems for airline crew scheduling, by providing approximate solutions of good quality in reasonable time (Wedelin 2013).

# REFERENCES

Akplogan M., De Givry S., Métivier J.P., Quesnel G., Joannon A, Garcia F. 2013. *Solving the crop allocation problem using hard and soft constraints*. RAIRO Operations Research. Vol 47, pp 151-172.
Billionnet A. (2007). Optimisation discrète : De la modélisation à la résolution par des logiciels de programmation mathématique. Dunod.

Batish D.R., Kohli, R.K., Jose, S., Singh H.P. 2007. *Ecological Basis of Agroforestry*. CRC Press/Taylor&Francis Group, 400 p.

Burgess, S.S.O., Adams, M.A., Turner, N.C. & Ong, C.K. 1998. *The redistribution of soil water by tree root systems*. Oecologia. Vol. 115, n° 3, pp 306–311.

Dury J., Schaller N., Garcia F., Reynaud A., Bergez J. E. 2012. *Models to support cropping plan and crop rotation decisions. A review*. Agronomy for Sustainable Development, Springer Verlag. Vol 32 (2), pp.567-580.

Jose S., Gillespie A.R., Pallardy S.G. 2004. *Interspecific interactions in temperate agroforestry, Agroforestry Systems* 61: 237–255, Kluwer Academic Publishers. Printed in the Netherlands.

Kaeser A., Sereke F., Dux D., Herzog F., Reckenholz-Tänikon A.R.T. 2010. *Agroforesterie modern en Suisse*. Vergers novateurs: productivité et rentabilité. Tanikon

Mohler Charles L. and Sue Ellen Johnson; 2009. *Crop rotation on organic farms. A planning manual*. Natural Resource, Agriculture, and Engineering Service (NRAES), 156 p.

Sahni S. 1974. *Computationally Related Problems*. SIAM JOURNAL ON COMPUTING. 3, 262-279.

Tchamitchian M., Godin E., 2014. *Designing mixed horticultural systems*. RAHMANN G & AKSOY U (eds.) Proceedings of the 4th ISOFAR Scientific Conference. 'Building Organic Bridges', at the Organic World Congress, Istanbul, Turkey

Vercambre G., Pagès L., Doussan C., Habib R. 2003. *Architectural analysis and synthesis of the plum tree root system in an orchard using a quantitative modelling approach*. Plant and Soil, 251: 1–11, Kluwer Academic Publishers.

Weaver J. E., Bruner W. E. 1927. Root development of vegetable crops. McGRAW-HILL BOOK COMPANY, INC., 254 p. Available at [http://www.sustainablefarmer.com/](http://www.sustainablefarmer.com/)

Wedelin D. 2013. *Revisiting the in-the-middle algorithm and heuristic for integer programming and the max-sum problem*. Chalmers University of Technology.
Available at [http://www.cse.chalmers.se/~dag/in-the-middlePreprint.pdf](http://www.cse.chalmers.se/~dag/in-the-middlePreprint.pdf)