Seismic-Resilient Pipe Network Planning

Seismic-Resilient Pipe Network (SRPN) Planning [Huang20] is a network design problem. The goal is to choose water pipes to upgrade to earthquake-resilient ones so that the network survives most earthquake risks and still delivers water to critical customers such as evacuation centers, hospitals, and police stations. The network must also guarantee water service within a certain distance of residential areas. [Huang20] models this as the edge-weighted Steiner Network Problem with Coverage Constraints (SNP-CC). The instances are built from the water pipe networks of combinations of Los Angeles water service zones. Following [Huang20], only threatened pipes (pipes that touch a liquefaction area or lie within 500 feet of a fault zone) need replacement. Each threatened pipe costs its length, and the rest of the network is assumed safe.

Formally, we are given:

• an undirected graph \(G=(V,E)\), where the edges \(E\) are the (threatened) pipes and the nodes \(V\) are pipe junctions;
• a replacement cost \(c_{ij}\geq 0\) for every pipe \(\{i,j\}\in E\) (positive for almost all pipes; a few pipes in some Hard instances have cost 0);
• a set of water sources \(T\subseteq V\) (e.g., pumps, storages, trunk pipes);
• a set of critical customers (Steiner nodes) \(C\subseteq V\), each mapped to its closest junction;
• a set of housing areas \(R\), and for each \(r\in R\) the set \(S(r)\subseteq E\) of pipes close enough to serve \(r\) (in a few Hard instances \(S(r)\) lists a pipe twice, which gives it coefficient 2 in constraint (3) and does not change the model).

We want to find a set of pipes \(E'\subseteq E\) with minimum cost \(\sum_{e\in E'}c_e\) such that every critical customer \(u\in C\) is connected to some source in \(T\) in the subgraph induced by \(E'\), and every housing area \(r\in R\) is covered, i.e., some pipe of \(E'\cap S(r)\) is connected to a source in \(T\). In the instances, a source can also be a critical customer (it then receives its unit of flow from the super source), and pipes in \(S(r)\) can be incident to a source.

The flow-based MILP (FB-MILP) of [Huang20] works on a directed graph \(\hat G=(V\cup\{0\},\hat E\cup\{(0,t):t\in T\})\). Each undirected pipe \(\{i,j\}\in E\) becomes two arcs \((i,j),(j,i)\in\hat E\), and an artificial super source \(0\) is linked to every source \(t\in T\). \(\delta^+(v)\) and \(\delta^-(v)\) denote the outgoing and incoming arcs of \(v\) in \(\hat G\), and \(M=|\hat E|+|V|\) is the total amount of flow available. Variables:

• \(x_{ij}\in\{0,1\}\) for each arc \((i,j)\in\hat E\): 1 if pipe \(\{i,j\}\) is upgraded and used in direction \(i\to j\);
• \(y_{e}\geq 0\) for each arc \(e\in\hat E\): continuous flow on arc \(e\);
• \(y_{0t}\geq 0\) for each \(t\in T\): flow injected by the super source into source \(t\).

Flow leaves the sources. Every critical customer absorbs one unit of flow, and every selected arc consumes one unit of flow at its tail, so a node can only receive flow through selected arcs that are connected to a source.

\begin{align} &\min\;\sum_{\{i,j\}\in E}c_{ij}\,(x_{ij}+x_{ji})&\nonumber\\ &\sum_{e\in\delta^-(v)}y_e=\mathbf{1}_{[v\in C]}+\sum_{e\in\delta^+(v)}(y_e+x_e)&\forall v\in V\\ &x_{ij}+x_{ji}\leq 1&\forall \{i,j\}\in E\\ &\sum_{\{i,j\}\in S(r)}(x_{ij}+x_{ji})\geq 1&\forall r\in R\\ &y_e\leq M\,x_e&\forall e\in\hat E\\ &\sum_{t\in T}y_{0t}=|C|+\sum_{e\in\hat E}x_e&\\ &0\leq y_e\leq M&\forall e\in\hat E\cup\{(0,t):t\in T\}\\ &x_e\in\{0,1\}&\forall e\in\hat E \end{align}

Constraint (1) is flow conservation at every junction. A critical customer keeps one unit of flow, and every selected outgoing arc uses up one unit (for a source \(t\), \(\delta^-(t)\) contains the arc \((0,t)\)). Constraint (2) uses each pipe in at most one direction. Constraint (3) covers every housing area. Constraint (4) allows flow only on selected arcs. Constraint (5) makes the flow injected at the sources equal to the flow consumed by customers and selected arcs. [Huang20] also has a residual-flow variable \(z\) with \(z+\sum_{t\in T}y_{0t}=M\). It does not appear in the instances because it is implied by (5) and the bounds (6).

Instance encoding. The instance files also contain a reverse arc \((t,0)\) for every source and a binary variable for each arc \((0,t)\) and \((t,0)\). These \(2|T|\) zero-cost binaries are fixed to 0 by equality constraints, and the flow on \((t,0)\) is linked to its fixed binary through (4), so it is also 0. Hence an instance has \(2|E|+2|T|\) binary and \(2|E|+2|T|\) continuous variables (# Var B = # Var C) and \(|V|+|E|+|R|+2|E|+|T|+2|T|+1\) constraints, all with \(M=|\hat E|+|V|=2|E|+|V|\).

@misc{huang2024distributional,
      title={Distributional MIPLIB: a Multi-Domain Library for Advancing ML-Guided MILP Methods}, 
      author={Weimin Huang and Taoan Huang and Aaron M Ferber and Bistra Dilkina},
      year={2024},
      eprint={2406.06954},
      archivePrefix={arXiv},
      primaryClass={cs.LG}
}

@inproceedings{huang2020enhancing,
  title={Enhancing seismic resilience of water pipe networks},
  author={Huang, Taoan and Dilkina, Bistra},
  booktitle={Proceedings of the 3rd ACM SIGCAS Conference on Computing and Sustainable Societies},
  pages={44--52},
  year={2020}
}