Application of LINGO in Water Resources Optimization Teaching Based on Integer Programming

Show more

1. Introduction

Water resources are the basic resources for the survival and development of human society. However, with the rapid development of economy and society, water resources are facing the serious shortage, especially for the northwest and north China. So, it is necessary to optimize the allocation of water resources to achieve efficient water resources use. Optimal allocation of water resources refers to the science of conducting limited and different forms of water resources assignment through engineering and non-engineering measures in a specific basin or region with effective, fair and sustainable principles (Gan et al., 2000) .

The optimal allocation of water resources requires reasonable and effective water resources allocation to maximize the comprehensive benefits. So, it is necessary to use operational research knowledge to make reasonable allocation calculations. In general water resources planning models, the decision variables are usually specified as non-negative real numbers. However, all or part of the decision variables are integers in some actual works, like the deployment of personnel and equipment, the selection of investment projects, the development order of projects, etc. Therefore, the planning problem in which decision variables (partially or completely) are integers is called integer programming (IP).

After long-term development, integer programming has caused complexity in the solution process due to its special integer constraints or 0 - 1 constraints. The branch and bound method, the cut plane method and the hidden enumeration method in traditional mathematical theory cannot meet the requirements of high efficiency, accuracy and fastness in the field of water resources optimization configuration. At the same time, these methods are more suitable for integer linear programming problems. However, it is more difficult to solve the integer programming problem with nonlinear constrained or objective functions. At present, a variety of new algorithms and optimization software are introduced into the field of water resources optimization configuration to solve complex mathematical models. Wu et al. (1992) used FORTRAN language to carry out the programming of hidden enumeration method, and solved the problem of reclaimed water reuse. Zhou (1988) used FORTRAN language to program the branch and bound method, and solved the problem of mine water supply and drainage; Zhong (2005) and Huang (2009) used MATLAB to design the genetic algorithm, and solved the problem of the field planning of the sewage treatment plant and the optimization of the rural water supply scale in the plain area; Li et al. (2007) and Gao (2007) used Visual Basic 6.0 software to carry out the programming of branch and bound method, and solved a series of problems in pump selection and the construction of rural drinking water safety project and water resources optimization in Binzhou City. Lovelady et al. (2009) used the Global Solver of the software LINGO to solve problem of integration of eco-industrial parks for managing water resources. Atilhan et al. (2012) used the software LINGO to solve problem of the optimization of macroscopic water desalination and distribution networks in Qatar. Singh et al. (2013) allocated available land and water resources in order to maximize net annual returns using the LINGO software.

At present, these methods are trying to use the computer to solve the problem quickly. Although the solving problems of water resources optimization configuration were solved in some cases, the following problems still exist: 1) programming is complicated, especially for integer constraint processing; 2) algorithm tends to be complicated, and now many methods are solved by introducing modern optimization algorithms, such as genetic algorithms, which brings uncertainty to the calculation results; 3) there are still some problems with the integer programming problem for solving nonlinear constraint or objective function.

This paper introduces LINGO software, a useful tool for solving planning problems. LINGO is a software for building and solving optimization models. It is convenient, fast and efficient in solving planning problem. At first, it can mainly solve linear programming problems and quadratic programming problems. With version update, currently LINGO can also solve the nonlinear programming problem (Schrage, 1999, 2006) . With its high-quality and efficient solving ability and strong pertinence, LINGO has become an important tool for solving optimization problems at present. At the same time, LINGO uses a common modeling language, which can be used to program optimization problems. There are certain built-in functions that allow users to use them during modeling. Because their language structure is relatively simple and intuitive, it can be used less command statement to describe complex mathematical models. It also provides an interface with other data files, which can easily solve the model, implement input and output of data, and analyze related problems.

Usually, the use of LINGO software to solve the optimization problem mainly includes two major steps: first, the corresponding mathematical model was established based on the actual problem analysis; second, the LINGO program codes were written based on the established mathematical model, and the result was solved by computer using its built-in algorithm.

Based on the above problems, firstly, this paper introduces LINGO software, which was usually used in the field of solving planning problems, into the water resources optimization integer programming teaching. Next, this paper studies the feasibility of its application by examples, and clarifies the scalability of its application. Finally, we think the LINGO software could improve students’ practical ability to solve complex engineering problems.

2. The Integer Programming Model

2.1. Integer Linear Programming Model

The integer linear programming model is mainly composed of an objective function, several restrictions and integer constraints of decision variables. The model structure is shown in Equation (1).

$\begin{array}{l}\text{opt}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}Z={c}_{1}{x}_{1}+{c}_{2}{x}_{2}+\cdots +{c}_{n}{x}_{n}\\ \text{s}\text{.t}\text{.}\{\begin{array}{l}{a}_{11}{x}_{1}+{a}_{12}{x}_{2}+\cdots +{a}_{1n}{x}_{n}\le \left(=,\ge \right){b}_{1}\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\vdots \\ {a}_{m1}{x}_{1}+{a}_{m2}{x}_{2}+\cdots +{a}_{mn}{x}_{n}\le \left(=,\ge \right){b}_{m}\\ {x}_{1},x{}_{2},\cdots ,{x}_{n}\ge 0\\ {x}_{1},x{}_{2},\cdots ,{x}_{n}\text{\hspace{0.17em}}\text{aretheinteger}\end{array}\end{array}$ (1)

The mathematical model of integer programming established by Equation (1) generally has the following characteristics: 1) it has all the features of the linear programming model; 2) if the decision variables in the model are not all integers, it is called Mixed Integer (MIP); 3) if the decision variables in the model are integers, it is called pure IP planning (Pure IP, PIP) or all integer programming (All IP, AIP); 4) if the value of the decision variable in the model is {0, 1}, it is called 0-1 planning and assignment problem is a more special 0 - 1 planning.

2.2. Other Linear Programming Model

Some programming objective functions or constraints of some integer programming models are not all linear functions or all are not linear functions, but some or all of the decision variables are integers. This kind of planning problem is also called integer programming, as shown in Equation (2).

$\begin{array}{l}\begin{array}{cc}\mathrm{min}& f\left(x\right)\end{array}\\ \text{s}\text{.t}\text{.}\{\begin{array}{l}\begin{array}{cc}{h}_{j}(x)=0& j=1,2,\cdots ,m\end{array}\\ \begin{array}{cc}{g}_{k}\left(x\right)\ge 0& k=1,2,\cdots ,p\end{array}\\ {x}_{1},x{}_{2},\cdots ,{x}_{n}\ge 0\\ {x}_{1},x{}_{2},\cdots ,{x}_{n}\text{\hspace{0.17em}}\text{aretheinteger}\end{array}\end{array}$ (2)

2.3. Built-in Function in LINGO

LINGO software provides a number of simple built-in functions to efficiently and conveniently solve the integer constraints and 0 - 1 constraints in the above integer programming. For example, @bin(x) function, where x is 0 or 1; @gin(x) function, which limits x to an integer; @bnd(L, x, U) function, limits L ≤ x ≤ U; @free(x) function, the default setting of the lower bound of the variable is 0, that is, x can take any real number.

3. Example

3.1. Example Background

This example is taken from the relevant data in Fang et al. (2003) . Somewhere in northern Xuhuai, China, it is located in the semi-humid warm temperate climate zone. The average annual precipitation is about 800 mm and the interannual variation of precipitation is large. The surface runoff in the flood season accounts for more than 80% runoff of the whole year. There is a reservoir with a capacity of 4.72 × 10^{8} m^{3} as the main water supply project, and a pumping station system with a pumping capacity of 8.00 × 10^{8} m^{3}・a^{−1}. With the development of the local economy and economy, the demand for water is increasing year by year, and the contradiction between supply and demand is prominent. To solve this problem, the local government plans to build a batch of water supply projects during the 25-year construction planning period. It mainly includes: Project 1 raises the normal water storage level of the reservoir, improves the design standard of the reservoir, and increases its water demand capacity; Project 2 repairs and expands the pumping station system to enhance the water diversion capacity; Project 3 opens a water diversion line for cross-border water diversion; Project 4 builts groundwater exploitation facilities and rationally exploit and utilize groundwater resources. The relevant data is shown in Table 1 (where construction costs were estimated from the 1998 price index). Construction requirements: The completion of the first two working hours can meet the water supply demand for more than ten years, while increasing the water supply is not less than 5.00 × 10^{8} m^{3}. In the calculation, it is assumed that there is no other limit on the water supply capacity and construction funds during the construction process, and the cash discount rate is 10%. According to this, the appropriate engineering construction sequence is selected to minimize the cost.

3.2. Model Establishment

3.2.1. Objective Function

The construction period of the project is 25 years, and 4 projects are constructed within this period. It is assumed that the construction period is divided into four construction periods, and only one project is allowed to be completed during each construction period. Therefore, the requested variable is x_{ij}, indicating the state of the i-th project in the j-th construction period.

$\begin{array}{l}\{\begin{array}{l}{x}_{ij}=1,\text{indicates that the}i\text{-th project was built during the}j\text{-th period}\uff0c\\ {x}_{ij}=0,\text{indicates that the}i\text{-th project does not build during the}j\text{-th period}\uff0c\end{array}\\ i,j=1,2,3,4\end{array}$ (3)

where $\underset{i=1}{\overset{4}{\sum}}{x}_{ij}}=1,j=1,2,3,4$ .

Create an integer programming objective function with the least cost goal:

$\mathrm{min}{P}_{t}={\displaystyle {\sum}_{i=1}^{4}{C}_{i}\cdot {x}_{i1}+\left[{\displaystyle {\sum}_{j=2}^{4}\left({\displaystyle {\sum}_{i=1}^{4}{C}_{i}\cdot {x}_{ij}}\right)}{\left(1+r\right)}^{-T}\right]}$ (4)

where P_{t} is the total amount of cash posted; C_{i} is the construction fund for the i-th project; r is the cash discount rate, which is 10%.

$\{\begin{array}{l}{T}_{1}={\displaystyle {\sum}_{i=1}^{4}{t}_{i}\cdot {x}_{i1}}\\ {T}_{2}={\displaystyle {\sum}_{i=1}^{4}{t}_{i}\cdot {x}_{i2}}\\ {T}_{3}={\displaystyle {\sum}_{i=1}^{4}{t}_{i}\cdot {x}_{i3}}\end{array}$ (5)

where t_{i} is the time required for the engineering capacity of the i-th project to meet the water supply needs.

Table 1. Relevant data of a project planning.

3.2.2. Restrictions

1) Constraints of engineering capacity increases water supply

The engineering capability of the first two stages is required to be at least 5.00 × 10^{8} m^{3}, thus,

$\underset{i=1}{\overset{4}{\sum}}{M}_{i}}\cdot \left({x}_{i1}+{x}_{i2}\right)\ge 5$ (6)

where M_{i} is the engineering capacity of i-th project.

2) Constraints of water supply demand time

Require the first two phases to complete the project to meet the water demand requirement of not less than 10 years, thus,

$\underset{i=1}{\overset{4}{\sum}}{t}_{i}}\cdot \left({x}_{i1}+{x}_{i2}\right)\ge 10$ (7)

where t_{i} is the water supply demand time of i-th project.

3) Constraints of project construction

Because only one project can be built in each construction period, at the same time, each project can only be built once, thus,

$\{\begin{array}{l}{\displaystyle {\sum}_{i=1}^{4}{x}_{ij}=1,j=1,2,3,4.}\\ {\displaystyle {\sum}_{j=1}^{4}{x}_{ij}=1,j=1,2,3,4.}\\ {x}_{ij}\text{isequalto1or0;}i=1,2,3,4;j=1,2,3,4.\\ {\displaystyle {\sum}_{j=1}^{4}{\displaystyle {\sum}_{j=1}^{4}{x}_{ij}=4}}\end{array}$ (8)

According to formulas (4) to (8), the whole model for constructing the problem is shown in Equation (9).

$\begin{array}{l}\mathrm{min}{P}_{t}={\displaystyle {\sum}_{i=1}^{4}{C}_{i}\cdot {x}_{i1}+\left[{\displaystyle {\sum}_{j=2}^{4}\left({\displaystyle {\sum}_{i=1}^{4}{C}_{i}\cdot {x}_{ij}}\right){\left(1+r\right)}^{-T}}\right]}\\ \{\begin{array}{l}{\displaystyle \underset{i=1}{\overset{4}{\sum}}{M}_{i}}\cdot \left({x}_{i1}+{x}_{i2}\right)\ge 5\\ {\displaystyle \underset{i=1}{\overset{4}{\sum}}{t}_{i}}\cdot \left({x}_{i1}+{x}_{i2}\right)\ge 10\\ {\displaystyle {\sum}_{i=1}^{4}{x}_{ij}}=1,j=1,2,3,4.\\ {\displaystyle {\sum}_{j=1}^{4}{x}_{ij}}=1,j=1,2,3,4.\\ {x}_{ij}\text{isequalto1or0;}i=1,2,3,4;j=1,2,3,4.\\ {\displaystyle {\sum}_{j=1}^{4}{\displaystyle {\sum}_{j=1}^{4}{x}_{ij}=4}}\end{array}\end{array}$ (9)

3.3. Models Solving

The built-in integer programming model is programmed in the LINGO software. The LINGO code is shown in Table 2. By calculating the above LINGO program, the following calculation results are obtained (see Table 2).

3.4. Results

From the program result, x_{21} = 1, x_{42} = 1, x_{13} = 1, x_{34} = 1 and the rest decision variables are 0. Therefore, the implementation order of the plan is Project 2, Project 4, Project 1, and Project 3. The minimum discounted construction cost is 1.69 × 1.0^{4} million yuan. According to the order of calculation results, the water supply growth demand can be satisfied for 25 years.

Table 2. The LINGO code and the calculation results.

In Fang & Jiang (2003) , the genetic algorithm was used to solve the model. The population size was 40 and the update algebra was N = 160. According to experience, the crossover probability was 0.8 and the mutation probability was 0.02. The whole calculation process was carried out by using the FORTRAN language programming program. The results are consistent with the results of this paper, that is, the optimal construction order is Project 2, Project 4, Project 1, and Project 3, and the minimum discount construction cost is 1.69 × 10^{4} million.

Compared with genetic algorithm in study Fang et al., the result of LINGO software is consistent and solving speed of LINGO is more quickly. This shows that LINGO software has obvious advantages in solving planning problems, and has a wide application space in solving water resources optimization problems.

4. Conclusion

Compared with other software to solve integer programming problems, due to some efficient built-in functions, especially @bin and @gin functions, you can directly constrain the decision variables to 0 - 1 or integers, which makes programming difficulty of LINGO software reduce and effectively improve the accuracy and reliability of the calculation. At the same time, LINGO software can also solve nonlinear programming problems, which makes it more widely used, especially for integer programming problems.

This paper uses LINGO to solve the example, which shows that LINGO can greatly reduce the complexity of the problem-solving process and avoid the difficulty of programming caused by introducing complex algorithms. At the same time, the LINGO programming language is more concise than other software. For simple cases, the program code is no different from the mathematical model. For relatively complex cases, the “set” can be used to program the model in a concise manner. LINGO software can play a larger and more effective role in the integer programming problem of water resources optimization configuration. Although the data volume of this example is small and the planning model is relatively simple, it has highlighted the advantages of LINGO software. For complex water resources optimization configuration planning model, LINGO’s advantages will be more obvious. Students could use the advanced software to solve the complex water resources optimization integer programming model based on the traditional integer programming solution. It is beneficial to cultivate college students’ innovative thinking and innovative consciousness.

Foundation Item

Beijing co-construction project special funding and Famous Teachers Cultivation Planning for Teaching of North China Electric Power University (the Fourth Period).

References

[1] Atilhan, S., Mahfouz, A. B., Batchelor, B., Linke, P., Abdel-Wahab, A., Nápoles-Rivera, F. et al. (2012). A Systems-Integration Approach to the Optimization of Macroscopic Water Desalination and Distribution Networks: A General Framework Applied to Qatar’s Water Resources. Clean Technologies and Environmental Policy, 14, 161-171.

https://doi.org/10.1007/s10098-011-0387-8

[2] Fang, H. Y., & Jiang, Z. Q. (2003). Integer Programming Model for Regional Water Supply Capacity Expansion Analysis. Journal of Yangzhou University (Natural Science Edition), 6, 66-70.

[3] Gan, W., Li, L. Y., & Yin, M. W. (2000). Analysis of Rational Allocation of Water Resources. China Water Resources, 4, 20-23.

[4] Gao, F. H. (2007). Research on Rural Drinking Water Safety Engineering Construction and Water Source Optimization Allocation in Binzhou City. Master’s Thesis, Jinan: Shandong University.

[5] Huang, J. S. (2009). Research on Rural Water Supply Project Construction and System Optimization in Plain Area. Master’s Thesis, Hefei: Hefei University of Technology.

[6] Li, A. Y., Li, B., & Wu, J. H. (2007). Application of Branch and Delimitation of Integer Programming in Pump Selection. Water Resources Science and Technology, 13, 165-167.

[7] Lovelady, E. M., & El-Halwagi, M. M. (2009). Design and Integration of Eco-Industrial Parks for Managing Water Resources. Environmental Progress & Sustainable Energy: An Official Publication of the American Institute of Chemical Engineers, 28, 265-272.

https://doi.org/10.1002/ep.10326

[8] Schrage, L. (2006). LINGO User’s Guide. Chicago, IL: LINDO System Inc.

[9] Schrage, L. (1999). Optimization Modeling with LINGO (5th Edition). Chicago, IL: LINDO Systems Inc.

[10] Singh, A., & Panda, S. N. (2013). Optimization and Simulation Modelling for Managing the Problems of Water Resources. Water Resources Management, 27, 3421-3431.

https://doi.org/10.1007/s11269-013-0355-7

[11] Wu, L. M., Wu, Y. S., & Su, W. H. (1992). Integer Programming Model for Urban Wastewater Reuse System Research. Environmental Science, 13, 36-41, 95.

[12] Zhong, Y. Q. (2005). Wastewater Plant Group Planning Based on Genetic Algorithm. Master’s Thesis, Chengdu: Sichuan University.

[13] Zhou, X. J. (1988). Application of Linear Programming and Integer Programming Method in Water Supply and Drainage Design of a Mine. Chemical Industry and Engineering, 8, 166-171.