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.