Optimization-Based Business Process Model Matching





Process Model Matching, Optimization Problem, Integer Linear Programming, Behavioral Similarity


The rapid increase in generation of business process models in the industry has raised the demand on the development of process model matching approaches. In this paper, we introduce a novel optimization-based business process model matching approach which can flexibly incorporate both the behavioral and label information of processes for the identification of correspondences between activities. Given two business process models, we achieve our goal by defining an integer linear program which maximizes the label similarities among process activities and the behavioral similarity between the process models. Our approach enables the user to determine the importance of the local label-based similarities and the global behavioral similarity of the models by offering the utilization of a predefined weighting parameter, allowing for flexibility. Moreover, extensive experimental evaluation performed on three real-world datasets points out the high accuracy of our proposal, outperforming the state of the art.


Download data is not yet available.


van der Aalst, W.M.P.: Process Mining: Data Science in Action. Springer, Heidelberg, 2 edn. (2016)

Antunes, G., Bakhshandeh, M., Borbinha, J., Cardoso, J., Dadashnia, S., Francescomarino, C.D., Dragoni, M., Fettke, P., Gal, A., Ghidini, C., Hake, P., Khiat, A., Klinkmüller, C., Kuss, E., Leopold, H., Loos, P., Meilicke, C., Niesen, T., Pesquita, C., Peus, T., Schoknecht, A., Sheetrit, E., Sonntag, A., Stuckenschmidt, H., Thaler, T., Weber, I., Weidlich, M.: The Process Model Matching Contest 2015. In: EMISA’15: International Workshop on Enterprise Modelling and Information Systems Architecture. pp. 127–155. GI, Innsbruck, Austria (Sep 2015)

Becker, J., Breuker, D., Delfmann, P., Dietrich, H.A., Steinhorst, M.: Identifying Business Process Activity Mappings by Optimizing Behavioral Similarity. In: AMCIS. vol. 1, p. Paper 21 (01 2012)

Becker, M., Laue, R.: A Comparative Survey of Business Process Similarity Measures.Computers in Industry 63(2), 148 – 167 (2012)

Cayoglu, U., Dijkman, R., Dumas, M., Fettke, P., Garc´ıa-Ba˜nuelos, L., Hake, P., Klinkm¨ uller, C., Leopold, H., Ludwig, A., Loos, P., Mendling, J., Oberweis, A., Schoknecht, A., Sheetrit, E., Thaler, T., Ullrich, M., Weber, I., Weidlich, M.: Report: The Process Model Matching Contest 2013. In: Lohmann, N., Song, M., Wohed, P. (eds.) Business Process Management Workshops. pp. 442–463. Springer International Publishing, Cham (2014)

Dijkman, R.M., Dumas, M., van Dongen, B.F., K¨a¨ arik, R., Mendling, J.: Similarity of Business Process Models: Metrics and Evaluation. Inf. Syst. 36(2), 498–516 (2011)

Dumas, M., Garc´ıa-Ba˜nuelos, L., Dijkman, R.M.: Similarity Search of Business Process Models. IEEE Data Eng. Bull. 32(3), 23–28 (2009)

Euzenat, J., Shvaiko, P.: Ontology Matching. Springer Publishing Company, Incorporated, 2nd edn. (2013)

Gurobi Optimization LLC: Gurobi Optimizer Reference Manual (2019), http://www.gurobi.com

Hillier, F., Lieberman, G.: Introduction to Linear Programming. McGraw-Hill (1990)

Klinkm¨ uller, C., Weber, I., Mendling, J., Leopold, H., Ludwig, A.: Increasing Recall of Process Model Matching by Improved Activity Label Matching. In: Business Process Management. pp. 211–218. Springer Berlin Heidelberg (2013) [12] Leopold, H., Niepert, M., Weidlich, M., Mendling, J., Dijkman, R., Stuckenschmidt, H.: Probabilistic Optimization of Semantic Process Model Matching. In: Business Process Management. pp. 319–334. Springer Berlin Heidelberg (2012)

Lin, D.: An Information-theoretic Definition of Similarity. In: Proc. of the 15th International Conference on Machine Learning. vol. 98, pp. 296–304. Morgan Kaufmann (1998)

Pegoraro, M., Uysal, M.S., van der Aalst,W.M.P.: Discovering Process Models from Uncertain Event Data. In: Business Process Management Workshops. pp. 238–249. Springer International Publishing, Cham (2019)

Petri, C.A.: Kommunikation mit Automaten. Schriften des Rheinisch-Westfälischen Institutes für Instrumentelle Mathematik an der Universit ¨ at Bonn, Technische Hochschule, Darmstadt. (1962), https://books.google.de/books?id=NCZMvAEACAAJ

Schoknecht, A., Thaler, T., Fettke, P., Oberweis, A., Laue, R.: Similarity of Business Process Models – A State-of-the-Art Analysis. ACM Comput. Surv. 50(4), 52:1–52:33 (Aug 2017)

Thaler, T., Schoknecht, A., Fettke, P., Oberweis, A., Laue, R.: A Comparative Analysis of Business Process Model Similarity Measures. In: Business Process Management Workshops. pp. 310–322. Springer International Publishing, Cham (2017)

Uysal, M.S., van Zelst, S.J., Brockhoff, T., Ghahfarokhi, A.F., Pourbafrani, M., Schumacher, R., Junglas, S., Schuh, G., van der Aalst, W.M.: Process Mining for Production Processes in the Automotive Industry. In: Industry Forum at BPM 2020 co-located with 18th International Conference on Business Process Management (BPM 2020), Sevilla, Spain (2020)

van der Aalst,W.,Weijters, T., Maruster, L.: Workflow Mining: Discovering Process Models from Event Logs. IEEE Transactions on Knowledge and Data Engineering 16(9), 1128–1142 (Sep 2004)

van der Aalst, W.: The Application of Petri-nets to Workflow Management. Journal of Circuits, Systems and Computers 8(1), 21–66 (1998)

Weidlich, M., Mendling, J., Weske, M.: Efficient Consistency Measurement Based on Behavioral Profiles of Process Models. IEEE Transactions on Software Engineering 37(3), 410–429 (May 2011)

Weidlich, M., Mendling, J., Weske, M.: Computation of Behavioural Profiles of Process Models. Business Process Technology, Hasso Plattner Institute for IT-Systems Engineering. Potsdam (2009)

Weigel, A., Fein, F.: Normalizing the Weighted Edit Distance. In: Proceedings of the 12th IAPR International Conference on Pattern Recognition, Vol. 3 - Conference C: Signal Processing. vol. 2, pp. 399–402 vol.2 (Oct 1994)

Wen, L., Song, J., Wang, J., Kumar, A.: BP+: An Improved Behavioral Profile Metric for Process Models. https://www.researchgate.net/publication/286932844 (2015), accessed: 01.02.2021