Format And Type Fonts CCHHEEMMIICCAALL EENNGGIINNEEEERRIINNGG TTRRAANNSSAACCTTIIOONNSS VOL. 45, 2015 A publication of The Italian Association of Chemical Engineering www.aidic.it/cet Guest Editors: Petar Sabev Varbanov, Jiří Jaromír Klemeš, Sharifah Rafidah Wan Alwi, Jun Yow Yong, Xia Liu Copyright © 2015, AIDIC Servizi S.r.l., ISBN 978-88-95608-36-5; ISSN 2283-9216 DOI: 10.3303/CET1545223 Please cite this article as: Klemeš J.J., Varbanov P.S., 2015, Spreading the message: p-graph enhancements: implementations and applications, Chemical Engineering Transactions, 45, 1333-1338 DOI:10.3303/CET1545223 1333 Spreading the Message: P-Graph Enhancements: Implementations and Applications Jiří Jaromír Klemeš*, Petar Sabev Varbanov Centre of Process Integration and Intensification – CPI 2 , Faculty of IT, University of Pannonia, Egyetem u.10, Veszprém, Hungary klemes@cpi.uni-pannon.hu P-graph is a combinatorial optimisation framework aimed at optimising process networks. It is particularly efficient in handling problems with high combinatorial complexity and it has shown great reduction in the computational burden related to that. The current contribution provides a critical review of the P-graph framework, its fundamentals, main application areas and influence on the scientific and engineering thoughts for solving complicated real-life problems. This is followed by an analysis of the achieved impact, results and limitations. Potential opportunities for future research, development and innovation, opened by the identified limitations, are then suggested and discussed. 1. Introduction 1.1 The need for advanced process network optimisation tools The complexity of process synthesis arises from the simultaneous occurrence of continuous and combinatorial aspects in the problem. The combinatorial complexity increases exponentially with the number of candidate operating units. This imposes significant challenges to the methods for network optimisation. As one option Mathematical Programming (MP) and specifically Mixed Integer Nonlinear Programming (MINLP) have been used for reducing available superstructures. For large problems applying MP becomes increasingly difficult to create a superstructure - the infeasibilities are discovered by the solvers only after evaluating the constraints. Building the problem superstructures heuristically is time demanding and error- prone, potentially missing advantageous options. As a result, practical problems are often complex to solve. If the problem is too simplified to be easily the resulting problem can be too simple to be practical and fully representative of the original task. 1.2 The answer to the challenge: P-graph P-graph (Friedler et al., 1992) and the associated framework in terms of the main algorithm (Friedler et al., 1993), the further procedure extensions (Friedler et al., 1995) including Accelerated Branch and Bound optimisation (Friedler et al., 1996) have been developed for treating network optimisation problems. The framework has been more recently presented in detail by Klemeš et al. (2010). Over the years it has proven its efficiency and superiority in solving topologically and combinatorically challenging problems. A number of successful applications to scientific and real-live problems have been produced, demonstrating the benefit potential. However the applications have also revealed certain limitations in treating engineering problems where the units are described by separate sub-models and accounting for these complexities becomes a necessity. An example is water or steam network optimisation where the performance depends on the operating unit size. As a result, the success stories and the revealed limitations have started shaping the most important directions for future research and development of P- graph, holding the promise for most benefit for solving problems in engineering, regional development and supply chains. A comprehensive overview of the developments in the area of Process Integration for Energy Saving and Pollution reduction has been provided by Friedler (2009), where P-graph applications play a prominent role. 1334 2. P-graph fundamentals: a concise review For handling network optimisation problems of practical complexity, the P-graph framework and tools has been efficiently applied. In terms of network structure and interactions the P-graph framework can be superior to MP due to exploiting the combinatorial nature of the problem instead of transforming it to the equations. P-graph is a rigorous mathematical tool for unambiguous representation of processing networks. The associated combinatorial instruments – the axioms ensuring representation unambiguity and the algorithms for generating, reducing and optimising the maximal network structure, have several important properties resulting in the P-graph superiority. The algorithms are constructed in a way that they automatically generate and optimise the problem superstructure, following the rules and options specified by the users. This is made possible by exploiting graph theory and advanced set manipulation. The superstructure optimisation avoids the examination of infeasible combinations of binary variable values by applying the branch-and-bound paradigm. This feature considerably improves the efficiency of P-graph algorithms compared with the general integer programming solvers. As a side effect from the latter feature, the P-graph approach to network optimisation drastically reduces the combinatorial search space and can be up to 30 orders of magnitude more efficient than pure MP measured by the number of options to evaluate. 3. Major implementations in tools The P-graph framework has been implemented in several tools over the years. They are all freely available from the main web site of the framework (P-graph, 2015). The first implementation has been the command-line implementation, implementing the core algorithms for superstructure construction and optimisation. The tool requires input of the Process Network Synthesis (PNS) problem in a special format (P-graph, 2015). That tool has been superseded by a Graphical User Interface shell named “PNS Editor”, employing the essentially same code base, but providing a more convenient editing, saving and execution set of interface windows. More recently, a pair of tools have been have been added to the suite for more efficient handling of PNS problems: PNS Draw and PNS Studio. PNS Draw is intended for drawing visually P-graph instances. It allows producing well organised diagrams of P-graphs, containing materials, operating units and connectors. Editing the properties of these objects and formatting of the complete diagram are also supported. A key feature is the export of the resulting diagram to several image formats as well as to a file format suitable for PNS Studio input. PNS Studio offers a variety of features for further visualising, then solving the PNS problems employing the combinatorial and optimisation algorithms of the p-graph framework. These are followed by report exporting to Excel as well as generation of MP model formulations. 4. Applications geographical spread and topical coverage After the works establishing the P-graph framework, there have been a number of applications mainly using the discussed free tools. The published sources have been analysed using the SCOPUS (2015) database by searching the term “P-graph”. Figure 1 illustrates the geographical spread of the resulting publications. Understandably, since the fundamentals of P-graph and the main algorithms, as discussed in section 1.2 “The answer to the challenge: P-graph”, have been developed jointly by the groups of Friedler (Veszprém, Hungary) and Fan (Kansas, US), most of the author affiliations are shared among European and North American institutions. In addition to the University of Pannonia (Veszprém), European authors also come from other countries such as Austria (Graz) and Germany (Aachen). An interesting development stands behind the 14 contributions by South-East Asia. Most of them have been published in the last 2 y at an increasing rate, coming from authors from the Philippines and Malaysia. The application areas are diverse, but have the common thread that all considered problems form complex processing or information flow networks. Table 1 shows the distribution of the numbers of publication and their impact. Obviously the basic papers have been cited disproportionately higher than the application contributions, having an average of 125 citations per article. Analysing the other publications, after exclusion of the two reviews, the highest number of publications have been in the area of Supply chains and Regional Development. They also collect the second highest total citation rate. However, the highest total citations and highest specific impact have the contributions in the topic of “Reaction Pathways and Mechanisms”. 1335 Total 96 publications 43 79 14 Affiliations 3 Figure 1: Distribution of author affiliations. World map template – courtesy of (Presentation Magazine, 2015) Table 1: Publications on P-graph related topics and their impact Topical Group Publications per group Citations per group Citations per publication 1. Fundamentals 2 251 125 2. Supply chains and Regional Development 22 146 6 3. Reaction Pathways and Mechanisms 15 187 12 4. Chemical Process Synthesis 11 89 8 5. Waste minimisation and processing 4 49 12 6. Energy conversion 8 68 8 7. Separation of mixtures 7 54 7 8. Reviews 2 24 12 9. Business process management 10 46 4 10. Sustainability 3 6 2 11. Control and Operation 3 7 2 12. Routing 2 5 2 13. Scheduling 2 1 0 (0.5) 14. CO2 capture and storage 1 - - 15. Fault diagnostics 2 - - 5. P-graph applications with the strongest message and impact The optimisation of regional energy supply chains with renewables (Lam et al., 2010) has been very successful in spreading the message of P-graph based process network optimisation. This work applies a two-level procedure for the design of regional biomass utilisation networks, minimising the environmental impact. The results illustrate that the proposed procedure successfully manages the complexity of the biomass energy supply network problem, by simultaneously simplifying the corresponding infrastructure links and their eventual design and implementation tasks. Another successful work has been (Fan et al., 2002). They have introduced a graph-theoretic method for identifying reaction mechanisms in catalytic reactions. The paper presents a mathematically exact method based on P-graph by synthesising networks of pathways and evaluating them. The discussions have been based on specially developed software tools and the results have indicated higher efficiency than other combinatorial approaches. That work has been followed up by a Chemical Process Synthesis application of P-graph exploring the biochemical production of butanol from grain feedstock (Liu et al., 2004). The proposed method aims at minimising the overall cost of the resulting downstream processing flowsheet. The proposed procedure starts with the selection of possible processing units and the equipment options for them, followed by algorithmic superstructure generation and generating a set of optimal and near-optimal flowsheets for further selection by engineers. 1336 An interesting contribution on waste minimisation has been that of Halim and Srinivasan (2002a). This is the first of a series of 3 publications and the most highly cited from the series. The paper has formulated a hierarchical decision making procedure embedding P-graph and its application in the overall work flow. Using a cause-and-effect based analysis, the work provides the complete algorithm and an illustrative case study. That work was later followed by extensions developing an intelligent decision support system (Halim and Srinivasan, 2002b) and adaptation to batch processes (Halim and Srinivasan, 2006). Further notable P-graph based applications include (Lee et al., 2005) on analysing metabolic pathways, on biochemical reactions (Seo et al., 2001), regional biorefinery synthesis (Halasz et al., 2005),. Efficient energy conversion networks using fuel cells (Varbanov and Friedler, 2008) and Heat Exchanger Network Synthesis (Nagy et al., 2001). 6. Analysis of the achievements, drivers, and limitations The reviewed high-quality scientific papers illustrate clearly the power and appeal of the P-graph framework, as well as its efficiency in tackling combinatorial challenges within a diverse set of application areas. The geographical spread and the popularity of the published works show a trend of growing impact and the need for further development. The main achievements of the framework and its application have been in offering an unrivalled reduction of combinatorial burden on solvers – up to 30 orders of magnitude compared with straight application of MP. Lam (2013) has made a comprehensive analysis of the P-graph framework achievements over the years. That analysis confirms the main state-of-the-art contributions and the need for further development as follows. There have been serious strengths. One of them is the P-graph tool (P-graph, 2015). Potential users do not need very advanced training to apply it – if they submit the required data input and interpret the results. What is needed is a sufficient knowledge of the modelled subject area and sound engineering or modelling judgement. However this is a standard requirement for all optimisation tasks. The P-graph framework allows sensitivity analysis and produces usually a set of recommended solutions as opposed to the usual output from straight applications of MP. There are also still not fully exploited opportunities in synergy with Process Integration (Friedler, 2010), which are worth to be more extensively exploited (Klemeš and Varbanov, 2013). A potential for the implementation in sustainability issues can be clearly envisaged (Klemeš, 2015) and should be the important part of the future research. The framework, however, has also certain limitations. These seem rooted mainly in the current implementation philosophy of the tools, while the mathematical rigor of the P-graph framework allows future developments. The P-graph implementations have been superior and useful in providing optimal solutions for problems with clearly identifiable discrete alternatives and combinations of such alternatives. There are certain key limitations stemming mainly from the current implementations. One is the complicated user interaction for larger problems in terms of both data entry and preparation. A second issue is the inability of the framework implementations to tackle efficiently network optimisation problems where the process performance varies with capacity or the material flows mix and split, causing the need for component-wise balance. Such are, for instance, Water Integration and Combined Heat and Power (CHP) system synthesis problems. One more issue is posed by problems where it is not clear in advance what constitutes a “material” or a specific state of a stream. A typical example is the problem of Heat Exchanger Network Synthesis. Although the P-graph framework does have an implementation dealing with this topic (Nagy et al., 2003.), it features a number of additional simplifications which make it useful for illustrating the framework potential in solving the problem, but does not go all the way to solving it. 7. Conclusions and directions for future developments From the overview and analysis it has become apparent that the P-graph framework has offered a mathematically rigorous paradigm for Process Network Optimisation and Synthesis. It provides a set of axioms and algorithms for superstructure generation and reduction in an efficient way, very much superior to most other methods. It has proven very successful in a number of areas such as supply chains, regional development, reaction pathways identification, energy conversion, and so on. It has been proven by a number of positive reviews of the core research papers (Klemeš, 2014). 1337 In solving all such problems it has demonstrated a great strength in reducing the combinatorial complexity, generating a limited set of alternative solution recommendations this preserving the valuable interaction with the decision makers instead of isolating them from the decision making process. Another very useful feature is the framework’s flexibility in combining it with other procedures and network optimisation principles. The successful application to regional renewable resources utilisation by Lam et al. (2010) has clearly illustrated this where the P-graph application stage is preceded by resource targeting, regional clustering and formulation of a series of network synthesis problems to pass to the P-graph algorithm. The discussed framework limitations also form drivers for potential further research and development aiming for improvements. One prospective direction of future work will obviously concern bridging the gap between the formulations of the real network optimisation problems and the requirements of the P-graph framework implementations for clear-cut input of fixed states/materials and fixed performance of operating units. A potential way of addressing this is to provide application-specific wrapper algorithms, which would translate the domain- specific problems into the required mathematical representations. Another potential innovation stemming from this issue is to develop ways of allowing more complex and realistic internal models for the operating units. In fact, the P-graph mathematical fundamentals do not require exactly proportional models with fixed performance. While this development may not constitute a significant chemical or process engineering innovation, in terms of information technology, modelling semantics, modelling paradigm evolution and enabling further widespread application of the P-graph concept and framework, this has the potential to become a major step forward. Another potential avenue for future innovation may be the combination of P-graph with MP. Such a suggestion has also been made in (Lam, 2013). This would require the interaction of experts on P-graph with those on MP. The possible options to consider is to embed MP into the overall P-graph framework or using P-graph implementations for generating very good initial points for problems where the MP models would feature non-linear relationships resulting in Non-Linear Programming or MINLP models. Finally, as one recent development on assessing energy storage options (Ravaghi-Ardebili et al., 2013) shows, P-graph has the potential to interface with other fields of research especially in power engineering. Therefore, appropriate interfaces for data input and export would clearly be of benefit in the future framework development. Acknowledgements The authors would like to acknowledge the support and close collaboration of late Dr LT Fan from the Kansas State University in the United States related to the conception and evolution of the P - graph framework as well as in spreading the message of network optimisation. The kind help of Ms Xia Liu – a visiting researcher from South China University of Technology is also highly appreciated. With regard to the wide-spread collaboration opportunities which contributed to the development of the current analysis, the financial support of the Hungarian State and the European Union are acknowledged via the project TÁMOP-4.1.1.C-12/1/KONV-2012-0017 "Green Energy” – Cooperation of the higher education sector for the development of green economy in the area of energetic. The use of the freeware World Map template from “Presentation Magazine” (2015) is also acknowledged and highly appreciated for the improvement of the visual presentation of the current article. References Fan L.T., Bertók B., Friedler F., 2002, A graph-theoretic method to identify candidate mechanisms for deriving the rate law of a catalytic reaction. Computers and Chemistry, 26(3), 265-292. Friedler F. 2009, Process Integration, Modelling and Optimisation for Energy Saving and Pollution Reduction, Chemical Engineering Transactions, 18, 1-26. Friedler, F., 2010, Process integration, modelling and optimisation for energy saving and pollution reduction, Applied Thermal Engineering, 30 (16), 2270-2280. Friedler F., Tarján K., Huang Y.W., Fan L.T., 1992, Graph-theoretic approach to process synthesis: axioms and theorems. Chemical Engineering Science, 47(8), 1973-1988. Friedler F., Tarjan K., Huang Y.W., Fan L.T., 1993, Graph-theoretic approach to process synthesis: Polynomial algorithm for maximal structure generation. Computers and Chemical Engineering, 17(9), 929-942. Friedler F., Varga J.B., Fan L.T., 1995, Decision-Mapping: A Tool for Consistent and Complete Decisions in Process Synthesis. Chem. Eng. Sci., 50, 1755-1768. 1338 Friedler F., Varga J.B., Fehér E., Fan L.T., 1996, Combinatorially Accelerated Branch-and-Bound Method for Solving the MIP Model of Process Network Synthesis. In State of the Art in Global Optimization, Ed. Floudas, C.A., Pardalos, P.M., Kluwer Academic Publishers, Boston, Massachusetts, USA, 609-626. Halasz L., Povoden G., Narodoslawsky M., 2005, Sustainable processes synthesis for renewable resources. Resources, Conservation and Recycling, 44(3), 293-307. Halim I., Srinivasan R., 2002a, Systematic waste minimization in chemical processes. 1. Methodology. Industrial and Engineering Chemistry Research, 41(2), 196-207. Halim I., Srinivasan R., 2002b, Systematic waste minimization in chemical processes. 2. Intelligent Decision Support System. Industrial and Engineering Chemistry Research, 41(2), 208–219. Halim I., Srinivasan R., 2006, Systematic waste minimization in chemical processes. 3. Batch operations. Industrial and Engineering Chemistry Research, 45(13), 4693-4705. Klemeš, J.J., 2015, Assessing and measuring environmental impact and sustainability, Clean Technologies and Environmental Policy, 17, 577-578 Klemeš, J.J., 2014, Reviewers and reviewing, Clean Technologies and Environmental Policy, 16(6) 987– 989 Klemeš, J.J., Varbanov, P.S., 2013, Process Intensification and Integration: an assessment, Clean Technologies and Environmental Policy, 15 (3), 417-422 Klemeš J., Friedler F., Bulatov I., Varbanov P., 2010, Sustainability in the Process Industry: Integration and Optimization, McGraw Hill Companies Inc, Ney York, USA, ISBN 978-0-07-160554-0, 362 ps. Lam, H.L., 2013. Extended P-graph applications in supply chain and Process Network Synthesis. Current Opinion in Chemical Engineering, 2(4), 475-486. Lam H.L., Varbanov P.S., Klemeš J.J., 2010, Optimisation of regional energy supply chains utilising renewables: P-graph approach. Computers and Chemical Engineering, 34(5), 782-792. Lee D.-Y., Fan L.T., Park S., Sang Y.L., Shafie S., Bertók B., Friedler F., 2005, Complementary identification of multiple flux distributions and multiple metabolic pathways. Metabolic Engineering, 7(3), 182-200. Liu J., Fan L.T., Seib P., Friedler F., Bertok B., 2004, Downstream process synthesis for biochemical production of butanol, ethanol, and acetone from grains: Generation of optimal and near-optimal flowsheets with conventional operating units. Biotechnology Progress, 20(5), 1518-1527. Nagy A.B., Adonyi R., Halasz L., Friedler F., Fan L.T., 2001, Integrated Synthesis of Process and Heat Exchanger Networks: Algorithmic Approach. Applied Thermal Engineering, 21, 1407–1427. P-graph, 2015. Demonstration Programs accessed 01/04/2015. Presentation Magazine, 2015, World Maps Vector Editable – Updated accessed 07/06/2015. Ravaghi-Ardebili Z., Manenti F., Corbetta M., Lima N.M.N., Zuniga Linan L., Papasidero D., 2013, Assessment of direct thermal energy storage technologies for concentrating solar power plants. Chemical Engineering Transactions, 35, 547-552. SCOPUS, 2015, Scopus - Document search, , accessed 29/03/2015. Seo H., Lee D.-Y., Park S., Fan L.T., Shafie S., Bertók B., Friedler F., 2001, Graph-theoretical identification of pathways for biochemical reactions. Biotechnology Letters, 23(19), 1551-1557. Varbanov P., Friedler F., 2008, P-graph methodology for cost-effective reduction of carbon emissions involving fuel cell combined cycles. Applied Thermal Engineering, 28(16), 2020-2029.