Maximizing Profit Using Benders Decomposition in Two-Stage Stochastic Water Distribution Network

Abstract

Profit is the primary intention that drives any industry. It is essential to incorporate the demand uncertainty in the water distribution industry to ensure maximum profit. This paper deals with the development of a two stage stochastic approach methodology. Initially a general two stage stochastic model is developed further a model based on Benders Decomposition is developed and the results are compared. The objective of the proposed method is to calculate the maximum profit that can be achieved by satisfying the varying demands of a site using water sources. The initial model is to formulate a two-stage stochastic deterministic equivalent model. Before the reality of the uncertain data is clear, a decision must be made in the first stage. The first stage's optimal solution is fixed, and only then can the values of the uncertain parameters be determined. The second method applies a simple benders' decomposition to the two-stage stochastic framework. Benders decomposition is a technique that helps in solving huge linear programming problems. This paper develops this method to simultaneously optimize the first set of variables (amount of water to be produced and transported) and second stage variables (Supply and Waste). The model is broken into a master problem and multiple subproblems. The solutions to these subproblems define the constraints of the master problem. The master problem is solved again and again until convergence. Both methodologies are illustrated with an example case study, and the results are compared. Benders Decomposition method took 50 iterations to converge and gave a profit value of $18,037.75. The deterministic equivalent model took 26 iterations to give the same value of profit.