Partitioning and Tearing of Networks Applied to Process Flowsheeting

“Partitioning and Tearing of Networks Applied to Process Flowsheeting”

Authors: Truls Gundersen and Terje Hertzberg,
Affiliation: Norsk Hydro and NTNU, Department of Chemical Engineering
Reference: 1983, Vol 4, No 3, pp. 139-165.

Keywords: Decomposition, graph theory, process flowsheeting, modular systems

Abstract: A review of the methods available for identification of the computational sequence in modular process simulators (partitioning and tearing) is followed by the presentation of a new very efficient and close-to-optimal routine for tearing. The problem of partitioning can be solved in computer times that are linear functions of the number of unit modules (vertices in the graph). The algorithm of Johns has been found to execute faster than the later and far better known algorithm of Tarjan. These methods are almost identical in idea but use different techniques in the book-keeping.

PDF

PDF (1804 Kb) DOI: 10.4173/mic.1983.3.2

DOI forward links to this article:

[1] G.V. Varma, K.H. Lau and D.L. Ulrichson (1993), doi:10.1016/0098-1354(93)80026-J

[2] A. Aspelund, T. Gundersen, J. Myklebust, M.P. Nowak and A. Tomasgard (2010), doi:10.1016/j.compchemeng.2009.10.018

[3] M. Hillestad and T. Hertzberg (1986), doi:10.1016/0098-1354(86)87008-9

[4] J.F. Cordoba (1988), doi:10.1016/0098-1354(88)85010-5

[5] M. Hillestad and T. Hertzberg (1988), doi:10.1016/0098-1354(88)85056-7

[6] J. R. ROACH, B. K. O'NEILL and D. A. HOCKING (1997), doi:10.1080/00986449708936616

[7] Magne Hillestad and Terje Hertzberg (1986), doi:10.4173/mic.1986.3.1

[8] S. LAKSHMINARAYANAN, S. SUBBA RAO and CH. DURGAPRASADA RAO (1992), doi:10.1080/00986449208936028

[9] Fei Zhao, Xi Chen and Lingyu Zhu (2016), doi:10.1016/B978-0-444-63428-3.50167-3

[10] Fei Zhao, Xi Chen and Lingyu Zhu (2017), doi:10.1002/aic.15622

[11] Shamsheer S. Chauhan, John T. Hwang and Joaquim R. R. A. Martins (2018), doi:10.1007/978-3-319-67988-4_7

[12] Andreas Möller and Jan Hedemann (2018), doi:10.1007/978-3-658-20380-1_23

[13] Shamsheer S. Chauhan, John T. Hwang and Joaquim R. R. A. Martins (2018), doi:10.1007/s00158-018-2004-5

[14] Delin Qu, Dengwen Sun, Masaaki Muraki and Toyohiko Hayakawa (1992), doi:10.1252/jcej.25.28

[15] Delin Qu, Dengwen Sun, Masaaki Muraki and Toyohiko Hayakawa (1992), doi:10.1252/jcej.25.527

[16] Andreas Moeller (2015), doi:10.1007/978-3-319-09228-7_18

[17] Ali Baharev, Hermann Schichl, Arnold Neumaier and Tobias Achterberg (2021), doi:10.1145/3446429

[18] Elias Martinez-Hernandez (2022), doi:10.1016/j.dche.2022.100075

[19] B. Lohe and E. Futterer (1994), doi:10.1002/9783527624867.ch3

References:
[1] BAKER, J.J. (1962). A note on multiplying boolean matrices, Comm. of the ACM, 5, 102 doi:10.1145/366792.366825
[2] BARKLEY, R.W., MOTARD, R.L. (1972). Decomposition of nets, Chem. Eng. J., 3, 265-275 doi:10.1016/0300-9467(72)85030-5
[3] BERGE, C. (1962). The theory of graphs and its applications, John Wiley and Sons, New York.
[4] BERGER, F., PERRIS, F.A. (1979). FLOWPACK II - a new generation of systems for steady state process flowsheeting, Comp. and Chem. Eng., 3, 309-317 doi:10.1016/0098-1354(79)80052-6
[5] BILLINGSLEY, D.S. (1967). Letter to editor, Chem. Eng. Sci., 22, 719 doi:10.1016/0009-2509(67)80060-5
[6] BOWIE, W.S. (1976). Applications of graph theory in computer systems, Int. J. of Comp. and Inf. Sci., 5, 9-31 doi:10.1007/BF00991069
[7] CHEUNG, L.K., KUH, E.S. (1974). The bordered triangular matrix and minimum essential sets of a digraph, IEEE Trans. Circ. Sys., CAS-21, 631-639.
[8] CHRISTENSEN, J.H., RUDD, D.F. (1969). Structuring design computations, AIChE J., 15, 94-100 doi:10.1002/aic.690150122
[9] DAHL, O.-J., MYHRHAUG, B., NYGAARD, K. (1968). SIMULA 67 - common base language, publ. no. S-2.Norwegian Computing Center, Oslo.
[10] DIVIETI, L., GRASSELI, A. (1968). On the determination of minimum feedback arc and vertex sets, IEEE Trans. Circ. Theory, CAT-15, 86-89 doi:10.1109/TCT.1968.1082764
[11] DUFF, I.S. (1981). On algorithms for obtaining a maximum transversal, ACM Trans. on Math. Software, 7, 315-330 doi:10.1145/355958.355963
[12] DUFF, I.S. (1981). Algorithm 575, Permutations for a zero-free diagonal. ACM Trans. on Math. Software, 7, 387-390 doi:10.1145/355958.355968
[13] DUFF, I.S., REID, J.K. (1976). An implementation of Tarjan´s algorithm for the block triangularization of a matrix, AERE Harwell report CSS29.
[14] FORD, L.R., FULKERSON, D.R. (1962). Flows in networks, Princeton University Press.
[15] FORDER, G.J., HUTCHISON, H.P. (1969). The analysis of chemical plant flowsheets, Chem. Eng. Sci., 24, 771-785 doi:10.1016/0009-2509(69)80068-0
[16] GENNA, P.L., MOTARD, R.L. (1975). Optimal decomposition of process networks, AIChE J., 21, 4, 656-663 doi:10.1002/aic.690210403
[17] GUARDABASSI, G. (1971). A note on minimal essential sets, IEEE Trans. Circ. Theory, CAT-18, 557-560 doi:10.1109/TCT.1971.1083332
[18] GUARDABASSI, G., SANGIOVANNI-VINCENTELLI, A. (1976). A two level algorithm for tearing, IEEE Trans. Circ. Sys., CAS-23, 783-791 doi:10.1109/TCS.1976.1084171
[19] GUNDERSEN, T. (1982). Decomposition of large scale chemical engineering systems, Dr. Ing. thesis, Dep. of Chem. Eng., Univ. of Trondheim, Norway.
[20] GUPTA, P.K., WESTERBERG, A.W., HENDRY, J.E., HUGHES, R.R. (1974). Assigning output variables to equations using linear programming, AIChE J., 20, 397-399 doi:10.1002/aic.690200231
[21] GUSTAVSON, F.G. (1976). Finding the block lower trangular form of a sparse matrix, in Bunch J.R. and Rose D.J. (eds) Sparse matrix computations, pp. 275-289 (Academic Press, New York).
[22] HARARY, F. (1969). Graph theory, Addison-Wesley, Reading, Mass.
[23] HIMMELBLAU, D.M. (1966). Decomposition of large scale systems-1, Systems composed of lumped parameter elements. Chem. Eng. Sci., 21, 425-438 doi:10.1016/0009-2509(66)85054-6
[24] HIMMELBLAU, D.M. (1967). Decomposition of large scale systems-2, Systems containing nonlinear elements. Chem. Eng, Sci, 22, 883-895 doi:10.1016/0009-2509(67)80152-0
[25] HLAVACEK, V. (1977). Analysis of a complex plant - steady state and transient behaviour (Journal review), Comp. and Chem. Eng., 1, 75-100 doi:10.1016/0098-1354(77)80011-2
[26] HOPCROFT, J.E., KARP, R.M. (1973). An n5/2 algorithm for maximum matchings in bipartite graphs, SIAM J. Comput., 2, 225-231 doi:10.1137/0202019
[27] JAIN, Y.V.S., EAKMAN, J.M. (1971). Identification of process flow networks, AIChE 68th meeting, Houston, Texas, Feb. 1971.
[28] JENNINGS, A. (1977). Matrix computations for engineers and scientists, John Wiley and Sons.
[29] JENSEN, K., WIRTH, N. (1978). PASCAL - user manual and report, 2nd ed..Springer Verlag.
[30] JOHNS, W.R. (1970). Mathematical considerations in preparing general purpose computer programs for the design or simulation of chemical processes, European Confed. of Chem. Eng. Conf, Florence, Italy, April 1970.
[31] JOHNS, W.R. (1981). Personal communication, Dep. of Chem. Eng., Polytechnic of the South Bank, London, Nov.
[32] JOHNS, W.R. (1982). Re-weighting algorithms for tearing graphs representing process flow-sheets, Inst. Chem. Engrs. Jubilee Symp., London, April 5-7.
[33] JOHNS, W.R., MÜLLER, F. (1976). Optimal sequence for computer flowsheeting calculations, Technisch-Chemisches Labor, Eidgenossisches Technische Hochschule Zürich.
[34] KARP, R.M. (1972). Reducibility among combinatorial problems in Miller RE and Thatcher JW, Complexity of computer computations, pp. 85-104.Plenum Press, New York.
[35] KEHAT, E., SHACHAM, M. (1973). Partitioning and tearing of system flowsheets, Proc. Techn., 18, 115-118.
[36] KEVORKIAN, A.K. (1980). General topological results on the construction of a minimum essential set of a directed graph, IEEE: Trans. Circ. Sys., CAS-27, 293-304 doi:10.1109/TCS.1980.1084814
[37] KEVORKIAN, A.K., SNOEK, J. (1973). Decomposition in large scale systems, Theory and applications of structural analysis in partitioning, disjointing and constructing hierarchical systems, in Himmelblau D.M. (ed) Decomposition of large scale problems (Elsevier).
[38] LEDET, W.P., HIMMELBLAU, D.M. (1970). Decomposition procedures for the solving of large scale systems, from Advances in Chemical Engineering, pp. 185-254.
[39] LEE, W., RUDD, D.F. (1966). On the ordering of recycle calculations, AIChE J., 12, 1184-1190 doi:10.1002/aic.690120625
[40] MAH, R.S.H. (1974). A constructive algorithm for computing the reachability matrix, AIChE J., 20, 1227-1228 doi:10.1002/aic.690200630
[41] MCCLUSCKY, E.J. (1965). An introduction to the theory of switching circuits, McGraw-Hill, New York.
[42] MOTARD, R.L., WESTERBERG, A.W. (1981). Exclusive tear sets for flowsheets, AIChE J., 27, 725-732 doi:10.1002/aic.690270504
[43] MUNRO, I. (1971). Efficient determination of the transitive closure of a directed graph, Information Proc. Letters, 1, 56-58 doi:10.1016/0020-0190(71)90006-8
[44] NETTER, Z. (1961). Graphs and directed sum matrices, I.R.E. Trans. on Cire theory, CT-8,77-78.
[45] NORMAN, R.L. (1965). A matrix method for location of cycles of a directed graph, AIChE J., 11, 450-452 doi:10.1002/aic.690110316
[46] PERKINS, J.D., SARGENT, R.W.H. (1982). SPEEDUP: A computer program for steady-state and dynamic simulation and design of chemical processes, AIChE Symp. Ser., 78, 1-11.
[47] PHO, T.K., LAPIDUS, L. (1973). An optimum tearing algorithm for recycle systems, AIChE J., 19, 1170-1181 doi:10.1002/aic.690190614
[48] PURDOM, P. (1970). A transitive closure algorithm, BIT, 10, 76-94 doi:10.1007/BF01940892
[49] RUBIN, D.I. (1962). Generalized material balance, C.E.P. Symp. Ser., 58, 54-61.
[50] SARGENT, R.W.H., WESTERBERG, A.W. (1964). SPEEDUP in chemical engineering design, Trans. Inst. Chem. Eng., 42, T190-T197.
[51] SMITH, G.W., WALFORD, R.B. (1975). The identification of a minimal feedback vertex set of a directed graph, IEEE Trans. Circ. Sys., CAS-22, 9-15 doi:10.1109/TCS.1975.1083961
[52] STEWARD, D.V. (1962). On an approach to techniques for the analysis of the structure of large systems of equations, SIAM Review, 4, 321-342 doi:10.1137/1004088
[53] STEWARD, D.V. (1965). Partitioning and tearing systems of equations, J. SIAM, Numer. anal..ser. B, 2, 345-365.
[54] TARJAN, R. (1972). Depth first search and linear graph algorithms, SIAM J. Computing, 1, 146-160 doi:10.1137/0201010
[55] TARJAN, R. (1973). Enumeration of the elementary circuits of a directed graph, SIAM J. Computing, 2, 211-216 doi:10.1137/0202017
[56] THORELLI, L.E. (1966). An algorithm for computing all paths in a graph, BIT 6, 347-349 doi:10.1007/BF01966095
[57] TIERNAN, J.C. (1970). An efficient algorithm to find the elementary circuits of a graph, Comm. of the ACM, 13, 722-726 doi:10.1145/362814.362819
[58] TSUKIYAMA, S., SHIRAKAWA, I., OZAKI, H. (1975). An algorithm for generating the cycles of a digraph, Electronics and Communications in Japan, 58-A, 8-15.
[59] UPADHYE, R.S., GRENS, E.A. II (1972). An efficient algorithm for optimum decomposition of recycle systems, AIChE J., 18, 533-539 doi:10.1002/aic.690180312
[60] UPADHYE, R.S., GRENS, E.A., II (1975). Selection of decomposition for chemical process simulation, AIChE J., 21, 136-143 doi:10.1002/aic.690210117
[61] WARSHALL, S. (1962). A theorem on boolean matrices, J. of the ACM, 9, 11-12 doi:10.1145/321105.321107
[62] WEINBLATT, H. (1972). A new search algorithm for finding the simple cycles of a finite directed graph, J. of the ACM, 19, 43-56 doi:10.1145/321679.321684
[63] WESTERBERG, A.W., EDIE, F.C. (1971). An approach to convergence and tearing in the solution of sparse equation sets, Ch. Eng. J., 2, 17-24 doi:10.1016/0300-9467(71)87003-X

BibTeX:
@article{MIC-1983-3-2,
  title={{Partitioning and Tearing of Networks Applied to Process Flowsheeting}},
  author={Gundersen, Truls and Hertzberg, Terje},
  journal={Modeling, Identification and Control},
  volume={4},
  number={3},
  pages={139--165},
  year={1983},
  doi={10.4173/mic.1983.3.2},
  publisher={Norwegian Society of Automatic Control}
};

Article

“Partitioning and Tearing of Networks Applied to Process Flowsheeting”