Process decomposition method with reachable vector.

Delin Qu, Dengwen Sun, Masaaki Muraki, Toyohiko HayakawaJOURNAL 1992 · DOI

Abstract

Based on graph theory and the concept of degree of vertex, a new reachable vector method for network decomposition is proposed in this paper. It differs from the traditional tearing algorithms which first find maximal cyclical nets and elementary cycles, and then tear elementary cycles to get a set of cut streams that break all cycles in the flow of information. In the proposed method the initial precedence sequence of vertex is formulated by introducing the conception of the degree of vertex, which serves as a reasonable primary structure for further adjustment. Then a reachable vector is presented instead of the reachable matrix to adjudge the position of vertices. With this new method a set of torn streams and calculation sequence of the process considered are obtained directly, and it is simple and easy to understand and program. Ten test problems are examined, and the new tearing algorithm finds the minimum number of tears for all ten problems. It indicates the effectiveness of the proposed method in the process decomposition.

1. Introduction

In chemical engineering, the simulation of large-scale industrial plants often relies on the sequential modular approach. In this framework, each unit operation—such as a reactor, heat exchanger, or distillation column—is calculated sequentially. However, real-world process networks are frequently characterized by complex recycle streams, creating feedback loops where the output of one unit eventually returns as an input to an upstream unit.

To solve these systems, engineers must perform "tearing." This involves selecting specific streams to "tear," assigning initial guesses to their values, calculating through the resulting open-loop sequence, and iterating until the guessed values match the calculated outputs. The primary challenge is finding the minimum number of tears required to break all cycles in the graph. Minimizing tears typically leads to faster numerical convergence and reduced computational strain. Traditional algorithms often require identifying every elementary cycle, a process that becomes computationally "explosive" as network complexity increases.

2. Methodology

The authors propose a streamlined strategy to address the tearing problem by focusing on dimensionality reduction and efficient heuristics.

2.1 Precedence Sequencing via Vertex Degree

Rather than initiating the algorithm with a random sequence, the method establishes an initial order based on the "degree" of each vertex (unit). This degree, $\delta$, is defined as the difference between the number of incoming streams and outgoing streams ($\delta = \text{in-degree} - \text{out-degree}$). By arranging units in descending order of this degree, the algorithm creates a "reasonable primary structure" that statistically minimizes the number of feedback flows from the outset, reducing the need for extensive subsequent adjustments.

2.2 The Reachable Vector

A core innovation of this paper is the replacement of the traditional $n \times n$ reachable matrix with a one-dimensional reachable vector. While a matrix requires $O(n^2)$ memory to track whether any unit can reach another, the reachable vector tracks reachability from a specific point of interest using Boolean logic. This reduction in dimensionality was particularly significant for enabling the decomposition of massive networks on the workstations of the early 1990s.

The algorithm iteratively examines "counter streams"—those that flow against the established calculation sequence. By applying Boolean operations to the reachable vector, the algorithm determines if a counter stream completes a cycle. If it does, the stream is added to the "torn set." If not, the sequence is adjusted to convert the counter stream into a "direct stream," thereby avoiding an unnecessary tear.

3. Experimental Evaluation

The proposed method was evaluated using a suite of ten standard test problems originally collected by Gundersen (1983). These benchmarks represent a wide spectrum of industrial complexity.

Table 1: Dimensions of the ten test problems used to evaluate the algorithm.

As shown in Table 1, the problems range from small networks (6 vertices) to highly complex systems, such as a heavy water plant (Problem 10) featuring 109 vertices and over 13,000 elementary cycles.

4. Results and Discussion

The reachable vector method demonstrated high efficiency and optimality across all test cases. It successfully identified the minimum number of tears for all ten problems, outperforming Gundersen’s original algorithm in four of the more complex cases where the latter failed to find the absolute minimum.

Figure 5: A complex process network (Problem 7) with 30 vertices.

Figure 5 illustrates Problem 7, a network with 30 vertices and 42 edges. Decomposing such a network manually or with exhaustive cycle-finding algorithms is prone to error and computational lag. In contrast, the proposed algorithm reached solutions rapidly; even the massive Problem 10 was solved in just 34.2 seconds on a SUN 3/140 workstation. The simplicity of the logic, implemented in Fortran 77, makes it significantly easier to program than traditional branch-and-bound or enumeration methods.

5. Conclusion

The reachable vector method offers a robust and efficient alternative to traditional cycle-tearing algorithms. By leveraging vertex degree heuristics and reducing the memory footprint of reachability analysis, the method achieves optimal results even for large-scale process networks. While the current study focuses on non-weighted tearing—where all streams are treated as equally difficult to converge—the underlying logic provides a strong foundation for future extensions into weighted stream analysis and modern large-scale graph processing.

Summary updated

Abstract

Based on graph theory and the concept of degree of vertex, a new reachable vector method for network decomposition is proposed in this paper. It differs from the traditional tearing algorithms which first find maximal cyclical nets and elementary cycles, and then tear elementary cycles to get a set of cut streams that break all cycles in the flow of information. In the proposed method the initial precedence sequence of vertex is formulated by introducing the conception of the degree of vertex, which serves as a reasonable primary structure for further adjustment. Then a reachable vector is presented instead of the reachable matrix to adjudge the position of vertices. With this new method a set of torn streams and calculation sequence of the process considered are obtained directly, and it is simple and easy to understand and program.Ten test problems are examined, and the new tearing algorithm finds the minimum number of tears for all ten problems. It indicates the effectiveness of the proposed method in the process decomposition.
BibTeX
@article{qu1992process,
  author = {Delin Qu and Dengwen Sun and Masaaki Muraki and Toyohiko Hayakawa},
  title = {{Process decomposition method with reachable vector.}},
  journal = {JOURNAL},
  year = {1992},
  doi = {10.1252/jcej.25.28},
}
Figure