On a mixed zero-one separable non-linear approach for water irrigation scheduling.

1. Introduction

In 1968 the Council of Europe published the European Water Charter (http://assembly.coe.int/), which states fundamental principles for the conservation of water resources and criteria for their rational use. Besides enunciating the fundamental principles for the protection of this indispensable vital resource, particularly under items 7 and 8, the European Water Charter points out the need for the inventory, control and management of water resources.

The need

for rational water management has become greater in many Mediterranean regions as a result of changes in the availability of water, changes in the general climatic conditions and the adverse effect of the actions of humans on the environment.

The complexity of water-related problems in Mediterranean regions is escalating as the use of water and the (environmental and other) objectives to be met continue to increase; see Balabanis et al (2000) and the references therein for details. Most of the simpler structural solutions for improved water utilization have been already implemented. In these circumstances, the need for rational water resources planning and scheduling is becoming greater than ever as a result of the impact of changes in the general climatic conditions and the increasing demand for water.

Water is no longer a free asset but rather an economic and environmental asset. A change in philosophy is needed; rather than trying to meet increasing demands for water and devising new costly supply sources, one should strive towards increasing efficiency in the use of water, that is, endeavor to do more with less.

The ability to help the decision maker in the planning and distribution scheduling of water resource systems depends on the level of sophistication of the available tools and techniques. A comprehensive approach may remedy the inadequacies of the tools currently available, by developing a hydrologic modeling framework and a highly numeric intensive computation decision support system. See Labadie et al. (1989), Loucks and Da Costa (1991), Loucks (1992) and Marco et al. (1993) and the references therein.

We should differentiate between water resources planning, which is usually long-term planning, and water distribution scheduling, which is usually performed on a daily basis. In the case of planning, see Andreu et al. (1996) for the deterministic environment and Pereira and Pinto (1991) and Escudero (2000) for the stochastic case. This is done by considering the uncertainty in the main parameters (i.e., water inflow and needs). Moreover, water distribution scheduling is a large-scale problem that requires a solution in a brief period of time (the time horizon is usually a day). For overviews of earliest/tardiness scheduling problems see e.g., Pinedo (1995) and Brucker (2001).

The aim of this paper is to develop a methodology to help produce irrigation scheduling policies for the use of water resources in a given area. It has been recognized that water supply problems constitute an obstacle in the regional development of Eastern Spain. Thus, a semi-arid region in this location has been selected as a pilot area thereby creating a real-life case. The interest in evaluating the benefits of the better use of water irrigation resources and needs in Spain are justified in Gomez-Limon and Martinez (2006).

We present a mixed zero-one separable non-linear model for managing the water irrigation scheduling of a given agricultural area. It is solved by successively optimizing mixed zero-one linear programs. (For a good explanation of mixed zero-one linear programming, see e.g., Wolsey (2000)). See Reddy et al. (1999) and Anwar and Clarke (2001) for other mixed-integer LP programs for the irrigation scheduling problem. In particular, the model presented in Reddy et al. (1999) has a strong connection with our work, but it functions with open channels and so does not consider the loss of pressure due to friction in the pipes. However, the constraints on the discharge of water are similar in both studies. Our approach meets the demands for water and the technical constraints on the pressure and the velocity of the water flow through the network of pipes under consideration, as well as other constraints, related more to the logistics of the problem. Given that there are several thousand hydrants in a real-life case, the problem can have several tens of thousands of (zero-one and continuous) variables and several tens of thousands of linear and non-linear constraints. We are not aware of any previous attempt to solve large-scale mixed zero-one separable non-linear programs of this kind.

The remainder of the paper is organized as follows. Section 2 presents a description of the main features of the problem. Section 3 introduces the parameters and variables of the proposed model. Section 4 presents the mixed zero-one separable non-linear model. Section 5 deals with the iterative approach for program solution. Section 6 reports our computational experiences with a large-scale real-life problem in addition to realistic problems. Conclusions are drawn in Section 7.

2. Problem description

Consider the problem of an agricultural area that needs to be irrigated on a daily basis with water that flows from a reservoir, through a pipe network arranged in a tree-like structure. There are three types of elements in the pipe system: sector head nodes; hydrant nodes; and bifurcation nodes. The last two types of nodes are also called non-head nodes, and they are grouped in sectors which start from the sector heads. These other sectors are interconnected in the opposite direction to the reservoir, and constitute the set of root nodes of the sector subtrees. Figure 1 illustrates the topology of the system.

Each sector head has a given elevation and a given water pressure. The irrigation is performed daily in a certain set of consecutive time periods (in our case, five periods of 4 h each). Depending on the size of the area to be irrigated by a hydrant, it has the right to be irrigated for a certain duration. Some hydrants can be used in all the time periods. The set of hydrants used to irrigate a certain land area during a time period must satisfy the demand for water and some technical constraints, such as the minimum water pressure and a maximum velocity in their upstream pipe segments.

[FIGURE 1 OMITTED]

The water pressure at a given hydrant is a function of the pressure at its sector head, the elevation difference between the sector head and the given hydrant, and the head loss which is described below. Furthermore, some additional pieces of information are taken into account in the irrigation scheduling problem. First, the sector heads and the bifurcation nodes allow the appropriate water flow distribution, but they do not have their own water needs. Second, the time periods for irrigation should be non-preempted (i.e., once the irrigation begins using a hydrant it cannot be interrupted). Third, it is assumed that there is enough water in the reservoir to satisfy the water requirements. Thus, the problem lies in the distribution system. When there are water restrictions, the proposed approach can also help the system operator by suggesting reductions or cuts in the demands for water.

Given an irrigation network, the system operator assigns a priority to each hydrant for each time period. Hence, the problem involves the selection of the hydrants for irrigation at each time period, such that the sum of the priorities is maximized and the technical and logistical constraints are satisfied in the given time frame. The constraints are the satisfaction of the daily water demand of the hydrants for given consecutive time periods, the maximum water velocity and the minimum pressure in the pipe segments.

Moreover, the decision support system based on the proposed model and algorithm allows the system operator to partially irrigate some fields on a given day. This feature plus the tuning of the priority coefficients, makes it possible to achieve a high priority for irrigation on the following day, in the event that a water user did not receive the required amount of water the preceding day.

3. Parameters and variables

In order to mathematically describe the irrigation scheduling problem, we need to take into account the technical, topographical, logistic and irrigation scheduling parameters. The technical and topographical parameters are related to physical properties of the water. The logistic parameters are related to the management of the irrigation system and the irrigation scheduling parameters are related to constraints on how to assign the time periods of the irrigation. Finally, the continuous variables are related to the water discharge in each node for each time period and the zero-one variables are related to the periods at which the hydrants are used for irrigation.

The notations for all relevant elements and parameters in the system are listed in Tables 1-5.

4. Model

The objective is to operate (turn on) the maximum number of hydrants with the highest priority factor formulated below in Equation (1). The pressure head at any hydrant must not fall below the specific threshold. This constraint is formulated by employing the Darcy-Weisbach equation, Equation (2). The discharge of water through each node during each time period is defined by Equation (3). The water flow velocity allowed along the immediate upstream pipe segment of any node is enforced by Equation (4). The irrigation must not be interrupted, thus a hydrant can only be turned on once by following Equation (5), and it is kept open during the time periods t, t + 1,..., t - [^.N.sub.j] + 1 by following Equation (3). Equation (6) fixes the irrigation schedule for some hydrants, due to logistics considerations imposed by the system operator. Note that the index [tau] has to be strictly positive and not greater than |T|, see objective function (1) and Equation (3).

The mathematical expression of the model is as follows:

max [summation over (i[member of]I-[I.sub.0])] [summation over (t[member of]T)] [c.sub.it][y.sub.it], (1)

subject to

[H.sub.[gamma](i)] + [E.sub.[gamma](i)] - [E.sub.i], - [summation over (j[member of][R.sub.i])] ([[8[f.sub.jt][L.sub.j]]/[[[pi].sup.2]g[D.sub.j.sup.5]]] [q.sub.jt.sup.2]) [greater than or equal to] [H.sub.min], [for all]t [member of] T, i [member of] I - [I.sub.0], (2)

[q.sub.it] = [summation over (j[member of][S.sub.i]-[I.sub.0]-[GAMMA])] K[F.sub.j]([summation over ([tau]=t-[^.N.sub.j]+1,..., t)][y.sub.j[tau]]), [for all]t [member of] T, i [member of] I [union] [GAMMA], (3)

(4/[[pi][D.sub.i.sup.2]])[q.sub.it] [less than or equal to] [V.sub.max], [for all]t [member of] T, i [member of] I [union] [GAMMA], (4)

[summation over (t[member of]T)] [y.sub.it] = 1, [for all]i [member of] I - [I.sub.0], (5)

[y.sub.it] = [^.y.sub.it], [for all]i [member of] [I.sup.[tau]], [tau] [member of] T, (6)

[y.sub.it] [member of] {0, 1}, [for all]t [member of] T, i [member of] I - [I.sub.0]. (7)

The program (1)-(7) has three blocks, namely, the technical and topographical subsystem that consists of Equations (2)-(4), the irrigation scheduling block that consists of Equation (5), and the logistic block that consists of the objective function, the fixing bound (6) and the parameter [F.sub.j] in Equation (3).

5. Algorithmic framework

5.1. Computing the friction factor [f.sub.ht]

The mixed zero-one program (1)-(7) has an additional difficulty. It is the computation of the friction factor [f.sub.it] in the calculation of the head loss in order to obtain the pressure in the immediate upstream pipe segment of the hydrant i, for i [member of] I - [I.sub.0]. This friction factor can be calculated by using the Colebrook-White equation (see e.g., Colebrook (1938) and Lester (2002)); it has the following expression, where the subindices t and i have been omitted:

1/[square root of f] = -2 log ([[epsilon]/3.71D] + [2.51v/[VD[square root of f]]]), (8)

where [[epsilon].sub.i] is a constant that is related to the roughness of the immediate upstream pipe segment of hydrant i, v is the water kinematic viscosity and V is the water flow velocity that can be calculated using the expression:

V = (4/[[pi][D.sup.2]])q. (9)

The computation of f will be iteratively performed at each outer iteration of the algorithm for a given water discharge through the hydrants. Considering Equation (8) as a nonlinear equation in f, we make use of the Newton-Raphson procedure to obtain its roots. This procedure starts with a value of f obtained by using only the first term of the right-hand side of the Colebrook-White formula, and approaches the root by steps which are proportional to the quotient of the function (8) and its derivative. (An explicit calculation of the friction factor for a set of special pipes is presented in Yoo and Sing (2004).)

5.2. Iterating a mixed zero-one linear problem

The constraints (2) have the quadratic term [q.sub.jt.sup.2], for j [member of] [R.sub.i], t [member of] T, i [member of] I - [I.sub.0]. It can be approximated by the Taylor series expansion:

[q.sub.jt.sup.2] [approximately equal to] [^.q.sub.jt.sup.2] + 2[^.q.sub.jt]([q.sub.jt] - [^.q.sub.jt]), (10)

where [^.q.sub.jt] is the value from the optimization of the model in the previous iteration, see Stephanopoulos and Westerberg (1975).

The algorithm for solving the original problem (1)-(7) in an outer iterative way is as follows.

Step 1. Compute the friction factor [f.sub.it] in Equation (8), such that q is replaced by [^.q.sub.it] in Equation (9).

Step 2. Solve the mixed zero-one model (1)-(7), where the function [q.sub.jt.sup.2] is substituted by its linear approximation (10). Let [q*.sub.it] denote the optimal value of the variable [q.sub.it] [for all]i [member of] I, t [member of] T.

Step 3. Optimality test. If condition (11) is satisfied then stop, the quasi-optimal solution has been obtained. Otherwise, go to Step 4.

[summation over (t[member of]T)][summation over (i[member of]I)]([q*.sub.it] - [^.q.sub.it])[.sup.2] [less than or equal to] [sigma], (11)

where [sigma] is a positive tolerance.

Step 4. Update:

[^.q.sub.it] [colon, equals] [^.q.sub.it] + [phi]([q*.sub.it] - [^.q.sub.it]), [for all]i [member of] I, t [member of] T, (12)

where 0 < [phi] [less than or equal to] 1, and go to Step 1.

6. Computational experience

6.1. Pilot case description

The approach presented in this work was used to solve a real-life problem presented by "La Comunidad de Regantes, Riegos de Levante, Canal 2nd", which is located in Eastern Spain. Its irrigation area consists of 2188 Ha and is distributed in 20 pipe sectors (i.e, 20 head nodes) with a total number of 2831 nodes (2025 of them are hydrants with their own water requirements). The irrigation is needed on a daily basis for |T| = 5 time periods (4 h each, and the additional time period is devoted to maintenance operations). The topography of this problem is depicted in Fig. 2. Because of the size of the land area to be irrigated, we need 1791 hydrants in time period 1, 191 hydrants in time period 2, 43 hydrants in time period 3 and no hydrants for time periods 4 and 5. The water flows from a reservoir with a capacity of 13 H[m.sup.3], and the full system has an free-like structure. The technical and topographic parameters are as follows: K = 2.3 1/sec/ha, [H.sub.min] = 2.5 Kg/[cm.sup.3], [V.sub.max] = 2.5 m/sec, [H.sub.[gamma]] = 40 [for all][gamma] [member of] [GAMMA], [epsilon] = 0.003 mm and v = 1.08 x [10.sup.-6] [m.sup.2]/s. The pipe length [L.sub.i] and the pipe diameter [D.sub.i] vary from 0 to 691 m and from 66 to 800 mm, respectively, for i [member of] I [union] [GAMMA].

[FIGURE 2 OMITTED]

Note that the instances of this experimentation are available on request from the authors for academic/research purposes only.

6.2. Numerical results

The proposed approach was programmed in C. It uses the optimization engine CPLEX v9.1 for solving the linear approximation of the mixed zero-one non-linear program (1)-(7). The computational experiments were conducted on a SUN Workstation W2100 with a 2.6 GHz Opteron processor, 4 GB of RAM and the operative system Linux Enterprise 3.

The objective function coefficients were generated according to the following probability distributions:

D0_L-U: Uniform random priority [c.sub.it] in the range [L, U] for each hydrant and time period.

D1_L-U: Decreasing random priority [c.sub.it] in the range [L/[2.sup.t-1], U/[2.sup.t-1]] for time period t and each hydrant.

D2_C: Constant priority, [c.sub.it], for each hydrant and time period t; [c.sub.i1] = C, [c.sub.i2] = C/2,..., [c.sub.it] = C/[2.sup.t-1], where C is a given number.

D3_C: Same constant priority [c.sub.it] for all hydrants and periods.

The distributions D1_L-U and D2_C consider the situation in which the users of the system prefer the first time periods in the time horizon. The distribution D3_C is intended for the case in which the system operator requires a feasible solution and does not have information as to the preferences of the users.

Table 6 shows the model dimensions of the linear approximation problem. The headings are as follows: m is the number of constraints, [n.sub.c] is the number of continuous variables, n01 is the number of integer zero-one variables, nel, is the number of non-zero elements in the constraint matrix and dens is the constraint matrix density.

Table 7 shows some solution information in several instances for an optimality gap of 0.05% in the linear mixed zero-one solution value. The headings of Table 7 are as follows: [Z.sub.IP] is the solution value obtained by the proposed approach; niter is the number of outer iterations of the algorithm presented in Section 5.2; t is the elapsed time required by the number of iterations; nn is the number of branch-and-bound nodes. Notice that a case whose dimensions are given in Table 6 is solved at each outer iteration.

The maximum number of allowed outer iterations is 100, the time limit is 3600 s, and [sigma] = 0.5, a very small value compared with the objective function values.

The main conclusions that can be drawn from the results shown in Table 7 are the extremely small elapsed time required in all instances and the three tested values of parameter [phi], see Equation (12). The best results are obtained for [phi] = 0.8. Note that only a second (on average) is needed each time the mixed zero one linear problem is optimized. The number of nodes is also very small, such that the system does not need to branch out; it is an indication of the tightness of the model and the quality of the CPLEX heuristic routines. Notice that the value [Z.sub.IP] does not differ from the optimal solution in more than the optimality gap, 0.05%. In our case there is not a lower value based on the linear programming relaxation solution value, since the linear model is only an instrument of the approach to be executed at each outer iteration of the algorithm.

The sets of hydrants required to irrigate the land will almost certainly be changed at a future date by the system operator and the water users. Thus, we have, in addition, generated realistic instances by randomly increasing the number of hydrants by 4%. The new hydrants have the right to irrigate throughout five consecutive periods during the day. Table 8 shows the results for the realistic instances. Again, the best performance is for [phi] = 0.8. In any case, the elapsed time is also extremely small.

The time limit has been released for the instances shown in Tables 9 and 10 for a CPLEX default optimality gap of 0.01%, since the elapsed time for the instances D2_100 and D2_1000 is greater than for an optimality gap of 0.05%. These times should be short enough taking into account the daily nature of the irrigation scheduling, but they do not permit different trials by varying the parameters of the problem. Obviously, there is not a significant difference in the solution value for the 0.05 and 0.01% optimality gaps. Moreover, the former has a much better time performance than the latter.

7. Conclusions

In this paper we have presented a model and an algorithm for irrigation scheduling by using as a pilot case a real-life problem from a land area of Eastern Spain. The model is a very tight large-scale mixed zero-one separable non-linear program. It is solved by successively optimizing a mixed zero-one linear program approximation, and usually takes a very short elapsed time. The computational results lead us to consider, in a future work, the use of the proposed approach in an extension of the irrigation network.

Acknowledgments

This research was partially supported by the grants MTM2004-01095 from the Spanish Ministry of Education and Science, and GV04B/655, GV05/077 and GRUPOS79/04 from the Generalitat Valenciana, Spain.

References

Andreu. J., Capilla J. and Sanchis. E. (1996) AQUATOOL, a generalized decision-support system for water-resources planning and operational management. Journal of Hydrology, 177, 269-291.

Anwar, A.A. and Clarke, D. (2001) Irrigation scheduling using mixed-integer linear programming. Journal of Irrigation and Drainage Engineering, 127(2), 63-69.

Balabanis, P., Peter, D., Ghazi, A. and Tsogas, M. (eds) (2000) Mediterranean Desertification: Research Results and Policy Implementation, European Commission, Belgium. EUR 19303.

Brucker, P. (2001) Scheduling Algorithms, Springer, Berlin.

Colebrook, C.F. (1938) Turbulent flow in pipes, with particular reference to the transition region between the smooth and rough pipe laws. Journal of the Institute of Civil Engineers, 11, 133-156.

Escudero, L.F. (2000) WARSYP, a robust approach for water resources planning under uncertainty. Annals of Operations Research, 95, 313-339.

Gomcz-Limon, J.A. and Martinez, Y. (2006) Multi-criteria modelling of irrigation water market at basin level: a Spanish case study. European Journal of Operational Research, 173, 313-336.

Labadie, J.W., Brazil, I.E., Corbu, I. and Johnson, L.F. (eds.) (1989) Computerized Decision Support Systems for Water Managers, American Society of Civil Engineers, New York, NY.

Lester, T.G. (2002) Calculating pressure drops in piping systems. ASHRAE Journal, 44, 41-43.

Loucks, D.P. (1992) Water resource systems models: their role in planning. Journal of Water Resource Planning Management, 118, 214-223.

Loucks, D.P. and Da Costa, J.R. (eds) (1991) Decision Support Systems. Water Resources Planning, Springer, Berlin.

Marco, J.B., Harboe, R. and Salas, ID. (eds) (1993) Stochastic Hydrology and its use in Water Resources Systems Simulation and Optimization, Kluwer, Dordrecht, The Netherlands.

Percira, M.V.F. and Pinto, L.M.V.G. (1991) Multistage stochastic optimization applied to energy planning. Mathematical Programming, 52, 359-375.

Pinedo, M. (1995) Scheduling: Theory, Algorithms and Systems, Prentice Hall.

Reddy, J.M., Wilamowski, D.M. and Sharmasarkar, F.C. (1999) Optimal scheduling of irrigation systems. International Commission on Irrigation and Drainage Journal, 48(3), 1-12.

Stephanopoulos, G. and Westerberg, E. (1975) The use of Hestenes method of multipliers to solve dual gaps in engineering system optimization. Journal of Optimization: Theory and Applications, 15, 285-309.

Yoo, D.H. and Singh, V.P. (2004) Explicit design of commercial pipes with no secondary losses. Journal of Irrigation and Drainage Engineering, 130, 437-440.

Wolsey, L. (2000) Integer Programming. Wiley.

Biographies

Marc Alminana (Ph.D. in Mathematics). He is an Associate Professor of Statistics and Operations Research at the Universidad Miguel Hernandez, Elche (Alicante, Spain) and member of its Operations Research Center.

Laureano F. Escudero (Ph.D. in Economic Sciences). He is a full professor of Statistics and Operations Research at the Universidad Miguel Hernandez, Elche (Alicante, Spain) and member of its Operations Research Center. For the period 2003-2004 he was the President of EURO, The Association of European Operational Research Societies. He has worked in the following IBM scientific centers: Centro Cientifico de Madrid (Spain), Palo Alto Scientific Center (California), German Manufacturing Technology Center (Sindelfingen, Germany), and T.J. Watson Research Center in Yorktown Heights (NY, USA).

Mercedes Landete (Ph.D. in Mathematics). He is an Associate Professor of Statistics and Operations Research at the Universidad Miguel Hernandez, Elche (Alicante, Spain) and member of its Operations Research Center.

Juan F. Monge (Ph.D. in Mathematics). He is an Associate Professor of Statistics and Operations Research at the Universidad Miguel Hernandez, Elche (Alicante, Spain) and member of its Operations Research Center.

Alejandro Rabasa is an Associate Professor of Computer Science at the Universidad Miguel Hernandez, Elche (Alicante, Spain) and member of its Operations Research Center.

Joaquin Sanchez-Soriano received a Mathematical Sciences Degree and a Ph.D. in Mathematical Sciences from Murcia University, Spain. At present, he is an Associate Professor in the Department of Statistics, Mathematics and Computer Science, and the Director of the Operations Research Center at the University Miguel Hernandez. He has published more than 40 research papers in different international journals and books. His current research interests include game theory and operations research and its applications.

M. ALMINANA, L.F. ESCUDERO, M. LANDETE, J.F. MONGE,* A. RABASA and J. SANCHEZ-SORIANO

Centro de Investigacion Operativa, Universidad Miguel Hernandez, Elche (Alicante), Spain

E-mail: monge@umh.es

Received May 2006 and accepted May 2007

*Corresponding author

Table 1. Sets of general elements

Parameter      Description

T              set of time periods when water irrigation is performed
I              set of hydrants and bifurcation nodes in the geographical
                 area under consideration
[I.sub.0]      set of bifurcation nodes
[I.sup.[tau]]  subset of hydrants whose irrigation starting period has
                 already been fixed to time period [tau], [tau]
                 [member of] T, for [I.sup.[tau]] [subset]
                 [T.sup.[tau]] - [I.sub.0]
[GAMMA]        set of sector heads with [gamma](i) [member of] [GAMMA]
                 being the root node (sector head) of the subtree to
                 which hydrant i belongs
[R.sub.i]      set of upstream nodes to hydrant i, in its path back to
                 its sector head, including the same hydrant i, for i
                 [member of] I - [I.sub.0]
[S.sub.i]      set of successor nodes to node i, including the same
                 hydrant i, for i [member of] I. Notice that the nodes
                 in set [S.sub.i] can belong to different successor
                 paths (it is the case where the successor path has
                 bifurcation nodes)

Table 2. Technical and topographical parameters

Parameter        Definition

[f.sub.it]       friction factor for obtaining the pressure in the
                   immediate upstream pipe segment of hydrant i at time
                   period t, to be updated iteratively, for i
                   [member of] I - [I.sub.0], t [member of] T. (For
                   details on the computing of this coefficient see
                   Section 5.1)
[E.sub.i]        elevation of node i, for i [member of] I [union]
                   [GAMMA]
[L.sub.i]        length of the immediate upstream pipe segment of node
                   i, for i [member of] I [union] [GAMMA]
[D.sub.i]        diameter of the immediate upstream pipe segment of node
                   i, for i [member of] I [union] [GAMMA]
g                gravity acceleration coefficient
[H.sub.[gamma]]  pressure at sector head [gamma], for [gamma]
                   [member of] [GAMMA]
[H.sub.min]      minimum pressure required by any hydrant at any time
                   period
[V.sub.max]      maximum water flow velocity allowed along the immediate
                   upstream pipe segment of any node at any time period
K                hydromodule (l/s/ha), i.e., constant to obtain the
                   water flow volume to irrigate the land area through
                   any hydrant at any time period

Table 3. Irrigation scheduling parameter

Parameter    Definition

[^.N.sub.i]  duration of the irrigation by hydrant i based on the size
               of the area to be inrigated, for i [member of] I -
               [I.sub.0]

Table 4. Logistic parameters provided by the system operator

Parameter         Definition

[c.sub.it]        priority coefficient for selecting hydrant i to begin
                    a non-preempted irrigation at time period t, for i
                    [member of] I - [I.sub.0]
[F.sub.i]         effective land area (has) to be irrigated by hydrant
                    i, for i [member of] I - [I.sub.0]
[^.y.sub.i[tau]]  fixed value of zero or one for the variable
                    [y.sub.i[tau]] due to logistic considerations, for i
                    [member of] [I.sup.[tau]]

Table 5. Variables

Variable    Definition

[q.sub.it]  water discharge to flow through node i at time period t to
              satisfy its own needs, if any, and the water needs of its
              successor nodes, for t [member of] T, i [member of] I
              [union] [GAMMA]
[y.sub.it]  a zero-one variable, such that its value is one if the
              irrigation in hydrant i begins at time period t and,
              otherwise, it is zero, for t [member of] T, i [member of]
              I - [I.sub.0]. Notice that the irrigation is carried out
              in periods t,..., t + [^.N.sub.i] - 1 such that
              [y.sub.it] = 1

Table 6. Model dimensions

Parameter  Value

m           44390
[n.sub.c]   14155
n01          9848
nel        332231
dens (%)        0.031

Table 7. Real instances solution (optimality GAP = 0.05%)

                           [phi] = 0.2       [phi] = 0.5
Instance    [Z.sub.IP]  t (s)   niter  nn  t (s)  niter  nn

D0_10-100    186629     114.91  41     41  38.13  13     13
D0_10-1000  1829603     111.40  41     41  33.78  13     13
D1_10-100     99260     111.44  42     42  38.96  14     14
D1_10-1000   975775     110.74  42     42  39.85  14     14
D2_100       151456     108.80  42     42  38.99  14     14
D2_1000     1514562     107.60  42     42  38.97  14     14
D3_1           2302     101.95  42     42  36.88  14     14

               [phi] = 0.8
Instance    t (s)  niter  nn

D0_10-100   18.78  6      6
D0_10-1000  18.13  6      6
D1_10-100   14.46  6      6
D1_10-1000  17.73  6      6
D2_100      18.62  6      6
D2_1000     18.20  6      6
D3_1        17.03  6      6

Table 8. Realistic instances solution (optimality GAP = 0.05%)

                           [phi] = 0.2    [phi] = 0.5
Instance    [Z.sub.IP]  t (s)  niter  nn  t (s)  niter  nn

D0_10-100   1959038     66.49  40     40  24.34  13     13
D0_10-1000   201033     70.93  40     40  22.62  13     13
D1_10_100   1016298     68.13  41     41  24.63  14     14
D1_10-1000   105042     71.66  41     41  25.82  14     14
D2_100      1637000     71.20  41     41  25.29  14     14
D2_1000      163593     70.87  41     41  26.69  14     14
D3_1           2614     65.80  41     41  24.80  14     14

               [phi] = 0.8
Instance    t (s)  niter  nn

D0_10-100   12.45  6      6
D0_10-1000  11.88  6      6
D1_10_100   11.81  6      6
D1_10-1000  12.14  6      6
D2_100      12.28  6      6
D2_1000     11.86  6      6
D3_1        11.26  6      6

Table 9. Real instances solution (optimality GAP = 0.01%)

                           [phi] = 0.2             [phi] = 0.5
Instance    [Z.sub.IP]  t (s)    niter  nn      t (s)    niter  nn

D0_10-100    186629      114.86  41         41    37.23  13         13
D0_10-1000  1829603      111.42  41         41    37.49  13         13
D1_10-100     99287      129.04  41         41    44.64  14         14
D1_10-1000   975936      136.58  41       2141    64.29  14       2114
D2_100       151500     8800.19  41     757787  7940.67  14     717098
D2_1000     1515000     6058.58  41     582869  5372.43  14     542126
D3_1           2302      102.63  41         41    35.55  14         14

               [phi] = 0.8
Instance    t (s)    niter  nn

D0_10-100     18.61  6           6
D0_10-1000    18.49  6           6
D1_10-100     20.70  6           6
D1_10-1000    43.74  6        2106
D2_100      8049.34  6      705042
D2_1000     5036.85  6      530054
D3_1          16.58  6           6

Table 10. Realistic instances solution (optimality GAP = 0.01%)

                              [phi] = 0.2             [phi] = 0.5
Instance    [Z.sub.IP]  t (s)     niter  nn      t (s)     niter  nn

D0_10-100   1959038        71.37  40         40     23.62  13         13
D0_10-1000   201033        71.64  40         40     23.92  13         13
D1_10-100   1016403        73.01  41         41     26.08  14         34
D1_10-1000   105067        73.16  41         61     27.29  14         14
D2_100       163631      1246.47  41     136041   1185.61  14     136014
D2_1000     1637187     14402.18   1     750038  14402.04   1     751361
D3_1           2614        66.30  41         41     24.39  14         14

                 [phi] = 0.8
Instance    t (s)     niter  nn

D0_10-100      11.72  6           6
D0_10-1000     11.76  6           6
D1_10-100      12.06  6           6
D1_10-1000     12.73  6          26
D2_100       1158.98  6      136006
D2_1000     14402.09  1      754304
D3_1           10.75  6           6