A mixed binary integer linear program is formulated to determine the economic development of marginal groundwater sources at local demand sites in an arid region. These marginal sources are required to augment the supply from an overloaded regional source. The model accounts for variable costs of supply, fixed investment costs, capacity constraints at the regional and local levels, and water quality requirements at the local sites. A Lagrangian relaxation reduces the model to a series of simple local problems, the solution of which provides an optimal sequence for developing the marginal groundwater sources while reducing the demands on the regional source. A heuristic and an exact procedure are also proposed to solve the problem for arbitrary levels of supply from the regional source. The exact procedure uses characteristics of the optimal solution to reduce the model to a series of knapsack-type problems. The theory is applied to a small case study taken from the Negev Desert in southern Israel.

The pooling problem, which is fundamental to the petroleum industry, describes a situation in which products possessing different attribute qualities are mixed in a series of pools in such a way that the attribute qualities of the blended products of the end pools must satisfy given requirements. It is well known that the pooling problem can be modeled through bilinear and nonconvex quadratic programming. In this paper, we investigate how best to apply a new branch-and-cut quadratic programming algorithm to solve the pooling problem. To this effect, we consider two standard models: One is based primarily on flow variables, and the other relies on the proportion of flows entering pools. A hybrid of these two models is proposed for general pooling problems. Comparison of the computational properties of flow and proportion models is made on several problem instances taken from the literature. Moreover, a simple alternating procedure and a variable neighborhood search heuristic are developed to solve large instances and compared with the well-known method of successive linear programming. Solution of difficult test problems from the literature is substantially accelerated, and larger ones are solved exactly or approximately.