Nested approaches for multi-stage stochastic planning problems

We present a JuMP-based solver that combines a nested primal-dual decomposition technique and convex relaxation approaches for tackling non-convex multi-stage stochastic programming problems. The approach addresses optimal long-term water supply infrastructure planning with feasibility constraints at operational timescales. We combine an outer primal decomposition of planning stages and inner dual ones of operating scenarios, with convexified non-anticipative constraints relaxed for scenarios.

The efficient operation of a series of critical infrastructures such as water networks is essential to sustainable futures. However, to sustain good infrastructure services in many places, they need continuous expansion, mainly in response to population growth and rapid industrialization. As a specific example, consider a water supply network that supplies the required demand of different consumers using the available resources. However, for the smooth operation of the network, it is necessary to find new resources and connect them to the growing demand points in an economical manner. If this expansion planning is to be done for a long-term horizon, it requires considering uncertainties on various system parameters like demands, price of electricity, and availability of resources. These conditions also are similar to a great extent for the other infrastructure networks like electric power, gas, and district heating networks with their related equations, variables, and parameters. As a result, long-term infrastructure planning problems that confront high levels of uncertainty need an appropriate approach to modeling this process. For this purpose, multi-stage stochastic programming (MSSP) can be used as a well-established approach for dynamic decision-making under uncertainty. However, due to the nonlinear equation governing the operation of physical infrastructure networks, besides the mixed-integer nature of planning decision variables, this becomes a complicated non-convex problem. In this regard, an iterative procedure based on primal-dual decomposition and convex relaxation for solving this MSSP problem is put forward. This technique is motivated by explained planning problem that requires the satisfaction of constraints that describe operational processes for water supply infrastructure at multiple timescales. Since the aim is just finding a dual for the operation problem (pump scheduling or optimal power flow), each approach, like copositive programming, that can do this task can be used for this purpose. Here, applying a dual decomposition technique, e.g., optimality condition decomposition or Lagrangian relaxation, breaks the time dependency of intra-operation intervals. It also makes amenable the operation of the system in a decentralized mode by relaxing the coupling constraints like mass conservation and nodal power balance equations. If the operation problems are considered the subproblems (second-stage), their solving generates relative cuts for the master planning problem (first-stage problem). This procedure will terminate with the convergence of outer primal decomposition to an acceptable gap. Figure 2 represents the primal\dual decomposition of the scenario tree Figure 1 in two steps. Flowchart 3 also shows the proposed solution technique graphically. The packages for solving the SP in the Julia programming language have been reviewed in Table 1. It is clear from this table that there is not any package to tackle the non-convex nonlinear mixed-integer MSSP problem. This work aims to develop a solver for this complicated MSSP problem. It also must be mentioned that although the proposed approach is applied to water supply networks, it is general enough to be used for any infrastructure network.