Use of Branch and Bound Algorithms for Greenhouse Climate Control George Dimokas1, Constantinos Kittas2 1 Department of Agriculture Crop Production and Rural Environment, University of Thessaly, Greece, e-mail: gedimokas@gmail.com 2 Department of Agriculture Crop Production and Rural Environment, University of Thessaly, Greece Abstract. Optimization of greenhouse climate management during winter period is an issue that intensely preoccupied researchers over the last two decades as it is directly linked to energy saving, products quality, and reduction of chemical inputs. Goal of this project was the use of Branch and Bound algorithms in order to obtain the optimize greenhouse climate control. For this purpose a biophysical simulator were used and experiments were carried out in the farm of the University of Thessaly in the region of Volos (Greece), during the autumn and winter periods of 2005 and 2007. Branch and Bound algorithms used for two different climate scenarios and the results showed the difference between the classical greenhouse climate control and the control according B & B optimization technique. Finally results showed the contribution of optimization technique to increase tomato production and to reduce energy consumption. Keywords: Branch and Bound Algorithms, Climate Control, Greenhouse, tomato production, optimization. 1 Introduction Most of the greenhouse climate control problems show large number of possible solutions, which are therefore entered the need for finding the best "route" or optimal solution (Dimokas 2009). The use of advanced optimization models, may contribute to the variation of the classical greenhouse climate management during winter period which usually consists in the management of heating by specifying two desired thermostat setting one temperature, for the night and one for day period, based mainly on the producer experience (Tap et al. 1993). The desired values of the temperature setting (set- points) are depending on the type and the age of crop. Nevertheless, experimental work showed that the growth and development of many vegetable and horticultural species appears to respond more to an average daily temperature than on accurate temperature evolution during the day (Heuvelink 1989, Vogelezang et al. 2000). 136 The heating of the greenhouse by the sum of the temperatures (Integrated Temperature Control) during the day has already been applied in several floriculture (Rijsdijk and Vogelezang 2000) and horticultural species (De Konning 1988), allowing an energy saving of about 10 - 20% (Bailey and Seginer 1989). Many experimental projects are referred to optimization of greenhouse climate. The optimal control is one of the processes studied further (van Henten 1994, Tchamitchian and Tantau 1996). According to this method, a model function of the optimization system is used, consisting of differential first degree equations and an algebraic criterion that measures the result quality of this operation. The principle of Bellman (Bellman 1957), allows to solve the problem with dynamic programming, while the principle of Pontryagin (Pontryagin et al. 1962) uses the Lagrange multipliers to convert the power system model and the algebraic criterion to one function for minimization. These experimental works have not yet reached to commercial systems. Goal of this project was the use of Branch and Bound algorithms in order to obtain the optimize greenhouse climate control for energy saving. 2 Material & Methods Branch and bound (BB or B&B) is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as general real valued problems. A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means of state space search: the set of candidate solutions is thought of as forming a rooted tree (Figure 1) with the full set at the root. The algorithm explores branches of this tree, which represent subsets of the solution set. Before enumerating the candidate solutions of a branch, the branch is checked against upper and lower estimated bounds on the optimal solution, and is discarded if it cannot produce a better solution than the best one found so far by the algorithm. S (Α) S S1 S1 S2 S3 S4 (Β) S4 S2 S3 S1 S31 S21 S21 S22 S 31 S32 (C) S22 S32 S3 Fig. 1. Display in the form of a tree Branch & Bound method. The method of branching and bounding (Branch & Bound) has found application in solving various and important optimization problems, eg, in integer programming, nonlinear problems, programming problems, plant sitting problems (Dimokas 2009). 137 2.1 Optimization Method for Greenhouse Climate Control Optimization of the biophysical simulator with the use of Branch & Bound method uses a space selection strategy in order to be investigated in accordance with the algorithms (1), (2) below. The algorithm (1), is responsible for setting the (Vh) ventilation (system controller) inside the greenhouse RH − pRT 1 (1) Vh = 0.1 ⋅ (1 + ( )) + pb1−Ti ( Abs ⋅ ( RH − pRT )) + 0.5 ( pc1 ) e⋅ where pb1, pc1, pRΤ, the values of the variables that have to be optimized in order to give the best solution. At the same time the algorithm (1), uses the biophysical simulator and more specifically the results obtained for the relative humidity (RH) and the air temperature inside the greenhouse (Ti), during the process of optimization. The algorithm (2) below is responsible for determining the operation of the (Vt) heating system (system controller) within the greenhouse. RH − pRT 1 (2) Vt = 0.1 ⋅ (1 + ( )) + pb 2 − DTi ( Abs ⋅ ( RH − pRT )) + 0.5 ( pc 2 ) e⋅ where pb2, pc2, pRΤ, the values of the variables that have to be optimized in order to give the best solution. At the same time the algorithm (2), uses the biophysical simulator and more specifically the results obtained for the relative humidity (RH) and the air temperature difference inside and outside the greenhouse (DTi), during the process of optimization. The problem to be solved is to minimize the objective function J to a range of possible solutions, S: min J = ∑ ( Fcon) − ∑ ( D.W .F ) (3) where ∑ ( Fcon) is the total energy gives the heating system inside the greenhouse, while respectively ∑ ( D.W .F ) the resulting dry weight of mature fruit. The limiting function used to optimize the biophysical simulator using Branch & Bound method shown below: min J (one) > max J (other ) (4) Function (4) reject some subset of possible solutions by further exploring inside, to find the possible solution when the above condition is true, that the optimal minimal solution that offers the particular subset is greater than the largest value of another subset. 138 2.2 Climate and Biological Measurements The measurements that used to optimize the model were data for tomato production and development simultaneously with the greenhouse climatic data, during the autumn and winter periods of 2005 and 2007. For the experimental periods were used also calculated values by the modified TOMGRO (Dimokas et. al., 2009), for: i) plant development and the number of leaves, fruits, flowers, ii) biomass and fruit production. The aim was to identify differences between the optimization method, and the climate control during the experimental period. 3 Results This section presents results of treatment followed during the experimental measurements and optimum proposed in accordance with the branch & bound method. The results are giving detailed greenhouse climatic conditions and all features related to the development and production of tomato plants. From these were selected and are presented in the following sections the results concerning: a. number of plants node, b. shoot dry weight, c. leaves dry weight, d. whole plant dry weight, e. simulation curve of windows opening, f. air temperature inside the greenhouse, g. temperature of the greenhouse cover. Values that are used as input variables for the number of nodes, dry weight of leaves, stems and fruits are the same that used of the modified TOMGRO. 3.1 Results of the first simulated period Initially a variation was observed in greenhouse air - cover temperature and presented in Figures 2 and 3. The optimum calculated values fall short of measured values and this is due to the diversification arising from the way of windows opening. Control of when and how much, windows are opening through the use of the algorithm (1) are indicated in Figure 5. Time variation of window opening rate leads to both reduce the temperature and reduce the humidity inside emissions (data not shown). Figures 4 (a-d) are showing the variation of calculated values using the modified TOMGRO, and the optimum values obtained after the use of branch & bound method for the number of nodes, dry weight of stem, leaves and whole plant correspondingly. In Figure 4 (a) observed that the climate change does not change the number of plant nodes formed. Correspondingly there is no change at the number of leaves and the number of produced flowers (data not shown). Variation is observed in Figure 4 (b) showing the dry weight of the shoot. The calculated optimal values are above those calculated by the modified TOMGRO. Reverse change is observed in the dry weight of leaves Figure 4 (c), wherein the optimum values are below those estimated by the modified TOMGRO. Smaller differences observed in Figure 4 (d) illustrating the total output of the plant biomass. The differences are due to the diversification of air temperature 139 values, Figure 2. Reduction of air temperature leads to a small hysteresis of growth and development of tomato plants. The reduction in biomass production when the plants are in the initial stage of development helps to create more robust plants and there is a regular practice for the producers that mainly use the chemical composition of the nutrient solution and the irrigation dose to achieve it. 3.2 Results of the second simulated period Figures 8 (a-d) are showing the variation of calculated values by using the modified TOMGRO and best values obtained after the use of the branch & bound method on the number of nodes and dry weight of the shoot, leaf and whole plant respectively for the second experimental period. In Figure 8 (a) is observed that the best calculated values relating to the formation of nodes, are slightly below than those created by the modified TOMGRO. The growth rate resulting from the optimum climate management is less than the one followed during the experimental period. Simultaneously a reduction is presented for the values of shoot dry weight, leaves dry weight and whole plant biomass. The reduction is almost 15.5% for shoot dry weight, 18.5% for leaves dry weight and 17.4% for whole plant dry weight. The decrease results from lower average value for the air temperature, kept inside the greenhouse (Figure 6). It is observed that during the experimental period air temperature was maintained above the fixed price of 15 oC. A similar differentiation was observed in cover temperature as shown in Figure 7. The gain from the use of Branch and Bound method was observed and that was the reduction of heating system cost that was calculated 19.72% compared to the initial treatment. The reduction in production costs resulting from the reduction of the heating system cost may lead to a reduction in growth and development of production, but may be a target for the producers. The decrease that caused to plants growth and development can be balanced by increasing the temperature inside the greenhouse to a period prior or after the reduction. This will give to the producers smaller costs for the climate management and simultaneously energy saving. 4 Discussion & Conclusions The results presented above were according two different climate scenarios within greenhouses, with simultaneous display of the changes caused in the development and production of the tomato crop. The periods used were selected of producer’s interest and was at the start of the growing season and the second in the medium. The study of the results for the first scenario, it is established that the reduction of air temperature contributes to the reduction of both dry weight of leaves and whole plant. The decrease in air temperature was due to the different treatment of the windows operating system (system controller and B & B method). 140 40 35 Air Temperature (o C) 30 25 20 15 10 5 0 9/10/2007 10/10/2007 11/10/2007 12/10/2007 13/10/2007 14/10/2007 Days Fig. 2. Variation of measured (–) and optimally calculated (-) values, for air temperature (oC) during the first simulated period. 50 45 Cover Temperature (o C) 40 35 30 25 20 15 10 5 0 9/10/2007 10/10/2007 11/10/2007 12/10/2007 13/10/2007 14/10/2007 Days Fig. 3. Variation of measured (–) and optimally calculated (–) values, for cover temperature (oC) during the first simulated period. The practice followed in accordance with the use of branch & bound method leads to an opening of a greenhouse window for longer period than that followed in the experimental procedure. However, the reduction of biomass produced when the plants are in the initial stage of development helps to create more robust plants in the future. 141 10 1 (c) Dry weight of leaves (g plant-1 ) ) -1t (a) 0,8 n a l p 9 0,6 o (n se d o 0,4 n fo 8 er 0,2 b m u N 0 7 0 1 2 3 4 5 0 1 2 3 4 5 Days Days 1 ) 1,4 0,6 -t n ) (b) la 1,2 p (d) -1t 0,5 (g 1 t an l n p 0,4 la g( p 0,8 fo s t m e 0,3 h 0,6 st ig e f w 0,4 o t h 0,2 ry ige d l 0,2 w ta yr 0,1 o T 0 D 0 1 2 3 4 5 0 Days 0 1 2 3 4 5 Days Fig. 4 (a), (b), (c), (d). Variation of calculated values according modified TOMGRO ( ) and the optimal values according B & B algorithms ( ), growth and biomass production of tomato plants, during the first simulated period. 100% Percentage of Window Opening (%) 90% 80% 70% 60% 50% 40% 30% 20% 10% 0% 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 Air Temperature (o C) Fig. 5. Percentage (%) of window opening (-), during the first simulated period. By observing the results of the second scenario it was found that the reduction of production costs by 19.72% led to a corresponding reduction of the biomass production by 15.5% of shoot dry weight, 18.5% of leaves dry weight and 17.4% of whole plant dry weight. However, the reduction caused in plants growth and development can be balanced with an increase in air temperature inside the greenhouse to a period prior to the reduction. 25 20 Air Temperature (o C) 15 10 5 0 28/11/2007 29/11/2007 30/11/2007 1/12/2007 2/12/2007 3/12/2007 4/12/2007 Days Fig. 6. Variation of measured (–) and optimally calculated (-) values, for air temperature (oC) during the second simulated period. 25 Cover Temperature (o C) 20 15 10 5 0 28/11/2007 29/11/2007 30/11/2007 1/12/2007 2/12/2007 3/12/2007 4/12/2007 Days Fig. 7. Variation of measured (–) and optimally calculated (-) values, for cover temperature (oC) during the second simulated period. Managing greenhouse climate as mentioned is a daily activity for the producers, which despite its frequency poses many problems. Further analysis of possible climate scenarios will help to create strategies that will shape the conditions for reducing production costs and improving the climate inside the greenhouse units. 143 15,0 5,0 (c) Dry weight of leaves (g plant-1 ) (a) Number of nodes (no plant-1 ) 4,0 14,0 3,0 13,0 2,0 12,0 1,0 11,0 0,0 0 1 2 3 4 5 0 1 2 3 4 5 Days Days 3,0 7,0 Total dry weight of plant (g plant-1 ) (b) (d) Dry weight of stmes (g plant-1 ) 2,5 6,0 5,0 2,0 4,0 1,5 3,0 1,0 2,0 0,5 1,0 0,0 0,0 0 1 2 3 4 5 0 1 2 3 4 5 Days Days Fig. 8 (a), (b), (c), (d). Variation of calculated values according modified TOMGRO ( ) and the optimal values according B & B algorithms ( ), growth and biomass production of tomato plants, during the second simulated period. 100% 100% Percentage of Heating System Opening (%) 90% 90% Percentage of Window Opening (%) 80% 80% 70% 70% 60% 60% 50% 50% 40% 40% 30% 30% 20% 20% 10% 10% 0% 0% 0 5 10 15 20 25 30 Air Temperature (o C) Fig. 9. Percentage (%) of window (-) and heating system (–) opening during the second simulated period. Acknowledgments. This paper is part of the 03ED526 research project, implemented within the framework of the “Reinforcement Program of Human Research 144 Manpower” (PENED) and co-financed by National and Community Funds (25% from the Greek Ministry of Development-General Secretariat of Research and Technology and 75% from E.U.-European Social Fund). References 1. Bailey, B.J., Seginer, I., (1989) Optimum control of greenhouse heating. Acta Horticulturae 245, p. 512-518. 2. Bellman, R.E., (1957) Dynamic programming. Princeton, New Jersey, USA: Princeton University Press. 3. de Koning, A.N.M., (1988) The effect of different day/night temperature regimes on the growth, development and yield of glasshouse tomatoes. Journal of Horticultural Science, 63 (3), p. 465-471. 4. Dimokas, G., (2009) Development of a biophysical simulator for tomato crop in order to optimize climate management for Mediterranean greenhouses during winter period. Ph.D. Thesis, University of Thessaly, p. 1-332. 5. Dimokas, G., Tchamitchian, M., Kittas, C., (2009) Calibration and validation of a biological model to simulate the development and production of tomatoes in Mediterranean greenhouses during winter period. Biosystems Engineering 103 (2), p. 217-227. 6. Heuvelink, E., (1989) Influence of day and night temperature on the growth of young tomato plants. Scientia Horticulturae, 38, p. 11-22. 7. Pontryagin, L.S., Boltyanskii, V.G., Gamkrelidze, R.V., Mishchenko, E.F., (1962) The mathematical theory of optimal processes. New-York, USA: Wiley Interscience. 8. Rijsdijk, A.A., Vogelezang, J., (2000) Temperature integration on a 24 hour basis: a more efficient climate control strategy. Acta Horticulturae, 519, p. 163- 170. 9. Tap, R.F., van Willigenburg, L.G., van Straten, G., van Henten, E.J., (1993) Optimal control of greenhouse climate: computation of the influence of fast and slow dynamics. 12th IFAC Triennial World Congress, Sydney, Australia, Volume 4, 4pp. 10. Tchamitchian, M., Tantau, H.J., (1996) Optimal control of the daily greenhouse climate: physical approach. 13th IFAC Triennial World Congress, San Francisco, USA, Volume B, p. 471-475. 11. van Henten, E.J., (1994) Greenhouse climate management: An optimal control approach. Ph.D. Thesis, Wageningen Agricultural Univericity, Wageningen, The Netherlands, p. 1-319. 12. Vogelezang, J., de Hoog, J., Marissen, N., (2000) Effects of diurnal temperature strategies on carbohydrate content and flower quality of greenhouse roses. Acta Horticulturae 515, p. 111-118. 145