Solving Mixed-Binary Optimization Problems for Groundwater Management

Groundwater simulation/optimization techniques are often formulated using many candidate well locations. Each candidate well location represents the potential location of a well in the final optimal solution. Execution of the optimization solution algorithm yields active pumping at a subset of these candidate locations. It is often convenient to use binary variables to represent the presence or absence of each well. Use of binary variables makes it possible to include well construction costs in the optimization formulation and to include constraints such as the number of active wells and non-zero lower bounds on pumping rates. Inclusion of binary variables produces a mixed-binary optimization problem that can require significant computational effort to solve. In the present work, the algorithmic advantage of a modification to the branch and bound algorithm for mixed-binary linear programs is considered. The approach involves resetting the binary variables in subproblem based on the optimal solution to the subproblem. Application of the modification to a small test problem yields substantial reduction in the number of iterations required for the branch and bound algorithm. Introduction Simulation models for the prediction of the response of groundwater systems to changing stresses have been in widespread use for many years. A subset of models, specifically intended for design and management of groundwater systems, has evolved over the last several decades. These management models combine simulation models with optimization methods to produce a coupled model in which management objectives can be optimized while constraints on system behavior and management needs are enforced. Numerically based management models for groundwater systems have been proposed beginning with Maddock (1972), who focused on water supply problems by coupling with the groundwater flow equation. In subsequent years, models have been proposed for management of groundwater pollution (e.g. Gorelick, et al., 1984; Wagner and Gorelick, 1987; Ahlfeld, 1990; Culver and Shoemaker, 1992) requiring coupling with contaminant transport models. Most recently models have been proposed for such applications as management of stream/aquifer interaction (Barlow, et al., 2003), salt-water intrusion (Finney, et al., 1992) and bioremediation (Minsker and Shoemaker, 1996). General reviews of this literature can be found in Gorelick (1983), Yeh (1992), Wagner (1995) and Ahlfeld and Mulligan (2000). Solution of the management model can present a significant computational challenge. Generally, solving the optimization problem requires repeated solution of the simulation Copyright ASCE 2004 World Water Congress 2003 2 model under different stress assumptions. As a result of this challenge significant research has been undertaken to find efficient solution algorithms. These algorithms have included linear and nonlinear programming, dynamic programming (Jones, et al., 1987), simulated annealing (Dougherty and Marryott, 1991), tabu search (Zheng and Wang, 1999) and genetic algorithms (McKinney and Lin, 1994). One form of the management problem includes integer or binary variables. In this paper, the focus is on the efficient use of the branch and bound algorithm, coupled with linear programming, for the solution of mixed binary formulations of the linear groundwater flow management problem. Groundwater Flow Management Formulation The groundwater flow management problem of interest is that which seeks to minimize total pumping and well installation costs while maintaining heads below a specified level. This is one of many possible formulations that make use of binary variables, as described below. The present formulation takes the form, j j E j j j X tq minimize (1)