PRES22_0231.docx DOI: 10.3303/CET2294133 Paper Received: 20 April 2022; Revised: 05 June 2022; Accepted: 10 June 2022 Please cite this article as: Bharadwaj R., Chaturvedi N.D., 2022, Maximizing Profit Using Benders Decomposition in Two-Stage Stochastic Water Distribution Network, Chemical Engineering Transactions, 94, 799-804 DOI:10.3303/CET2294133 CHEMICAL ENGINEERING TRANSACTIONS VOL. 94, 2022 A publication of The Italian Association of Chemical Engineering Online at www.cetjournal.it Guest Editors: Petar S. Varbanov, Yee Van Fan, Jiří J. Klemeš, Sandro Nižetić Copyright © 2022, AIDIC Servizi S.r.l. ISBN 978-88-95608-93-8; ISSN 2283-9216 Maximizing Profit Using Benders Decomposition in Two-Stage Stochastic Water Distribution Network Raghav Bharadwaj, Nitin Dutt Chaturvedi* Process Systems Engineering Lab, Department of Chemical and Biochemical Engineering, Indian Institute of Technology Patna, Bihta, 801106, Patna, Bihar India nitind@iitp.ac.in 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. 1. Introduction Water is one of the major resources in process industries (Chaturvedi and Manan, 2021). Water resource consumption has been identified as one of the important global environmental issues of the 21st Century (Kumawat and Chaturvedi, 2020). Al-Redhwan et al. (2005) developed an approach based on Sensitivity analysis and Stochastic Programming to develop flexible and resilient process water networks. Stochastic Programming is a framework for describing uncertainty in optimization issues. A stochastic program is an optimization problem in which some or all of the problem parameters are unknown but follow well-defined Probability distributions. This paradigm differs from Deterministic optimization, which assumes that all problem parameters are known precisely. Stochastic programming aims to develop a solution that optimizes some criteria set by the decision-maker while also accounting for the issue parameters' uncertainty. Many real-world decisions contain uncertainty that's why stochastic programming has utility in various fields, including banking, transportation, and energy optimization. Among stochastic programming models, the two-stage stochastic programming model is applied in water resource allocation due to its unique advantages. The central notion behind two-stage stochastic programming is that (optimal) choice should be made using data that is accessible at the time the decision is made, rather than relying on future observations. The first stage shows the need to make quick judgments. The second stage reflects judgments that should be taken in the future, taking into account a range of probable scenarios, each of which provides a plausible manifestation of the unknown facts. The purpose is to determine the least expensive option, including the estimated costs of the first and second stages. The uncertainty about the problem parameters is modelled by a limited number of subproblems (scenarios), weighted by their occurrence 799 probability, and containing a local representation of the problem uncertainties. By obtaining the optimal solutions for each scenario, one could expect to find similarities and trends among the scenarios to develop a solution that holds a good trade-off under all scenarios. Damsleth et al. (1992) proposed a two-stage stochastic model applied to a North Sea reservoir. Ling et al. (2020) adopted a novel two-stage fuzzy stochastic programming approach for the water resource allocation problem capable of addressing uncertainties with both possibility and probability distribution. Fu et al. (2018) developed an agricultural multi- water source allocation model, consisting of stochastic robust programming and two-stage random programming and introducing interval numbers and random variables to represent the uncertainties, which was proposed for the optimization of irrigation water allocation in Jiamusi City of Heilongjiang Province, China. Ling et al. (2017) established an inexact two-stage stochastic programming model was developed for supporting regional water resource allocation management under uncertainties. However, these problems give up mathematical complex formulation. In this context, this paper uses decomposition of problem. The decomposition refers to splitting a mathematical programming problem (also known as a constrained optimization problem, of which linear programming is an exciting subset) into smaller, more manageable problems that can then be re-integrated to obtain an overall solution. Benders (1962) originally applied the idea of decomposition to mixed-integer programming problems. These problems are constrained optimization problems in which some variables can take real values, and others may only take integer values. Benders used decomposition to split the problem into a pure integer programming problem and a pure linear programming problem that could be solved iteratively, in turn, to solve the overall problem. 2. Problem definition This paper deals with the development of a methodology for targeting profit for the water distribution network. The schematic is shown in Figure 1. The problem definition is as follows: • There is a set S of sources where each source has a fixed maximum purification capacity. • There is a set D of sites where each site has some uncertain demand which has to be fulfilled. • There is a set A of individual scenarios that signify the nature of demand. • The main aim is to maximize the profit generated by the distribution of water to the different sites by optimizing the transport, purification, and waste costs. • Before the actual demand is observed, we suppose that pure water is transferred from the source to the site. Actual demand is known after the water arrives at each place. • If demand isn't met, supply is depleted. The remaining water must be disposed of if the carried water exceeds the ultimate demand. The cost of wastewater removal is known. Figure 1: Schematic of the problem definition 3. Models Different models of two-stage stochastic optimization and benders decomposition are explained in this section. 3.1. Two-Stage Stochastic Optimization-Core Model The two-stage stochastic optimization core model is extensively analyzed and is given by Eq(1) as objective)) and subject to constraints in Eqs(2-4). 𝑀𝑀𝑀𝑀𝑛𝑛𝑥𝑥 𝑧𝑧 = 𝑐𝑐𝑇𝑇𝑥𝑥 + 𝐸𝐸[𝑄𝑄(𝑥𝑥, ω)] (1) 800 𝑠𝑠. 𝑡𝑡. 𝐴𝐴𝑥𝑥 = 𝑏𝑏 , 𝑥𝑥 ≥ 0 (2) 𝑤𝑤ℎ𝑒𝑒𝑒𝑒𝑒𝑒, 𝑄𝑄(𝑥𝑥, ω) = 𝑀𝑀𝑀𝑀𝑛𝑛𝑦𝑦 𝑞𝑞ω𝑇𝑇𝑦𝑦(ω) (3) 𝑠𝑠. 𝑡𝑡. , 𝑇𝑇𝜔𝜔𝑥𝑥 + 𝑊𝑊𝜔𝜔𝑦𝑦(𝜔𝜔) = ℎ𝜔𝜔 (4) Let x and y be two variables, and ω be the set of all possible realizations of the unknown data is given by Ω, Ω={ω1, ,ωs} ⊆ ℝr where r is the number of random variables representing the uncertain parameters. Eq(2) define the problem in the first stage, whereas Eq(3) and Eq(4) define the problem in the second stage. In the first stage, x is the decision variable, 𝑐𝑐𝑇𝑇 is the objective function's cost coefficients, and 𝐸𝐸[𝑄𝑄(𝑥𝑥, ω)] is the expected value of the second stage problem's optimal solution. The coefficients are denoted by A, and the right-hand side of the first stage restrictions is denoted by b. The decision variable is y, the transition matrix is T, the recourse matrix is W (cost of recourse), and the right-hand side of the second stage constraints is h. It is worth noting that the second stage's parameters and decision variables are all reliant on the stochastic data's specific realization 𝝎𝝎. The objective z is a random variable as it is a function of 𝝎𝝎. Stochastic solvers automatically optimize the expected value of the objective variable z since a random variable cannot be maximized. 3.2. Two-Stage Stochastic Optimization-Deterministic Equivalent Building and solving the deterministic equivalent is one of the most prevalent ways of solving a two-stage stochastic LP. Assume the uncertain parameters have a (finite) discrete distribution and that each scenario s occurs with probability 𝑃𝑃(𝜔𝜔𝑠𝑠) = 𝑝𝑝𝑠𝑠for all s=1,…., S and ∑ 𝑝𝑝𝑠𝑠 = 1𝑠𝑠 . 𝐸𝐸[𝑄𝑄(𝑥𝑥, 𝜔𝜔)] = ∑ 𝑝𝑝𝑠𝑠𝑞𝑞𝑇𝑇𝑦𝑦𝑠𝑠𝑠𝑠 , with ys denoting the best second-stage option for scenario s. After that, the deterministic equivalent is given by Eq(5) subject to the set of constraints Eq(6). 𝑐𝑐𝑇𝑇𝑥𝑥 + 𝑝𝑝1𝑞𝑞𝑇𝑇𝑦𝑦1 + 𝑝𝑝2𝑞𝑞𝑇𝑇𝑦𝑦2 + ⋯ + 𝑝𝑝𝑠𝑠𝑞𝑞𝑇𝑇𝑦𝑦𝑠𝑠 (5) 𝑠𝑠. 𝑡𝑡. 𝐴𝐴𝑥𝑥 = 𝑏𝑏 (6) 𝑇𝑇𝑠𝑠𝑥𝑥 + 𝑊𝑊𝑠𝑠𝑦𝑦𝑠𝑠 = ℎ𝑠𝑠 (7) 𝑤𝑤ℎ𝑒𝑒𝑒𝑒𝑒𝑒, 𝑥𝑥 ∈ ℝn , 𝑦𝑦1 ∈ ℝn , 𝑦𝑦2 ∈ ℝm , 𝑦𝑦𝑠𝑠 ∈ ℝm, 𝑠𝑠 ∈ 𝑆𝑆 (8) 3.3 Benders Decomposition Original optimization problem structure; min 𝑐𝑐′ 𝑦𝑦 + 𝑄𝑄(𝑦𝑦), 𝑠𝑠. 𝑡𝑡. 𝐴𝐴𝑦𝑦 ≤ 𝑏𝑏, 𝑦𝑦 ≥ 0 (9) The function 𝑄𝑄(𝑦𝑦) in Eq(9) is difficult and expensive to assess because it depends on finding an optimal solution to all sub-problems. Remember that we are seeking a rational approach to applying restrictions to some master problem, a less constrained version of the complete problem, to come up with reasonable estimates of y without solving the whole thing. The initial master problem in Benders decomposition is the first stage problem. The restrictions we apply to it correspond to the feasibility and optimality of the (second-stage) sub-problems. It is anticipated that these estimates will converge to the best solution by introducing constraints judiciously while requiring us to tackle a minor problem. Next, from the above objective function, the complicated Q(y) term with a variable θ. Bounds are placed by utilizing the information extracted from the subproblems known as optimality cuts. The assumption is that, while these bounds will eventually recreate the function Q(y), they will not do so initially, making the problem significantly more straightforward. We hope to identify the best solution before the original Q(y) function is reproduced. Consider the sub-problem for the case when the random processes u takes the realization uω. Call this sub-problem ω. Eq(10) and Eq(11) state the primal sub problem and Eq(12) and Eq(13) state the dual subproblem. Dual of a minimization problem would be a maximization problem. Primal Sub-problem: 𝑄𝑄(𝑦𝑦, 𝑢𝑢𝜔𝜔) = 𝑚𝑚𝑀𝑀𝑛𝑛𝑣𝑣 𝑞𝑞(𝑢𝑢𝜔𝜔)′𝑣𝑣 (10) s. t. 𝑊𝑊(𝑢𝑢𝜔𝜔)𝑣𝑣 ≤ ℎ(𝑢𝑢𝜔𝜔)– 𝑇𝑇(𝑢𝑢𝜔𝜔)𝑦𝑦 , 𝑣𝑣 ≥ 0 (11) Dual Subproblem 𝑄𝑄(𝑦𝑦, 𝑢𝑢𝜔𝜔) = 𝑚𝑚𝑚𝑚𝑥𝑥 𝜋𝜋’(ℎ(𝑢𝑢𝜔𝜔) – 𝑇𝑇(𝑢𝑢𝜔𝜔)𝑦𝑦) (12) s. t. 𝜋𝜋’ 𝑤𝑤(𝑢𝑢𝜔𝜔) ≤ 𝑞𝑞(𝑢𝑢𝜔𝜔)’, 𝜋𝜋 ≥ 0 (13) 801 𝑦𝑦𝑖𝑖 is the value of the first stage decision that comes from the ith iteration of the master problem. Let πω𝑖𝑖 be the optimal values of the variables in the dual subproblem (Eq(14)). 𝑄𝑄�𝑦𝑦𝑖𝑖, 𝑢𝑢ω� = �πω𝑖𝑖 � ′ (ℎ − 𝑇𝑇𝑦𝑦𝑖𝑖 ) (14) By duality theory, it is known that the right-hand side of Eq(15) corresponds to the linear space that forms part of 𝑄𝑄�𝑦𝑦𝑖𝑖, 𝑢𝑢ω� at 𝑦𝑦𝑖𝑖. A constraint in the primal sub-problem (Eq(10)) produces the linear piece of 𝑄𝑄�𝑦𝑦𝑖𝑖, 𝑢𝑢ω�.It is necessary to remember that when we form the dual, each constraint in the primal problem leads to a dual variable. Each primal variable leads to a dual constraint, and the constraints from the primal problem are multiplied by one of the dual variables to generate the dual problem's objective. What we are doing with Eq(15) is using constraints from the subproblem to produce a lower bound on its objective 𝑄𝑄�𝑦𝑦𝑖𝑖, 𝑢𝑢ω�.Eq(16) represents the bound which is placed on θ. 𝑄𝑄(𝑦𝑦2, 𝑢𝑢ω) ≥ (𝜋𝜋𝜔𝜔𝑖𝑖 )′ (ℎ − 𝑇𝑇𝑦𝑦2) (15) 𝛳𝛳 , 𝑄𝑄(𝑦𝑦) ≥ ∑ 𝑝𝑝𝜔𝜔�𝜋𝜋𝜔𝜔𝑖𝑖 � ′ (ℎ − 𝑇𝑇𝑦𝑦)ω (16) Figure 2: Schematic representation of the bender’s decomposition method 4. Mathematical formulation 𝑃𝑃𝑒𝑒𝑃𝑃𝑃𝑃𝑀𝑀𝑡𝑡 = ∑ 𝑝𝑝𝑗𝑗𝑝𝑝𝑒𝑒𝑃𝑃𝑏𝑏𝜔𝜔𝑆𝑆𝑢𝑢𝑝𝑝𝑝𝑝𝑆𝑆𝑦𝑦𝑗𝑗 − ∑ 𝑐𝑐𝑖𝑖,𝑗𝑗 𝑇𝑇𝑒𝑒𝑚𝑚𝑛𝑛𝑠𝑠𝑝𝑝𝑃𝑃𝑒𝑒𝑡𝑡𝑆𝑆𝑀𝑀𝑡𝑡𝑒𝑒𝑖𝑖,𝑗𝑗 − ∑ 𝑐𝑐𝑖𝑖𝑃𝑃𝑢𝑢𝑒𝑒𝑀𝑀𝑃𝑃𝑀𝑀𝑒𝑒𝑃𝑃𝑊𝑊𝑚𝑚𝑡𝑡𝑒𝑒𝑒𝑒𝑖𝑖 − ∑ 𝑐𝑐𝑗𝑗𝑝𝑝𝑒𝑒𝑃𝑃𝑏𝑏𝜔𝜔𝑊𝑊𝑚𝑚𝑠𝑠𝑡𝑡𝑒𝑒𝑗𝑗𝑗𝑗,𝑤𝑤𝑖𝑖 𝑖𝑖,𝑗𝑗𝑗𝑗,𝜔𝜔 , (17) 𝑃𝑃𝑢𝑢𝑒𝑒𝑀𝑀𝑃𝑃𝑀𝑀𝑒𝑒𝑃𝑃𝑊𝑊𝑚𝑚𝑡𝑡𝑒𝑒𝑒𝑒𝑖𝑖 = ∑ 𝑇𝑇𝑒𝑒𝑚𝑚𝑛𝑛𝑠𝑠𝑝𝑝𝑃𝑃𝑒𝑒𝑡𝑡𝑆𝑆𝑀𝑀𝑡𝑡𝑒𝑒𝑖𝑖,𝑗𝑗𝑗𝑗 (18) 𝑃𝑃𝑢𝑢𝑒𝑒𝑀𝑀𝑃𝑃𝑀𝑀𝑒𝑒𝑃𝑃𝑊𝑊𝑚𝑚𝑡𝑡𝑒𝑒𝑒𝑒𝑖𝑖 ≤ 𝐶𝐶𝑚𝑚𝑝𝑝𝑚𝑚𝑐𝑐𝑀𝑀𝑡𝑡𝑦𝑦𝑖𝑖 (19) 𝑅𝑅𝑒𝑒𝑐𝑐𝑒𝑒𝑀𝑀𝑣𝑣𝑒𝑒𝑃𝑃𝑗𝑗 = 𝑆𝑆𝑢𝑢𝑝𝑝𝑝𝑝𝑆𝑆𝑦𝑦𝑗𝑗,𝜔𝜔 + 𝑊𝑊𝑚𝑚𝑠𝑠𝑡𝑡𝑒𝑒𝑗𝑗,𝜔𝜔 (20) 𝑆𝑆𝑢𝑢𝑝𝑝𝑝𝑝𝑆𝑆𝑦𝑦𝑗𝑗,𝜔𝜔 ≤ 𝑃𝑃𝑒𝑒𝑚𝑚𝑚𝑚𝑛𝑛𝑃𝑃𝑗𝑗, 𝑆𝑆𝑢𝑢𝑝𝑝𝑝𝑝𝑆𝑆𝑦𝑦𝑗𝑗,𝜔𝜔, 𝑇𝑇𝑒𝑒𝑚𝑚𝑛𝑛𝑠𝑠𝑝𝑝𝑃𝑃𝑒𝑒𝑡𝑡𝑆𝑆𝑀𝑀𝑡𝑡𝑒𝑒𝑖𝑖,𝑗𝑗, 𝑃𝑃𝑢𝑢𝑒𝑒𝑀𝑀𝑃𝑃𝑀𝑀𝑒𝑒𝑃𝑃𝑊𝑊𝑚𝑚𝑡𝑡𝑒𝑒𝑒𝑒𝑖𝑖 , 𝑊𝑊𝑚𝑚𝑠𝑠𝑡𝑡𝑒𝑒𝑗𝑗,𝜔𝜔 ≥0 (21) The proposed methodologies are illustrated with an example consisting of multiple sources and sites which require water. The main objective of both methods was to maximize profit given by Eq(17). Eq(18) represents the first stage equation. Eq(19) is the purification capacity constraint at a particular source. Eq(20) is the second stage equation. Eq(21) is the demand constraint and also implies the non-negativity of the variables. 𝑆𝑆𝑢𝑢𝑝𝑝𝑝𝑝𝑆𝑆𝑦𝑦𝑗𝑗 is the supplied water that is used at a site j, 𝑇𝑇𝑒𝑒𝑚𝑚𝑛𝑛𝑠𝑠𝑝𝑝𝑃𝑃𝑒𝑒𝑡𝑡𝑆𝑆𝑀𝑀𝑡𝑡𝑒𝑒𝑖𝑖,𝑗𝑗 is the amount of water that is transported from a source i to site j, 𝑃𝑃𝑢𝑢𝑒𝑒𝑀𝑀𝑃𝑃𝑀𝑀𝑒𝑒𝑃𝑃𝑊𝑊𝑚𝑚𝑡𝑡𝑒𝑒𝑒𝑒𝑖𝑖 is the production of purified water at source i, 𝑊𝑊𝑚𝑚𝑠𝑠𝑡𝑡𝑒𝑒𝑗𝑗 is the wastewater which was extra(not used) at a site j, 𝑝𝑝𝑗𝑗 is the supply price, 𝑐𝑐𝑖𝑖,𝑗𝑗is the unit transportation cost from source i to site j, 𝑐𝑐𝑖𝑖 is the unit purification cost, 𝑐𝑐𝑗𝑗 is the cost of removal of wastewater, 𝑐𝑐𝑚𝑚𝑝𝑝𝑚𝑚𝑐𝑐𝑀𝑀𝑡𝑡𝑦𝑦𝑖𝑖 is the maximum amount of water that can be purified at factory i, 𝑃𝑃𝑒𝑒𝑚𝑚𝑚𝑚𝑛𝑛𝑃𝑃𝑗𝑗 is the demand at site j. The Primal Sub-problem is formulated as: 𝑂𝑂𝑏𝑏𝑂𝑂𝑒𝑒𝑐𝑐𝑡𝑡𝑀𝑀𝑣𝑣𝑒𝑒 = 𝑀𝑀𝑚𝑚𝑥𝑥 { ∑ 𝑝𝑝𝑗𝑗𝑆𝑆𝑢𝑢𝑝𝑝𝑝𝑝𝑆𝑆𝑦𝑦𝑗𝑗 − ∑ 𝑐𝑐𝑗𝑗𝑊𝑊𝑚𝑚𝑠𝑠𝑡𝑡𝑒𝑒𝑗𝑗} 𝑂𝑂𝑅𝑅 𝑀𝑀𝑀𝑀𝑛𝑛 { ∑ 𝑐𝑐𝑗𝑗𝑊𝑊𝑚𝑚𝑠𝑠𝑡𝑡𝑒𝑒𝑗𝑗 − ∑ 𝑝𝑝𝑗𝑗𝑆𝑆𝑢𝑢𝑝𝑝𝑝𝑝𝑆𝑆𝑦𝑦𝑗𝑗}𝑗𝑗𝑗𝑗𝑗𝑗𝑗𝑗 (22) 𝑆𝑆𝑢𝑢𝑝𝑝𝑝𝑝𝑆𝑆𝑦𝑦𝑗𝑗 + 𝑊𝑊𝑚𝑚𝑠𝑠𝑡𝑡𝑒𝑒𝑗𝑗 = 𝑒𝑒𝑒𝑒𝑐𝑐𝑒𝑒𝑀𝑀𝑣𝑣𝑒𝑒𝑃𝑃𝑗𝑗 (23) 𝑆𝑆𝑢𝑢𝑝𝑝𝑝𝑝𝑆𝑆𝑦𝑦𝑗𝑗 + 𝑆𝑆𝑆𝑆𝑚𝑚𝑐𝑐𝑆𝑆𝑆𝑆𝑢𝑢𝑝𝑝𝑝𝑝𝑆𝑆𝑦𝑦𝑗𝑗 = 𝑃𝑃𝑒𝑒𝑚𝑚𝑚𝑚𝑛𝑛𝑃𝑃𝑗𝑗 (24) Supply and waste are the two variables of the second stage which are inter-dependent on each other and based on the uncertain demand variable. Eq(22) is the primal sub-problem objective and Eq(23) and (24) are the constraints. The Dual of the Sub-problem: 𝑀𝑀𝑚𝑚𝑥𝑥 ∑ 𝑒𝑒𝑒𝑒𝑐𝑐𝑒𝑒𝑀𝑀𝑣𝑣𝑒𝑒𝑃𝑃𝑗𝑗𝑝𝑝𝑀𝑀_𝑠𝑠𝑢𝑢𝑝𝑝𝑝𝑝𝑆𝑆𝑀𝑀𝑒𝑒𝑃𝑃 + ∑ 𝑃𝑃𝑒𝑒𝑚𝑚𝑚𝑚𝑛𝑛𝑃𝑃𝑗𝑗𝑝𝑝𝑀𝑀_𝑠𝑠𝑢𝑢𝑝𝑝𝑝𝑝𝑆𝑆𝑦𝑦𝑚𝑚𝑚𝑚𝑥𝑥𝑗𝑗𝑗𝑗 (25) Benders Decomposition Master Problem Sub-problem Feedback (CUTS) Information (SOLUTIONS) 802 𝑝𝑝𝑀𝑀_𝑠𝑠𝑢𝑢𝑝𝑝𝑝𝑝𝑆𝑆𝑀𝑀𝑒𝑒𝑃𝑃𝑗𝑗 + 𝑝𝑝𝑀𝑀_𝑠𝑠𝑢𝑢𝑝𝑝𝑝𝑝𝑆𝑆𝑦𝑦𝑚𝑚𝑚𝑚𝑥𝑥𝑗𝑗 ≤ −𝑝𝑝𝑗𝑗 (26) 𝑝𝑝𝑀𝑀_𝑠𝑠𝑢𝑢𝑝𝑝𝑝𝑝𝑆𝑆𝑀𝑀𝑒𝑒𝑃𝑃 ≤ 𝑐𝑐𝑗𝑗 (27) 𝑝𝑝𝑀𝑀_𝑠𝑠𝑢𝑢𝑝𝑝𝑝𝑝𝑆𝑆𝑦𝑦𝑚𝑚𝑚𝑚𝑥𝑥𝑗𝑗 ≤ 0 (28) Eq(25) is the dual subproblem objective. Eq(26), Eq(27) and Eq(28) are the constraints. Here 𝒑𝒑𝒑𝒑_𝒔𝒔𝒔𝒔𝒑𝒑𝒑𝒑𝒔𝒔𝒑𝒑𝒔𝒔𝒔𝒔 and 𝒑𝒑𝒑𝒑_𝒔𝒔𝒔𝒔𝒑𝒑𝒑𝒑𝒔𝒔𝒔𝒔𝒔𝒔𝒔𝒔𝒙𝒙𝒋𝒋 are the two dual variables corresponding to the primal sub-problem. 5. Case Study Table 1 gives the demand data. Table 2 gives the data of cost of transportation. The model is solved in GAMS version 24.8.5 (CPLEX solver). Sets of sources, sites, and scenarios are declared from the start. Table 1 shows the demand outcomes and their probability. A joint probability is estimated for these 65,536 scenarios. The probability in Table 1 is considered to be independent. The Benders master problem is formed. The maximum number of iterations to be executed is provided, as well as a dynamic subset. Positive variables and equations are only specified for the first stage. Variable theta is used to represent the entire second stage function. The cutconst and the cutcoeff are two parameters that are established and used in optimality cuts. This master problem is then modeled. Next, the benders subproblem is formulated. Positive variables and equations associated with the second stage are defined. Note that the received value is constant. This is the decision passed from the first stage to the second stage. The primal subproblem and the dual subproblem are formulated using the simplex method. Apply the Benders algorithm. The first step is to solve the master problem for minimization, which is set to having no optimality cuts. The upper and lower bound for theta are defined as +inf and -inf. Now iterations are started. By duality theory, the optimal solution to the primal subproblem would be equal to the dual subproblem. When the master problem was solved without cuts, the value of the received variable is obtained which is used to solve the dual variables for each joint scenario. These dual variables define the optimality constraints that are passed back to the master problem. The upper bound is updated, including the dual subproblem solutions. A convergence test is introduced, i.e., If the gap between the best upper and lower bound is less than epsilon, the procedure terminates. The master problem is solved with added new constraints that update the lower bound, received variable, and objmaster. This process continues to the next iteration, and upper bound and lower bounds are continuously updated every iteration. The formulation has 11 single equations and 24 single variables and it takes 50 iterations to converge. The deterministic equivalent version is solved directly by specifying the equations directly in GAMS using CPLEX solver. The deterministic version has 19 single equations and 107 single variables and solution time and solution converges in 26 iterations. After solving the problem by benders, the profit value is $18,037.75. Minus value is since it is the minimum value of (- Profit) equivalent to the maximum of (+profit). Compared with the direct implementation of the deterministic equivalent model, a similar value of $18,037.75 was obtained. Table 1: Possible Consequences for demand (m3) and their probabilities Sites a1 a2 a3 a4 D1 120,0.15 140,0.30 160,0.15 170,0.40 D2 80,0.10 110,0.20 125,0.25 140,0.45 D3 200,0.05 230,0.10 260,0.35 275,0.50 D4 160,0.07 215,0.13 240,0.34 260,0.46 D5 180,0.08 195,0.22 205,0.30 255,0.40 D6 170,0.09 190,0.31 210,0.25 240,0.35 D7 190,0.16 220,0.14 250,0.50 280,0.20 D8 215,0.15 225,0.15 235,0.20 245,0.50 803 Table 2: Transport Cost from sources to sites ($/m3) Unit purification Cost=29 $/m3, Supply Price = 44 $/ m3, Cost of removal of wastewater =14 $/ m3, Scenarios- {a1,a2,a3,a4}, Sources- {S1,S2,S3,S4,S5,S6,S7,S8,S9,S10}, Sites- {D1,D2,D3,D4,D5,D6,D7,D8}, The total number of sources and sites are 10 and 8. Total scenarios=48=65,536. 6. Conclusions In this paper, two methodologies are presented. The objective of the proposed methods is to maximize profit in the water distribution network in a dual-stage stochastic environment. The first method formulates the two- stage stochastic deterministic equivalent model. The other method applies a simple Benders' decomposition to the two-stage stochastic framework. 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. Bender’s decomposition can be more fruitful for a more complicated multi-stage stochastic problem in which there is a significant increase in the number of scenarios and variables. The results obtained via the two methods are the almost same. Current research work is directed toward the development of a multistage stochastic model using Bender’s decomposition. Acknowledgements The authors would like to thank the DST-SERB, India, and the Indian Institute of Technology, Patna, for providing the research funding for this project under grant no. ECR/2018/000197. References Arya D., Shah K., Gupta A., Bandyopadhyay S., 2018, Stochastic pinch analysis to optimize resource allocation networks, Industrial & Engineering Chemistry Research, 57(48),16423-32. Benders J.F., 1962, Partitioning procedures for solving mixed-variables programming problems, Computational Management Science 2.1, 3-19. Bhosekar A., Abhay A., Marianthi I., 2021, Multiobjective modular biorefinery configuration under uncertainty, Industrial & Engineering Chemistry Research, 60.35, 12956-12969. Chaturvedi N.D., Manan Z.A., 2021, Batch process integration for resource conservation toward cleaner production–A state-of-the-art review. Journal of Cleaner Production, 318, 128609. Damsleth E., Tjolsen C.B., Omre H., Haldorsen H.H., 1992, A two-stage stochastic model applied to a North Sea reservoir, Journal of Petroleum Technology, 44(04), 402-86. Fu Q., Li T., Cui S., Liu D., Lu X., 2018, Agricultural multi-water source allocation model based on interval two- stage stochastic robust programming under uncertainty, Water Resources Management, 32(4), 1261-74. Ji L., Sun P., Ma Q., Jiang N., Huang G.H., Xie Y.L., 2017, Inexact two-stage stochastic programming for water resources allocation under considering demand uncertainties and response—A case study of Tianjin, China, Water, 9(6), p.414. Ji L., Wu T., Xie Y., Huang G., Sun L., 2020, A novel two-stage fuzzy stochastic model for water supply management from a water-energy nexus perspective, Journal of Cleaner Production, 277, p.123386. Kumawat P.K., Chaturvedi N.D., 2020, Robust targeting of resource requirement in a continuous water network, Chemical Engineering Transactions, 81, 1003-8. Murphy J., 2013, Benders, nested benders and stochastic programming: An intuitive introduction, arXiv:1312,3158. Zhang J., Nault B. R., Dimitrakopoulos R.G., 2019, Optimizing a mineral value chain with market uncertainty using benders decomposition, European Journal of Operational Research, 274.1, 227-239. D1 D2 D3 D4 D5 D6 D7 D8 D1 D2 D3 D4 D5 D6 D7 D8 S1 2.30 5.1 3.7 4.45 5.23 7.43 8.34 9.12 S6 9.92 9.94 5.59 4.42 2.22 2.23 3.34 3.39 S2 1.40 2.50 1.80 1.96 4.25 5.40 6.45 7.24 S7 5.56 5.51 9.91 8.82 8.83 8.84 5.56 6.69 S3 3.56 3.80 2.40 5.76 6.78 7.89 5.67 6.67 S8 8.84 8.86 8.97 9.21 9.28 9.30 9.56 9.45 S4 5.56 6.67 7.78 8.82 3.34 4.41 5.51 5.57 S9 6.71 8.81 9.95 3.45 5.51 5.78 5.69 5.90 S5 4.45 4.43 9.97 7.78 8.88 9.99 7.77 6.65 S10 12.4 13.6 14.6 16.8 17.9 14.6 3.45 3.67 804 PRES22_0276.pdf Maximizing Profit Using Benders Decomposition in Two-Stage Stochastic Water Distribution Network